On the structure of linear recurrent error-control codes
ESAIM: Control, Optimisation and Calculus of Variations, Tome 8 (2002) , pp. 703-713.

We are extending to linear recurrent codes, i.e., to time-varying convolutional codes, most of the classic structural properties of fixed convolutional codes. We are also proposing a new connection between fixed convolutional codes and linear block codes. These results are obtained thanks to a module-theoretic framework which has been previously developed for linear control.

DOI : https://doi.org/10.1051/cocv:2002035
Classification : 93C65,  94B05,  94B10,  12H05,  13A02,  13C05
Mots clés : convolutional codes, linear recurrent codes, block codes, transducers, encoders, feedback decoding, linear systems, controllability, observability, input-output inversion, modules 
@article{COCV_2002__8__703_0,
     author = {Fliess, Michel},
     title = {On the structure of linear recurrent error-control codes},
     journal = {ESAIM: Control, Optimisation and Calculus of Variations},
     pages = {703--713},
     publisher = {EDP-Sciences},
     volume = {8},
     year = {2002},
     doi = {10.1051/cocv:2002035},
     zbl = {1070.94026},
     mrnumber = {1932969},
     language = {en},
     url = {http://www.numdam.org/item/COCV_2002__8__703_0/}
}
Fliess, Michel. On the structure of linear recurrent error-control codes. ESAIM: Control, Optimisation and Calculus of Variations, Tome 8 (2002) , pp. 703-713. doi : 10.1051/cocv:2002035. http://www.numdam.org/item/COCV_2002__8__703_0/

[1] C. Berrou and A. Glavieux, Near-optimum error-correcting coding and decoding: Turbo-codes. IEEE Trans. Communicat. 44 (1996) 1261-1271.

[2] R.E. Blahut, Theory and Practice of Error Control Codes. Addison-Wesley (1983). | MR 698946 | Zbl 0569.94012

[3] N. Bourbaki, Algèbre, Chap. 2. Hermann (1970). | MR 274237

[4] G. Cohen, J.-L. Dornstetter and P. Godlewski, Codes correcteurs d'erreurs. Masson (1992).

[5] R.M. Cohn, Difference Algebra. Interscience (1965). | MR 205987 | Zbl 0127.26402

[6] A. Dholakia, Introduction to Convolutional Codes with Applications. Kluwer (1994). | Zbl 0826.94001

[7] F. Fagnani and S. Zampieri, System-theoretic properties of convolutional codes over rings. IEEE Trans. Inform. Theory 47 (2001) 2256-2274. | MR 1873201 | Zbl 1028.94033

[8] M. Fliess, Automatique en temps discret et algèbre aux différences. Forum Math. 2 (1990) 213-232. | MR 1050406 | Zbl 0706.93039

[9] M. Fliess, Some basic structural properties of generalized linear systems. Systems Control Lett. 15 (1990) 391-396. | MR 1084580 | Zbl 0727.93024

[10] M. Fliess, A remark on Willems' trajectory characterization of linear controllability. Systems Control Lett. 19 (1992) 43-45. | Zbl 0765.93003

[11] M. Fliess, Reversible linear and nonlinear discrete-time dynamics. IEEE Trans. Automat. Control 37 (1992) 1144-1153. | MR 1178584 | Zbl 0764.93058

[12] M. Fliess, Une interprétation algébrique de la transformation de Laplace et des matrices de transfert. Linear Algebra Appl. 203-204 (1994) 429-442. | MR 1275520 | Zbl 0802.93010

[13] M. Fliess, Variations sur la notion de contrôlabilité, in Journée Soc. Math. France. Paris (2000) 47-86. | MR 1799559 | Zbl 0992.93002

[14] M. Fliess and H. Bourlès, Discussing some examples of linear system interconnections. Systems Control Lett. 27 (1996) 1-7. | MR 1375906 | Zbl 0877.93064

[15] M. Fliess, J. Lévine, P. Martin and P. Rouchon, Flatness and defect of non-linear systems: Introductory theory and applications. Internat. J. Control 61 (1995) 1327-1361. | MR 1613557 | Zbl 0838.93022

[16] M. Fliess and R. Marquez, Continuous-time linear predictive control and flatness: A module-theoretic setting with examples. Internat. J. Control 73 (2000) 606-623. | MR 1768024 | Zbl 1006.93508

[17] M. Fliess and R. Marquez, Une approche intrinsèque de la commande prédictive linéaire discrète. APII J. Europ. Syst. Automat. 35 (2001) 127-147.

[18] M. Fliess, R. Marquez, E. Delaleau and H. Sira-Ramírez, Correcteurs proportionnels-intégraux généralisés. ESAIM: COCV 7 (2002) 23-41. | Numdam | Zbl 1037.93040

[19] M. Fliess, R. Marquez and H. Mounier, An extension of predictive control, PID regulators and Smith predictors to some linear delay systems. Internat. J. Control (to appear). | MR 1916231 | Zbl 1021.93015

[20] M. Fliess and H. Mounier, Controllability and observability of linear delay systems: An algebraic approach. ESAIM: COCV 3 (1998) 301-314. | Numdam | MR 1644427 | Zbl 0908.93013

[21] G.D. Forney Jr., Convolutional codes I: Algebraic structure. IEEE Trans. Inform. Theory 16 (1970) 720-738. | MR 275988 | Zbl 0205.20702

[22] G.D. Forney Jr., Minimal bases of rational vector spaces, with applications to multivariable linear systems. SIAM J. Control 13 (1975) 493-520. | MR 378886 | Zbl 0269.93011

[23] G.D. Forney Jr., Algebraic structure of convolutional codes and algebraic system theory, in Mathematical System Theory - The Influence of R.E. Kalman, edited by A.C. Antoulas. Springer (1991) 527-557. | Zbl 0751.94011

[24] G.D. Forney Jr. and M.D. Trott, The dynamics of group codes: State-space, trellis diagrams and canonical encoders. IEEE Trans. Inform. Theory 39 (1993) 1491-1513. | MR 1281706 | Zbl 0801.94015

[25] G.D. Forney Jr., B. Marcus, N.T. Sindhushayana and M. Trott, A multilingual dictionary: System theory, coding theory, symbolic dynamics and automata theory, in Different Aspects of Coding Theory. Proc. Symp. Appl. Math. 50; Amer. Math. Soc. (1995) 109-138. | MR 1368638 | Zbl 0845.58024

[26] R. Johannesson and K. Sh. Zigangirov, Fundamentals of Convolutional Coding. IEEE Press (1999). | MR 1768537 | Zbl 0964.94024

[27] T. Kailath, Linear Systems. Prentice-Hall (1979). | MR 569473 | Zbl 0454.93001

[28] E.W. Kamen, P.P. Khargonekar and K.R. Poola, A transfer-function approach to linear time-varying discrete-time systems. SIAM J. Control Optim. 23 (1985) 550-565. | MR 791887 | Zbl 0626.93039

[29] T.Y. Lam, Lectures on Rings and Modules. Springer (1999). | MR 1653294

[30] S. Lin and D.J. Costello Jr., Error Control Coding: Fundamentals and Applications. Prentice-Hall (1983).

[31] J.H. Van Lint, Introduction to Coding Theory, 3 rd Edition. Springer (1999). | MR 1664228 | Zbl 0936.94014

[32] H.-A. Loeliger, G.D. Forney Jr., T. Mittelholzer and M.D. Trott, Minimality and observability of group systems. Linear Algebra Appl. 205-206 (1994) 937-963. | MR 1276847 | Zbl 0813.93046

[33] J.L. Massey and M.K. Sain, Codes, automata and contnuous systems: Explicit interconnections. IEEE Trans. Automat. Control 12 (1967) 644-650.

[34] R.J. Mceliece, The algebraic theory of convolutional codes, in Handbook of Coding Theory, Vol. 1, edited by V. Pless and W.C. Huffman. Elsevier (1998) 1065-1138. | MR 1667948 | Zbl 0967.94020

[35] J.C. Mcconnel and J.C. Robson, Noncommutative Noetherian Rings. Wiley (1987). | MR 934572 | Zbl 0644.16008

[36] H. Mounier, P. Rouchon and J. Rudolph, Some examples of linear systems with delays. APII J. Europ. Syst. Automat. 31 (1997) 911-925.

[37] P. Piret, Convolutional Codes, an Algebraic Approach. MIT Press (1988). | MR 959540 | Zbl 0986.94510

[38] J. Rosenthal, Connections between linear systems and convolutional codes, in Codes, Systems and Graphical Models, edited by B. Marcus and J. Rosenthal. Springer (2000) 39-66. | MR 1861952 | Zbl 0993.94559

[39] J. Rosenthal, J.M. Schumacher and E.V. York, On behaviors and convolutional codes. IEEE Trans. Informat. Theory 42 (1996) 1881-1891. | MR 1465746 | Zbl 0876.94042

[40] J. Rosenthal and E.V. York, BCH convolutional codes. IEEE Trans. Inform. Theory 45 (1999) 1833-1844. | MR 1720637 | Zbl 0958.94035

[41] J. Rotman, An Introduction to Homological Algebra. Academic Press (1979). | MR 538169 | Zbl 0441.18018

[42] A.J. Viterbi and J.K. Omura, Principles of Digital Communication and Coding. McGraw-Hill (1979). | Zbl 0495.94002

[43] L. Weiss, Controllability, realization and stability of discrete-time systems. SIAM J. Control 10 (1972) 230-251. | MR 392092 | Zbl 0238.93007

[44] J.C. Willems, Paradigms and puzzles in the theory of dynamical systems. IEEE Trans. Automat. Control 36 (1991) 259-294. | MR 1092818 | Zbl 0737.93004

[45] G. Zémor, Cours de cryptographie. Cassini (2000). | Zbl 0978.94040