×

State-space realizations of periodic convolutional codes. (English) Zbl 1501.94101

Summary: Convolutional codes are discrete linear systems over a finite field and can be defined as \(\mathbb{F}[d]\)-modules, where \(\mathbb{F}[d]\) is the ring of polynomials with coefficient in a finite field \(\mathbb{F}\). In this paper we study the algebraic properties of periodic convolutional codes of period 2 and their representation by means of input-state-output representations. We show that they can be described as \(\mathbb{F}[d^2]\)-modules and present explicit representation of the set of equivalent encoders. We investigate their state-space representation and present two different but equivalent types of state-space realizations for these codes. These novel representations can be implemented by realizing two linear time-invariant systems separately and switching the input (or the output) that is entering (or leaving) the system. We investigate their minimality and provide necessary and also sufficient conditions in terms of the reachability and observability properties of the two linear systems involved. The ideas presented here can be easily generalized for codes with period larger than 2.

MSC:

94B10 Convolutional codes
93B20 Minimal systems representations
93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
Full Text: DOI

References:

[1] J. Rosenthal, Connections between linear systems and convolutional codes, in Codes, Systems and Graphical Models, IMA Vol. Math. Appl. 123, B. Marcus and J. Rosenthal, eds., Springer, New York, 2001, pp. 39-66. · Zbl 0993.94559
[2] J. L. Massey and M. K. Sain, Codes, automata, and continuous systems: Explicit interconnections, IEEE Trans. Automat. Control, 12 (1967), pp. 644-650.
[3] G. D. Forney, Algebraic structure of convolutional codes, and algebraic system theory, in Mathematical System Theory, Springer, Berlin, Heidelberg, 1991, pp. 527-557. · Zbl 0751.94011
[4] G. D. Forney, The Viterbi algorithm, Proc. IEEE, 61 (1973), pp. 268-278.
[5] G. D. Forney, Minimal realizations of linear systems: The shortest basis approach, IEEE Trans. Inform. Theory, 57 (2011), pp. 726-737. · Zbl 1366.93112
[6] T. Kailath, Linear Systems, Prentice Hall Inform. System Sci. Ser., Prentice-Hall, Englewood Cliffs, NJ, 1980. · Zbl 0454.93001
[7] J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory, IT-15 (1969), pp. 122-127. · Zbl 0167.18101
[8] J. Rosenthal, J. M. Schumacher, and E. V. York, The Behavior of Convolutional Codes, Report BS-R9533, CWI, Amsterdam, 1995.
[9] G. D. Forney, Jr., Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control Optim., 13 (1975), pp. 493-520, https://doi.org/10.1137/0313029. · Zbl 0269.93011
[10] G. D. Forney, R. Johannesson, and Z.-X. Wan, Minimal and canonical rational generator matrices for convolutional codes, IEEE Trans. Inform. Theory, IT-42 (1996), pp. 1865-1880. · Zbl 0881.94023
[11] H. Gluesing-Luerssen and G. Schneider, State space realizations and monomial equivalence for convolutional codes, Linear Algebra Appl., 425 (2007), pp. 518-533. · Zbl 1140.94016
[12] D. J. Costello, Free distance bounds for convolutional codes, IEEE Trans. Inform. Theory, 20 (1974), pp. 356-365. · Zbl 0298.94009
[13] M. Mooser, Some periodic convolutional codes better than any fixed code (Corresp.), IEEE Trans. Inform. Theory, 29 (1983), pp. 750-751. · Zbl 0512.94013
[14] R. Palazzo, A time-varying convolutional encoder better than the best time-invariant encoder, IEEE Trans. Inform. Theory, 39 (1993), pp. 1109-1110. · Zbl 0783.94016
[15] R. Johannesson and K. Sh. Zigangirov, Fundamentals of Convolutional Coding, IEEE Press, New York, 1999. · Zbl 0964.94024
[16] P. J. Lee, There are many good periodically time-varying convolutional codes, IEEE Trans. Inform. Theory, 35 (1989), pp. 460-463.
[17] D. Truhachev, K. S. Zigangirov, and D. J. Costello, Distance bounds for periodically time-varying and tail-biting LDPC convolutional codes, IEEE Trans. Inform. Theory, 56 (2010), pp. 4301-4308. · Zbl 1366.94629
[18] A. J. Feltstrom, D. Truhachev, M. Lentmaier, and K. S. Zigangirov, Braided block codes, IEEE Trans. Inform. Theory, 55 (2009), pp. 2640-2658. · Zbl 1367.94403
[19] F. Fekri, M. Sartipi, R. M. Mersereau, and R. W. Schafer, Convolutional codes using finite-field wavelets: Time-varying codes and more, IEEE Trans. Signal Process., 53 (2005), pp. 1881-1896. · Zbl 1370.94584
[20] J. Justesen, New convolutional code constructions and a class of asymptotically good time-varying codes, IEEE Trans. Inform. Theory, 19 (1973), pp. 220-225. · Zbl 0254.94018
[21] J. J. Climent, V. Herranz, C. Perea, and V. Tomás, A systems theory approach to periodically time-varying convolutional codes by means of their invariant equivalent, in Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Springer, Berlin, Heidelberg, 2009, pp. 73-82. · Zbl 1273.94391
[22] D. Napp, R. Pereira, and P. Rocha, A state space approach to periodic convolutional codes, in Coding Theory and Applications, Á. I. Barbero, V. Skachek, and Ø. Ytrehus, eds., Springer, Cham, 2017, pp. 238-247. · Zbl 1429.94095
[23] D. Napp, R. Pereira, R. Pinto, and P. Rocha, Periodic state-space representations of periodic convolutional codes, Cryptogr. Commun., 11 (2019), pp. 585-595. · Zbl 1454.94132
[24] M. Ait Rami and D. Napp, Discrete-time positive periodic systems with state and control constraints, IEEE Trans. Automat. Control, 61 (2016), pp. 234-239. · Zbl 1359.93268
[25] S. Bittanti and P. Colaneri, Periodic Systems, Filtering and Control, Springer, London, 2009. · Zbl 1163.93003
[26] J. C. Aleixo, P. Rocha, and J. C. Willems, State space representation of SISO periodic behaviors, in Proceedings of the 50th Annual IEEE Conference on Decision and Control and European Control Conference, 2011, pp. 1545-1550.
[27] P. Bolzern and P. Colaneri, The periodic Lyapunov equation, SIAM J. Matrix Anal. Appl., 9 (1988), pp. 499-512, https://doi.org/10.1137/0609041. · Zbl 0662.93050
[28] M. Kuijper, A periodically time-varying minimal partial realization algorithm based on twisting, Automatica, 35 (1999), pp. 1543-1548. · Zbl 0932.93014
[29] R. Bru, S. Romero, and E. Sánchez, Structural properties of positive periodic discrete-time linear systems: Canonical forms, Appl. Math. Comput., 153 (2004), pp. 697-719. · Zbl 1055.93013
[30] M. Kuijper and J. C. Willems, A behavioral framework for periodically time varying systems, in Proceedings of the 36th Annual IEEE Conference on Decision and Control, Vol. 3, 1997, pp. 2013-2016.
[31] D. Napp, M. van der Put, and S. Shankar, Periodic behaviors, SIAM J. Control Optim., 48 (2010), pp. 4652-4663, https://doi.org/10.1137/100782577. · Zbl 1213.93075
[32] J. C. Willems, Paradigms and puzzles in the theory of dynamical systems, IEEE Trans. Automat. Control, 36 (1991), pp. 259-294. · Zbl 0737.93004
[33] D. Napp, S. Shankar, and H. L. Trentelman, Regular implementation in the space of compactly supported functions, Systems Control Lett., 57 (2008), pp. 851-855. · Zbl 1162.93012
[34] E. Fornasini, D. Napp, R. Pereira, R. Pinto, and P. Rocha, State realizations of 2-periodic convolutional codes: A switching system approach, IFAC-PapersOnLine, 54 (2021), pp. 114-118. · Zbl 1501.94101
[35] J. Rosenthal and E. V. York, BCH convolutional codes, IEEE Trans. Automat. Control, 45 (1999), pp. 1833-1844. · Zbl 0958.94035
[36] E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional coding, Linear Algebra Appl., 392 (Supplement C) (2004), pp. 119-158. · Zbl 1060.94043
[37] H. Gluesing-Luerssen, J. Rosenthal, and R. Smarandache, Strongly MDS convolutional codes, IEEE Trans. Inform. Theory, 52 (2006), pp. 584-598. · Zbl 1309.94164
[38] R. J. McEliece, The algebraic theory of convolutional codes, in Handbook of Coding Theory, Vols. I and II, V. S. Pless and W. C. Huffman, eds., North-Holland, Amsterdam, 1998, pp. 1065-1138. · Zbl 0967.94020
[39] G. Solomon and H. C. A. van Tilborg, A connection between block and convolutional codes, SIAM J. Appl. Math., 37 (1979), pp. 358-369, https://doi.org/10.1137/0137027. · Zbl 0415.94008
[40] R. Hutchinson, The existence of strongly MDS convolutional codes, SIAM J. Control Optim., 47 (2008), pp. 2812-2826, https://doi.org/10.1137/050638977. · Zbl 1177.94196
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.