Realization of 2D (2,2)-periodic encoders by means of 2D periodic separable Roesser models

Napp, Diego ; Pereira, Ricardo ; Pinto, Raquel ; Rocha, Paula

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 3, pp. 527-539.

Résumé

It is well known that convolutional codes are linear systems when they are defined over a finite field. A fundamental issue in the implementation of convolutional codes is to obtain a minimal state representation of the code. Compared with the literature on one-dimensional (1D) time-invariant convolutional codes, there exist relatively few results on the realization problem for time-varying 1D convolutional codes and even fewer if the convolutional codes are two-dimensional (2D). In this paper we consider 2D periodic convolutional codes and address the minimal state space realization problem for this class of codes. This is, in general, a highly nontrivial problem. Here, we focus on separable Roesser models and show that in this case it is possible to derive, under weak conditions, concrete formulas for obtaining a 2D Roesser state space representation. Moreover, we study minimality and present necessary conditions for these representations to be minimal. Our results immediately lead to constructive algorithms to build these representations.

Détail

Keywords: periodic 2D system, convolutional codes, realization problems
Mots-clés : układ dwuwymiarowy, kod splotowy, problem realizacji

Bibliographie

[1] Aleixo, J.C. and Rocha, P. (2017). Roesser model representation of 2D periodic behaviors: The (2,2)-periodic SISO case, 10th International Workshop on Multidimensional (nD) Systems (nDS), Zielona Góra, Poland, pp. 1–6.

[2] Aleixo, J.C. and Rocha, P. (2018). On the state space realization of separable periodic 2D systems, 2018 European Control Conference, Limassol, Cyprus, pp. 2300–2305.

[3] Aleixo, J.C., Rocha, P. and Willems, J.C. (2011). State space representation of SISOperiodic behaviors, 2011 50th IEEE Conference on Decision and Control/European Control Conference, Orlando, FL, USA, pp. 1545–1550.

[4] Basu, S. and Swamy, M.N.S. (2002). Editorial preface to special issue on multidimensional signals and systems, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 49(6): 709–714.

[5] Charoenlarpnopparut, C. and Bose, N. (2001). Grobner bases for problem solving in multidimensional systems, Multidimensional Systems and Signal Processing 12(3): 365–376.

[6] Climent, J.-J., Herranz, V., Perea, C. and Tomás, V. (2009). A systems theory approach to periodically time-varying convolutional codes by means of their invariant equivalent, in M. Bras-Amorós and T. Høholdt (Eds), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, Berlin/Heidelberg, pp. 73–82.

[7] Costello, D.J. (1974). Free distance bounds for convolutional codes, IEEE Transactions on Information Theory 20(3): 356–365.

[8] Felstrom, A.J. and Zigangirov, K.S. (1999). Time-varying periodic convolutional codes with low-density parity-check matrix, IEEE Transactions on Information Theory 45(6): 2181–2191.

[9] Fornasini, E., Pinho, T., Pinto, R. and Rocha, P. (2015). Minimal realizations of syndrome formers of a special class of 2D codes, in R. Pinto et al. (Eds), Coding Theory and Applications, Springer International Publishing, Cham, pp. 185–193.

[10] Fornasini, E. and Pinto, R. (2004). Matrix fraction descriptions in convolutional coding, Linear Algebra and Its Applications 392(C): 119–158.

[11] Fornasini, E. and Valcher, M. (1994). Algebraic aspects of two-dimensional convolutional codes, IEEE Transactions on Information Theory 40(4): 1068–1082.

[12] Fornasini, E. and Valcher, M. (1998). Multidimensional systems with finite support behaviors: Signal structure, generation and detection, SIAM Journal on Control and Optimization 36(2): 760–779.

[13] Galkowski, K. (1996). The Fornasini–Marchesini and the Roesser models: Algebraic methods for recasting, IEEE Transactions on Automatic Control 41(1): 107–112.

[14] Galkowski, K. (2001). State-Space Realisations of Linear 2-D Systems with Extensions to the General nD (n > 2) Case, Vol. 263, Lecture Notes in Control and Information Sciences, Springer, London.

