# 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).   Google Scholar [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), (1975), 64.   Google Scholar [3] E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional coding,, Linear Algebra Appl., 392 (2004), 119.  doi: 10.1016/j.laa.2004.06.007.  Google Scholar [4] E. Fornasini and M. E. Valcher, Algebraic aspects of two-dimensional convolutional codes,, IEEE Trans. Inf. Theory, 40 (1994), 1068.  doi: 10.1109/18.335967.  Google Scholar [5] G. Forney, Convolutional Codes I: Algebraic structure,, IEEE Trans. Inf. Theory, 16 (1970), 720.   Google Scholar [6] G. Forney, Structural analysis of convolutional codes via dual codes,, IEEE Trans. Inf. Theory, 19 (1973), 512.   Google Scholar [7] B. Levy, 2D Polynomial and Rational Matrices, and their Applications for the Modeling of 2-D Dynamical Systems,, Ph.D thesis, (1981).   Google Scholar [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.  doi: 10.1109/TCS.1987.1086219.  Google Scholar [9] T. Pinho, Minimal State-Space Realizations of 2D Convolutional Codes,, Ph.D thesis, (2014).   Google Scholar [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.  doi: 10.1007/s10623-012-9768-1.  Google Scholar [11] P. Rocha, Representation of noncausal 2D systems,, in New Trends in Systems Theory, (1991), 630.   Google Scholar [12] R. P. Roesser, A Discrete State-Space Model for Linear Image Processing,, IEEE Trans. Automat. Control, 20 (1975), 1.   Google Scholar [13] M. E. Valcher and E. Fornasini, On 2D finite support convolutional codes,, Multidim. Syst. Signal Proc., 5 (1994), 231.  doi: 10.1007/BF00980707.  Google Scholar [14] P. A. Weiner, Multidimensional Convolutional Codes,, Ph.D thesis, (1998).   Google Scholar [15] J. C. Willems, Models for dynamics,, in Dynamics Reported (eds. U. Kirchgraber and H.O. Walther), (1989), 171.   Google Scholar

show all references

