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.

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

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

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

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.

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

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

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

[9]

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

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

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

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

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

[14]

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

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

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

[17]

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

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.

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

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

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

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.

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

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

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

[9]

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

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

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

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

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

[14]

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

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

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

[17]

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

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

Gianira N. Alfarano, Anina Gruica, Julia Lieb, Joachim Rosenthal. Convolutional codes over finite chain rings, MDP codes and their characterization. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022028
[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 and Continuous Dynamical Systems, 2014, 34 (1) : 181-201. doi: 10.3934/dcds.2014.34.181
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy