American Institute of Mathematical Sciences

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

Composition codes

Ettore Fornasini 1, , Telma Pinho 2, , Raquel Pinto 2, and  Paula Rocha 3,

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.
Keywords: Encoders and syndrome formers, 2D composition codes, minimal 2D state-space models..
Mathematics Subject Classification: Primary: 94B10, 93C35; Secondary: 93B25, 93B2.
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), Springer, 1975, 64-82. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

G. Forney, Convolutional Codes I: Algebraic structure, IEEE Trans. Inf. Theory, 16 (1970), 720-738. Correction, Ibid., 17 (1971), 360.  Google Scholar

[6]

G. Forney, Structural analysis of convolutional codes via dual codes, IEEE Trans. Inf. Theory, 19 (1973), 512-518.  Google Scholar

[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. 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-296. doi: 10.1109/TCS.1987.1086219.  Google Scholar

[9]

T. Pinho, Minimal State-Space Realizations of 2D Convolutional Codes, Ph.D thesis, Univ. Aveiro, Portugal, 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-250. doi: 10.1007/s10623-012-9768-1.  Google Scholar

[11]

P. Rocha, Representation of noncausal 2D systems, in New Trends in Systems Theory, Birkhäuser, 1991, 630-635.  Google Scholar

[12]

R. P. Roesser, A Discrete State-Space Model for Linear Image Processing, IEEE Trans. Automat. Control, 20 (1975), 1-10.  Google Scholar

[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.  Google Scholar

[14]

P. A. Weiner, Multidimensional Convolutional Codes, Ph.D thesis, Univ. Notre Dame, USA, 1998.  Google Scholar

[15]

J. C. Willems, Models for dynamics, in Dynamics Reported (eds. U. Kirchgraber and H.O. Walther), John Wiley Sons Ltd., 1989, 171-269.  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), Springer, 1975, 64-82. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

G. Forney, Convolutional Codes I: Algebraic structure, IEEE Trans. Inf. Theory, 16 (1970), 720-738. Correction, Ibid., 17 (1971), 360.  Google Scholar

[6]

G. Forney, Structural analysis of convolutional codes via dual codes, IEEE Trans. Inf. Theory, 19 (1973), 512-518.  Google Scholar

[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. 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-296. doi: 10.1109/TCS.1987.1086219.  Google Scholar

[9]

T. Pinho, Minimal State-Space Realizations of 2D Convolutional Codes, Ph.D thesis, Univ. Aveiro, Portugal, 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-250. doi: 10.1007/s10623-012-9768-1.  Google Scholar

[11]

P. Rocha, Representation of noncausal 2D systems, in New Trends in Systems Theory, Birkhäuser, 1991, 630-635.  Google Scholar

[12]

R. P. Roesser, A Discrete State-Space Model for Linear Image Processing, IEEE Trans. Automat. Control, 20 (1975), 1-10.  Google Scholar

[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.  Google Scholar

[14]

P. A. Weiner, Multidimensional Convolutional Codes, Ph.D thesis, Univ. Notre Dame, USA, 1998.  Google Scholar

[15]

J. C. Willems, Models for dynamics, in Dynamics Reported (eds. U. Kirchgraber and H.O. Walther), John Wiley Sons Ltd., 1989, 171-269.  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]

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 & 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 & 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 & 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 & 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 & 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 & 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 & 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]

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
[14]

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, 2006, 15 (3) : 777-809. doi: 10.3934/dcds.2006.15.777
[15]

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
[16]

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
[17]

Boling Guo, Yongqian Han, Guoli Zhou. Random attractor for the 2D stochastic nematic liquid crystals flows. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2349-2376. doi: 10.3934/cpaa.2019106
[18]

María J. Martín, Jukka Tuomela. 2D incompressible Euler equations: New explicit solutions. Discrete & Continuous Dynamical Systems, 2019, 39 (8) : 4547-4563. doi: 10.3934/dcds.2019187
[19]

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
[20]

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, 2013, 33 (9) : 4017-4040. doi: 10.3934/dcds.2013.33.4017

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (153)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences