American Institute of Mathematical Sciences

Advanced
February  2016, 10(1): 179-193. doi: 10.3934/amc.2016.10.179

Decoding of $2$D convolutional codes over an erasure channel

Joan-Josep Climent 1, , Diego Napp 2, , Raquel Pinto 2, and  Rita Simões 2,

1. 

Departament de Matemàtiques, Universitat d'Alacant, Ap. Correus 99, E-03080, Alacant
2. 

CIDMA - Center for Research and Development in Mathematics and Applications, Department of Mathematics, University of Aveiro, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal, Portugal, Portugal

Received  December 2014 Revised  September 2015 Published  March 2016

In this paper we address the problem of decoding $2$D convolutional codes over an erasure channel. To this end we introduce the notion of neighbors around a set of erasures which can be considered an analogue of the notion of sliding window in the context of $1$D convolutional codes. The main idea is to reduce the decoding problem of $2$D convolutional codes to a problem of decoding a set of associated $1$D convolutional codes. We first show how to recover sets of erasures that are distributed on vertical, horizontal and diagonal lines. Finally we outline some ideas to treat any set of erasures distributed randomly on the $2$D plane.
Keywords: $2$D finite support convolutional codes, $1$D finite support convolutional codes, erasure channel..
Mathematics Subject Classification: Primary: 94B10; Secondary: 94B2.
Citation: Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179
References:
[1]

P. Almeida, D. Napp and R. Pinto, A new class of superregular matrices and MDP convolutional codes, Linear Algebra Appl., 439 (2013), 2145-2157. doi: 10.1016/j.laa.2013.06.013.  Google Scholar

[2]

M. Arai, A. Yamamoto, A. Yamaguchi, S. Fukumoto and K. Iwasaki, Analysis of using convolutional codes to recover packet losses over burst erasure channels, in Proc. 2001 Pacific Rim Int. Symp. Depend. Comp., IEEE, Seoul, 2001, 258-265. doi: 10.1109/PRDC.2001.992706.  Google Scholar

[3]

J. J. Climent, D. Napp, C. Perea and R. Pinto, A construction of MDS 2D convolutional codes of rate 1/n based on superregular matrices, Linear Algebra Appl., 437 (2012), 766-780. doi: 10.1016/j.laa.2012.02.032.  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]

E. Fornasini and M. E. Valcher, On 2D finite support convolutional codes: an algebraic approach, Multidim. Syst. Signal Proc., 5 (1994), 231-243. doi: 10.1007/BF00980707.  Google Scholar

[6]

E. Fornasini and M. E. Valcher, nD polynomial matrices with applications to multidimensional signal analysis, Multidim. Syst. Signal Proc., 8 (1997), 387-407. doi: 10.1023/A:1008256224288.  Google Scholar

[7]

H. Gluesing-Luerssen, J. Rosenthal and R. Smarandache, Strongly MDS convolutional codes, IEEE Trans. Inf. Theory, 52 (2006), 584-598. doi: 10.1109/TIT.2005.862100.  Google Scholar

[8]

H. Gluesing-Luerssen, J. Rosenthal and P. Weiner, Duality between multidimensional convolutional codes and systems, in Advances in Mathematical Systems Theory (eds. F. Colonius, U. Helmke, F. Wirth and D. Praetzel-Wolters), Birkhauser, 2000, 135-150. doi: 10.1007/978-1-4612-0179-3_8.  Google Scholar

[9]

R. Hutchinson, The existence of strongly MDS convolutional codes, SIAM J. Control Opt., 47 (2008), 2812-2826. doi: 10.1137/050638977.  Google Scholar

[10]

R. Hutchinson, J. Rosenthal and R. Smarandache, Convolutional codes with maximum distance profile, Syst. Control Lett., 54 (2005), 53-63. doi: 10.1016/j.sysconle.2004.06.005.  Google Scholar

[11]

R. Hutchinson, R. Smarandache and J. Trumpf, On superregular matrices and MDP convolutional codes, Linear Algebra Appl., 428 (2008), 2585-2596. doi: 10.1016/j.laa.2008.02.011.  Google Scholar