##### References:
 [1] S. Attasi, Systèmes linéaires homogènes à deux indices,, in Rapport Laboria, (1973).   Google Scholar [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), (1975), 64.   Google Scholar [3] E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional coding,, Linear Algebra Appl., 392 (2004), 119.  doi: 10.1016/j.laa.2004.06.007.  Google Scholar [4] E. Fornasini and M. E. Valcher, Algebraic aspects of two-dimensional convolutional codes,, IEEE Trans. Inf. Theory, 40 (1994), 1068.  doi: 10.1109/18.335967.  Google Scholar [5] G. Forney, Convolutional Codes I: Algebraic structure,, IEEE Trans. Inf. Theory, 16 (1970), 720.   Google Scholar [6] G. Forney, Structural analysis of convolutional codes via dual codes,, IEEE Trans. Inf. Theory, 19 (1973), 512.   Google Scholar [7] B. Levy, 2D Polynomial and Rational Matrices, and their Applications for the Modeling of 2-D Dynamical Systems,, Ph.D thesis, (1981).   Google Scholar [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.  doi: 10.1109/TCS.1987.1086219.  Google Scholar [9] T. Pinho, Minimal State-Space Realizations of 2D Convolutional Codes,, Ph.D thesis, (2014).   Google Scholar [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.  doi: 10.1007/s10623-012-9768-1.  Google Scholar [11] P. Rocha, Representation of noncausal 2D systems,, in New Trends in Systems Theory, (1991), 630.   Google Scholar [12] R. P. Roesser, A Discrete State-Space Model for Linear Image Processing,, IEEE Trans. Automat. Control, 20 (1975), 1.   Google Scholar [13] M. E. Valcher and E. Fornasini, On 2D finite support convolutional codes,, Multidim. Syst. Signal Proc., 5 (1994), 231.  doi: 10.1007/BF00980707.  Google Scholar [14] P. A. Weiner, Multidimensional Convolutional Codes,, Ph.D thesis, (1998).   Google Scholar [15] J. C. Willems, Models for dynamics,, in Dynamics Reported (eds. U. Kirchgraber and H.O. Walther), (1989), 171.   Google Scholar
 [1] Géry de Saxcé, Claude Vallée. Structure of the space of 2D elasticity tensors. Discrete & 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] Gianluca Crippa, Elizaveta Semenova, Stefano Spirito. Strong continuity for the 2D Euler equations. Kinetic & Related Models, 2015, 8 (4) : 685-689. doi: 10.3934/krm.2015.8.685 [4] Ka Kit Tung, Wendell Welch Orlando. On the differences between 2D and QG turbulence. Discrete & Continuous Dynamical Systems - B, 2003, 3 (2) : 145-162. doi: 10.3934/dcdsb.2003.3.145 [5] Julien Cividini. Pattern formation in 2D traffic flows. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 395-409. doi: 10.3934/dcdss.2014.7.395 [6] Igor Kukavica, Amjad Tuffaha. On the 2D free boundary Euler equation. Evolution Equations & Control Theory, 2012, 1 (2) : 297-314. doi: 10.3934/eect.2012.1.297 [7] Bernd Kawohl, Guido Sweers. On a formula for sets of constant width in 2d. Communications on Pure & Applied Analysis, 2019, 18 (4) : 2117-2131. doi: 10.3934/cpaa.2019095 [8] Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022 [9] Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591 [10] 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 [11] Hakima Bessaih, Benedetta Ferrario. Statistical properties of stochastic 2D Navier-Stokes equations from linear models. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 2927-2947. doi: 10.3934/dcdsb.2016080 [12] Igor Chueshov, Irena Lasiecka. Existence, uniqueness of weak solutions and global attractors for a class of nonlinear 2D Kirchhoff-Boussinesq models. Discrete & Continuous Dynamical Systems - A, 2006, 15 (3) : 777-809. doi: 10.3934/dcds.2006.15.777 [13] 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 & Applied Analysis, 2019, 18 (5) : 2735-2755. doi: 10.3934/cpaa.2019122 [14] Brian Ryals, Robert J. Sacker. Global stability in the 2D Ricker equation revisited. Discrete & Continuous Dynamical Systems - B, 2017, 22 (2) : 585-604. doi: 10.3934/dcdsb.2017028 [15] Leonardo Kosloff, Tomas Schonbek. Existence and decay of solutions of the 2D QG equation in the presence of an obstacle. Discrete & Continuous Dynamical Systems - S, 2014, 7 (5) : 1025-1043. doi: 10.3934/dcdss.2014.7.1025 [16] Yuri N. Fedorov, Luis C. García-Naranjo, Joris Vankerschaver. The motion of the 2D hydrodynamic Chaplygin sleigh in the presence of circulation. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 4017-4040. doi: 10.3934/dcds.2013.33.4017 [17] Makram Hamouda, Chang-Yeol Jung, Roger Temam. Boundary layers for the 2D linearized primitive equations. Communications on Pure & Applied Analysis, 2009, 8 (1) : 335-359. doi: 10.3934/cpaa.2009.8.335 [18] A. Rousseau, Roger Temam, J. Tribbia. Boundary conditions for the 2D linearized PEs of the ocean in the absence of viscosity. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1257-1276. doi: 10.3934/dcds.2005.13.1257 [19] Tetsu Mizumachi. Instability of bound states for 2D nonlinear Schrödinger equations. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 413-428. doi: 10.3934/dcds.2005.13.413 [20] Tian Ma, Shouhong Wang. Structure of 2D incompressible flows with the Dirichlet boundary conditions. Discrete & Continuous Dynamical Systems - B, 2001, 1 (1) : 29-41. doi: 10.3934/dcdsb.2001.1.29

2018 Impact Factor: 0.879