[15] Gluesing-Luersen, H., Rosenthal, J. and Weiner, P. (2000). Duality between mutidimensinal convolutional codes and systems, in F. Colonius et al. (Eds), Advances in Mathematical Systems Theory: A Volume in Honor of Diedrich Hinrichsen, Birkhauser, Boston, MA, pp. 135–150.

[16] Gluesing-Luerssen, H. and Schneider, G. (2007). State space realizations and monomial equivalence for convolutional codes, Linear Algebra and Its Applications 425(2): 518–533.

[17] Guardia, G.G.L. (2019). Asymptotically good convolutional codes, Linear and Multilinear Algebra 67(7): 1483–1494.

[18] Hinamoto, T. (1980). Realizations of a state-space model from two-dimensional input-output map, IEEE Transactions on Circuits and Systems 27(1): 36–44.

[19] Jangisarakul, P. and Charoenlarpnopparut, C. (2011). Algebraic decoder of multidimensional convolutional code: Constructive algorithms for determining syndrome decoder and decoder matrix based on Grobner basis, Multidimensional Systems and Signal Processing 22(1): 67–81.

[20] Kaczorek, T. (2001). Elimination of finite eigenvalues of the 2D Roesser model by state feedbacks, International Journal of Applied Mathematics and Computer Science 11(2): 369–376.

[21] Kailath, T. (1980). Linear Systems, Prentice-Hall, Englewood Cliffs, NJ.

[22] Kuijper, M. and Polderman, J. (2004). Reed–Solomon list decoding from a system theoretic perspective, IEEE Transactions on Information Theory IT-50(2): 259–271.

[23] Kuijper, M. and Willems, J.C. (1997). A behavioral framework for periodically time varying systems, Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, USA, Vol. 3, pp. 2013–2016.

[24] Lobo, R., Bitzer, D.L. and Vouk, M.A. (2012). On locally invertible encoders and multidimensional convolutional codes, IEEE Transactions on Information Theory 58(3): 1774–1782.

[25] Mooser, M. (1983). Some periodic convolutional codes better than any fixed code (corresp.), IEEE Transactions on Information Theory 29(5): 750–751.

[26] Napp, D., Perea, C. and Pinto, R. (2010). Input-state-output representations and constructions of finite support 2D convolutional codes, Advances in Mathematics of Communications 4(4): 533–545.

[27] Napp, D., Pereira, R., Pinto, R. and Rocha, P. (2019). Periodic state-space representations of periodic convolutional codes, Cryptography and Communications 11(4): 585–595.

[28] Palazzo, R. (1993). A time-varying convolutional encoder better than the best time-invariant encoder, IEEE Transactions on Information Theory 39(3): 1109–1110.

[29] Pinho, T. (2016). Minimal State-Space Realizations of 2D Convolutional Codes, PhD thesis, University of Aveiro, Aveiro.

[30] Pinho, T., Pinto, R. and Rocha, P. (2014). Realization of 2D convolutional codes of rate 1/n by separable Roesser models, Designs, Codes and Cryptography 70(1): 241–250.

[31] Rosenthal, J. (2001). Connections between linear systems and convolutional codes, in B. Marcus and J. Rosenthal (Eds), Codes, Systems and Graphical Models, Springer-Verlag, New York, NY, pp. 39–66.

[32] Rosenthal, J. and York, E.V. (1999). BCH convolutional codes, IEEE Transactions on Automatic Control 45(6): 1833–1844.

[33] Valcher, M. and Fornasini, E. (1994). On 2D finite support convolutional codes: An algebraic approach, Multidimensional Systems and Signal Processing 5(3): 231–243.

[34] Weiner, P. (1998). Multidimensional Convolutional Codes, PhD dissertation, University of Notre Dame, South Bend, IN.

[35] Zerz, E. (2000). Topics in Multidimensional Linear Systems Theory, Lecture Notes in Control and Information Sciences, Vol. 256, Springer-Verlag, London.