[12]

P. Jangisarakul and C. Charoenlarpnopparut, Algebraic decoder of multidimensional convolutional code: Constructive algorithms for determining syndrome decoder and decoder matrix based on Gröbner basis, Multidim. Syst. Signal Proc., 22 (2011), 67-81. doi: 10.1007/s11045-010-0139-7.  Google Scholar

[13]

D. Napp, C. Perea and R. Pinto, Input-state-output representations and constructions of finite support 2D convolutional codes, Adv. Math. Commun., 4 (2010), 533-545. doi: 10.3934/amc.2010.4.533.  Google Scholar

[14]

V. Tomás, Complete-MDP Convolutional Codes over the Erasure Channel, Ph.D thesis, Univ. Alicante, Alicante, Spain, 2010. Google Scholar

[15]

V. Tomás, J. Rosenthal and R. Smarandache, Reverse-maximum distance profile convolutional codes over the erasure channel, in Proc.19th Int. Symp. Math. Theory Netw. Syst. (ed. A. Edelmayer), 2010, 2121-2127. doi: 10.5167/uzh-44714.  Google Scholar

[16]

V. Tomás, J. Rosenthal and R. Smarandache, Decoding of convolutional codes over the erasure channel, IEEE Trans. Inf. Theory, 58 (2012), 90-108. doi: 10.1109/TIT.2011.2171530.  Google Scholar

[17]

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

show all references

References:
[1]

P. Almeida, D. Napp and R. Pinto, A new class of superregular matrices and MDP convolutional codes, Linear Algebra Appl., 439 (2013), 2145-2157. doi: 10.1016/j.laa.2013.06.013.  Google Scholar

[2]

M. Arai, A. Yamamoto, A. Yamaguchi, S. Fukumoto and K. Iwasaki, Analysis of using convolutional codes to recover packet losses over burst erasure channels, in Proc. 2001 Pacific Rim Int. Symp. Depend. Comp., IEEE, Seoul, 2001, 258-265. doi: 10.1109/PRDC.2001.992706.  Google Scholar

[3]

J. J. Climent, D. Napp, C. Perea and R. Pinto, A construction of MDS 2D convolutional codes of rate 1/n based on superregular matrices, Linear Algebra Appl., 437 (2012), 766-780. doi: 10.1016/j.laa.2012.02.032.  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]

E. Fornasini and M. E. Valcher, On 2D finite support convolutional codes: an algebraic approach, Multidim. Syst. Signal Proc., 5 (1994), 231-243. doi: 10.1007/BF00980707.  Google Scholar

[6]

E. Fornasini and M. E. Valcher, nD polynomial matrices with applications to multidimensional signal analysis, Multidim. Syst. Signal Proc., 8 (1997), 387-407. doi: 10.1023/A:1008256224288.  Google Scholar

[7]

H. Gluesing-Luerssen, J. Rosenthal and R. Smarandache, Strongly MDS convolutional codes, IEEE Trans. Inf. Theory, 52 (2006), 584-598. doi: 10.1109/TIT.2005.862100.  Google Scholar

[8]

H. Gluesing-Luerssen, J. Rosenthal and P. Weiner, Duality between multidimensional convolutional codes and systems, in Advances in Mathematical Systems Theory (eds. F. Colonius, U. Helmke, F. Wirth and D. Praetzel-Wolters), Birkhauser, 2000, 135-150. doi: 10.1007/978-1-4612-0179-3_8.  Google Scholar

[9]

R. Hutchinson, The existence of strongly MDS convolutional codes, SIAM J. Control Opt., 47 (2008), 2812-2826. doi: 10.1137/050638977.  Google Scholar

[10]

R. Hutchinson, J. Rosenthal and R. Smarandache, Convolutional codes with maximum distance profile, Syst. Control Lett., 54 (2005), 53-63. doi: 10.1016/j.sysconle.2004.06.005.  Google Scholar

[11]

