On the structure of linear recurrent error-control codes

Fliess, Michel

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.

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

[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 | Zbl

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

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

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

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

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

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

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

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

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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

[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 | Zbl

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

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

[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 | Zbl

[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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

[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^{\mathrm{rd}}$ Edition. Springer (1999). | MR | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

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

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

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

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

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