# American Institute of Mathematical Sciences

February  2016, 10(1): 163-177. doi: 10.3934/amc.2016.10.163

## Composition codes

 1 Department of Information Engineering, University of Padua, Italy 2 CIDMA, Department of Mathematics, University of Aveiro, Portugal, Portugal 3 SYSTEC, Faculty of Engineering, University of Porto, Portugal

Received  December 2014 Revised  July 2015 Published  March 2016

In this paper we introduce a special class of 2D convolutional codes, called composition codes, which admit encoders $G(d_1,d_2)$ that can be decomposed as the product of two 1D encoders, i.e., $G(d_1,d_2)=G_2(d_2)G_1(d_1)$. Taking into account this decomposition, we obtain syndrome formers of the code directly from $G_1(d_1)$ and $G_2(d_2)$, in case $G_1(d_1)$ and $G_2(d_2)$ are right prime. Moreover we consider 2D state-space realizations by means of a separable Roesser model of the encoders and syndrome formers of a composition code and we investigate the minimality of such realizations. In particular, we obtain minimal realizations for composition codes which admit an encoder $G(d_1,d_2)=G_2(d_2)G_1(d_1)$ with $G_2(d_2)$ a systematic 1D encoder. Finally, we investigate the minimality of 2D separable Roesser state-space realizations for syndrome formers of these codes.
Citation: Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163
##### References:
 [1] S. Attasi, Systèmes linéaires homogènes à deux indices, in Rapport Laboria, 1973. [2] E. Fornasini and G. Marchesini, Algebraic realization theory of two-dimensional filters, in Variable Structure Systems with Application to Economics and Biology (eds. A. Ruberti and R. Mohler), Springer, 1975, 64-82. [3] E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional coding, Linear Algebra Appl., 392 (2004), 119-158. doi: 10.1016/j.laa.2004.06.007. [4] E. Fornasini and M. E. Valcher, Algebraic aspects of two-dimensional convolutional codes, IEEE Trans. Inf. Theory, 40 (1994), 1068-1082. doi: 10.1109/18.335967. [5] G. Forney, Convolutional Codes I: Algebraic structure, IEEE Trans. Inf. Theory, 16 (1970), 720-738. Correction, Ibid., 17 (1971), 360. [6] G. Forney, Structural analysis of convolutional codes via dual codes, IEEE Trans. Inf. Theory, 19 (1973), 512-518. [7] B. Levy, 2D Polynomial and Rational Matrices, and their Applications for the Modeling of 2-D Dynamical Systems, Ph.D thesis, Stanford University, USA, 1981. [8] T. Lin, M. Kawamata and T. Higuchi, Decomposition of 2-D separable-denominator systems: Existence, uniqueness, and applications, IEEE Trans. Circ. Syst., 34 (1987), 292-296. doi: 10.1109/TCS.1987.1086219. [9] T. Pinho, Minimal State-Space Realizations of 2D Convolutional Codes, Ph.D thesis, Univ. Aveiro, Portugal, 2014. [10] T. Pinho, R. Pinto and P. Rocha, Realization of 2D convolutional codes of rate $\frac1n$ by separable Roesser models, Des. Codes Crypt., 70 (2014), 241-250. doi: 10.1007/s10623-012-9768-1. [11] P. Rocha, Representation of noncausal 2D systems, in New Trends in Systems Theory, Birkhäuser, 1991, 630-635. [12] R. P. Roesser, A Discrete State-Space Model for Linear Image Processing, IEEE Trans. Automat. Control, 20 (1975), 1-10. [13] M. E. Valcher and E. Fornasini, On 2D finite support convolutional codes, Multidim. Syst. Signal Proc., 5 (1994), 231-243. doi: 10.1007/BF00980707. [14] P. A. Weiner, Multidimensional Convolutional Codes, Ph.D thesis, Univ. Notre Dame, USA, 1998. [15] J. C. Willems, Models for dynamics, in Dynamics Reported (eds. U. Kirchgraber and H.O. Walther), John Wiley Sons Ltd., 1989, 171-269.

show all references

##### References:
 [1] S. Attasi, Systèmes linéaires homogènes à deux indices, in Rapport Laboria, 1973. [2] E. Fornasini and G. Marchesini, Algebraic realization theory of two-dimensional filters, in Variable Structure Systems with Application to Economics and Biology (eds. A. Ruberti and R. Mohler), Springer, 1975, 64-82. [3] E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional coding, Linear Algebra Appl., 392 (2004), 119-158. doi: 10.1016/j.laa.2004.06.007. [4] E. Fornasini and M. E. Valcher, Algebraic aspects of two-dimensional convolutional codes, IEEE Trans. Inf. Theory, 40 (1994), 1068-1082. doi: 10.1109/18.335967. [5] G. Forney, Convolutional Codes I: Algebraic structure, IEEE Trans. Inf. Theory, 16 (1970), 720-738. Correction, Ibid., 17 (1971), 360. [6] G. Forney, Structural analysis of convolutional codes via dual codes, IEEE Trans. Inf. Theory, 19 (1973), 512-518. [7] B. Levy, 2D Polynomial and Rational Matrices, and their Applications for the Modeling of 2-D Dynamical Systems, Ph.D thesis, Stanford University, USA, 1981. [8] T. Lin, M. Kawamata and T. Higuchi, Decomposition of 2-D separable-denominator systems: Existence, uniqueness, and applications, IEEE Trans. Circ. Syst., 34 (1987), 292-296. doi: 10.1109/TCS.1987.1086219. [9] T. Pinho, Minimal State-Space Realizations of 2D Convolutional Codes, Ph.D thesis, Univ. Aveiro, Portugal, 2014. [10] T. Pinho, R. Pinto and P. Rocha, Realization of 2D convolutional codes of rate $\frac1n$ by separable Roesser models, Des. Codes Crypt., 70 (2014), 241-250. doi: 10.1007/s10623-012-9768-1. [11] P. Rocha, Representation of noncausal 2D systems, in New Trends in Systems Theory, Birkhäuser, 1991, 630-635. [12] R. P. Roesser, A Discrete State-Space Model for Linear Image Processing, IEEE Trans. Automat. Control, 20 (1975), 1-10. [13] M. E. Valcher and E. Fornasini, On 2D finite support convolutional codes, Multidim. Syst. Signal Proc., 5 (1994), 231-243. doi: 10.1007/BF00980707. [14] P. A. Weiner, Multidimensional Convolutional Codes, Ph.D thesis, Univ. Notre Dame, USA, 1998. [15] J. C. Willems, Models for dynamics, in Dynamics Reported (eds. U. Kirchgraber and H.O. Walther), John Wiley Sons Ltd., 1989, 171-269.
 [1] Géry de Saxcé, Claude Vallée. Structure of the space of 2D elasticity tensors. Discrete and Continuous Dynamical Systems - S, 2013, 6 (6) : 1525-1537. doi: 10.3934/dcdss.2013.6.1525 [2] Diego Napp, Carmen Perea, Raquel Pinto. Input-state-output representations and constructions of finite support 2D convolutional codes. Advances in Mathematics of Communications, 2010, 4 (4) : 533-545. doi: 10.3934/amc.2010.4.533 [3] Jintao Li, Jindou Shen, Gang Xu. The global supersonic flow with vacuum state in a 2D convex duct. Electronic Research Archive, 2021, 29 (2) : 2077-2099. doi: 10.3934/era.2020106 [4] Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031 [5] Gianluca Crippa, Elizaveta Semenova, Stefano Spirito. Strong continuity for the 2D Euler equations. Kinetic and Related Models, 2015, 8 (4) : 685-689. doi: 10.3934/krm.2015.8.685 [6] Bernd Kawohl, Guido Sweers. On a formula for sets of constant width in 2d. Communications on Pure and Applied Analysis, 2019, 18 (4) : 2117-2131. doi: 10.3934/cpaa.2019095 [7] Ka Kit Tung, Wendell Welch Orlando. On the differences between 2D and QG turbulence. Discrete and Continuous Dynamical Systems - B, 2003, 3 (2) : 145-162. doi: 10.3934/dcdsb.2003.3.145 [8] Julien Cividini. Pattern formation in 2D traffic flows. Discrete and Continuous Dynamical Systems - S, 2014, 7 (3) : 395-409. doi: 10.3934/dcdss.2014.7.395 [9] Igor Kukavica, Amjad Tuffaha. On the 2D free boundary Euler equation. Evolution Equations and Control Theory, 2012, 1 (2) : 297-314. doi: 10.3934/eect.2012.1.297 [10] Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems and Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022 [11] Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems and Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591 [12] Henri Schurz. Stochastic heat equations with cubic nonlinearity and additive space-time noise in 2D. Conference Publications, 2013, 2013 (special) : 673-684. doi: 10.3934/proc.2013.2013.673 [13] Aiting Le, Chenyin Qian. Smoothing effect and well-posedness for 2D Boussinesq equations in critical Sobolev space. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022057 [14] Hakima Bessaih, Benedetta Ferrario. Statistical properties of stochastic 2D Navier-Stokes equations from linear models. Discrete and Continuous Dynamical Systems - B, 2016, 21 (9) : 2927-2947. doi: 10.3934/dcdsb.2016080 [15] Igor Chueshov, Irena Lasiecka. Existence, uniqueness of weak solutions and global attractors for a class of nonlinear 2D Kirchhoff-Boussinesq models. Discrete and Continuous Dynamical Systems, 2006, 15 (3) : 777-809. doi: 10.3934/dcds.2006.15.777 [16] Abdelwahab Bensouilah, Van Duong Dinh, Mohamed Majdoub. Scattering in the weighted $L^2$-space for a 2D nonlinear Schrödinger equation with inhomogeneous exponential nonlinearity. Communications on Pure and Applied Analysis, 2019, 18 (5) : 2735-2755. doi: 10.3934/cpaa.2019122 [17] Brian Ryals, Robert J. Sacker. Global stability in the 2D Ricker equation revisited. Discrete and Continuous Dynamical Systems - B, 2017, 22 (2) : 585-604. doi: 10.3934/dcdsb.2017028 [18] Boling Guo, Yongqian Han, Guoli Zhou. Random attractor for the 2D stochastic nematic liquid crystals flows. Communications on Pure and Applied Analysis, 2019, 18 (5) : 2349-2376. doi: 10.3934/cpaa.2019106 [19] María J. Martín, Jukka Tuomela. 2D incompressible Euler equations: New explicit solutions. Discrete and Continuous Dynamical Systems, 2019, 39 (8) : 4547-4563. doi: 10.3934/dcds.2019187 [20] Leonardo Kosloff, Tomas Schonbek. Existence and decay of solutions of the 2D QG equation in the presence of an obstacle. Discrete and Continuous Dynamical Systems - S, 2014, 7 (5) : 1025-1043. doi: 10.3934/dcdss.2014.7.1025

2020 Impact Factor: 0.935