R. Hutchinson, R. Smarandache and J. Trumpf, On superregular matrices and MDP convolutional codes, Linear Algebra Appl., 428 (2008), 2585-2596. doi: 10.1016/j.laa.2008.02.011.  Google Scholar

[12]

P. Jangisarakul and C. Charoenlarpnopparut, Algebraic decoder of multidimensional convolutional code: Constructive algorithms for determining syndrome decoder and decoder matrix based on Gröbner basis, Multidim. Syst. Signal Proc., 22 (2011), 67-81. doi: 10.1007/s11045-010-0139-7.  Google Scholar

[13]

D. Napp, C. Perea and R. Pinto, Input-state-output representations and constructions of finite support 2D convolutional codes, Adv. Math. Commun., 4 (2010), 533-545. doi: 10.3934/amc.2010.4.533.  Google Scholar

[14]

V. Tomás, Complete-MDP Convolutional Codes over the Erasure Channel, Ph.D thesis, Univ. Alicante, Alicante, Spain, 2010. Google Scholar

[15]

V. Tomás, J. Rosenthal and R. Smarandache, Reverse-maximum distance profile convolutional codes over the erasure channel, in Proc.19th Int. Symp. Math. Theory Netw. Syst. (ed. A. Edelmayer), 2010, 2121-2127. doi: 10.5167/uzh-44714.  Google Scholar

[16]

V. Tomás, J. Rosenthal and R. Smarandache, Decoding of convolutional codes over the erasure channel, IEEE Trans. Inf. Theory, 58 (2012), 90-108. doi: 10.1109/TIT.2011.2171530.  Google Scholar

[17]

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

[1]

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

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

Sergio Estrada, J. R. García-Rozas, Justo Peralta, E. Sánchez-García. Group convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 83-94. doi: 10.3934/amc.2008.2.83
[4]

José Ignacio Iglesias Curto. Generalized AG convolutional codes. Advances in Mathematics of Communications, 2009, 3 (4) : 317-328. doi: 10.3934/amc.2009.3.317
[5]

Heide Gluesing-Luerssen. On isometries for convolutional codes. Advances in Mathematics of Communications, 2009, 3 (2) : 179-203. doi: 10.3934/amc.2009.3.179
[6]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55
[7]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83
[8]

Sara D. Cardell, Joan-Josep Climent. An approach to the performance of SPC product codes on the erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 11-28. doi: 10.3934/amc.2016.10.11
[9]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Convolutional codes with a matrix-algebra word-ambient. Advances in Mathematics of Communications, 2016, 10 (1) : 29-43. doi: 10.3934/amc.2016.10.29
[10]

Diego Napp, Roxana Smarandache. Constructing strongly-MDS convolutional codes with maximum distance profile. Advances in Mathematics of Communications, 2016, 10 (2) : 275-290. doi: 10.3934/amc.2016005
[11]

Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010
[12]

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

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

JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003
[15]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233
[16]

Gerhard Rein. Galactic dynamics in MOND---Existence of equilibria with finite mass and compact support. Kinetic & Related Models, 2015, 8 (2) : 381-394. doi: 10.3934/krm.2015.8.381
[17]

Yuusuke Sugiyama. Degeneracy in finite time of 1D quasilinear wave equations Ⅱ. Evolution Equations & Control Theory, 2017, 6 (4) : 615-628. doi: 10.3934/eect.2017031
[18]

Julia García-Luengo, Pedro Marín-Rubio, José Real. Regularity of pullback attractors and attraction in $H^1$ in arbitrarily large finite intervals for 2D Navier-Stokes equations with infinite delay. Discrete & Continuous Dynamical Systems, 2014, 34 (1) : 181-201. doi: 10.3934/dcds.2014.34.181
[19]

Kailu Yang, Xiaomiao Wang, Menglong Zhang, Lidong Wang. Some progress on optimal $ 2 $-D $ (n\times m,3,2,1) $-optical orthogonal codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021012
[20]

A. Naga, Z. Zhang. The polynomial-preserving recovery for higher order finite element methods in 2D and 3D. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 769-798. doi: 10.3934/dcdsb.2005.5.769

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (114)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy