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

Metrics

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

[Back to Top]