# American Institute of Mathematical Sciences

• Previous Article
Representation and matrix-product structure of Type-1 constacyclic codes over $\mathbb{F}_{p^m}[u]/\langle u^e\rangle$
• AMC Home
• This Issue
• Next Article
A multivariate identity-based broadcast encryption with applications to the internet of things
doi: 10.3934/amc.2021031
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## A decoding algorithm for 2D convolutional codes over the erasure channel

 1 Institute of Mathematics, University of Zurich 2 Department of Mathematics, University of Aveiro

* Corresponding author: Julia Lieb

Received  June 2020 Revised  March 2021 Early access August 2021

Two-dimensional (2D) convolutional codes are a generalization of (1D) convolutional codes, which are suitable for transmission over an erasure channel. In this paper, we present a decoding algorithm for 2D convolutional codes over such a channel by reducing the decoding process to several decoding steps applied to 1D convolutional codes. Moreover, we provide constructions of 2D convolutional codes that are specially tailored to our decoding algorithm.

Citation: Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, doi: 10.3934/amc.2021031
##### References:
 [1] P. Almeida, D. Napp and R. Pinto, MDS 2D convolutional codes with optimal 1D horizontal projections, Des. Codes Cryptogr., 86 (2018), 285-302.  doi: 10.1007/s10623-017-0357-1. [2] P. J. Almeida, D. Napp and R. Pinto, Superregular matrices and applications to convolutional codes, Linear Algebra Appl., 499 (2016), 1-25.  doi: 10.1016/j.laa.2016.02.034. [3] P. J. Almeida and J. Lieb, Complete j-MDP convolutional codes, IEEE Trans. Inform. Theory, 66 (2020), 7348-7359.  doi: 10.1109/TIT.2020.3015698. [4] 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. [5] J. Climent, D. Napp, C. Perea and R. Pinto, Maximum distance seperable 2D convolutional codes, IEEE Trans. Inform. Theory, 62 (2016), 669-680.  doi: 10.1109/TIT.2015.2509075. [6] J. Climent, D. Napp, R. Pinto and R. Simoes, Decoding of 2D convolutional codes over an erasure channel, Adv. Math. Commun., 10 (2016), 179-193.  doi: 10.3934/amc.2016.10.179. [7] 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. [8] E. Fornasini and M. E. Valcher, Algebraic aspects of two-dimensional convolutional codes, IEEE Trans. Inform. Theory, 40 (1994), 1068-1082.  doi: 10.1109/18.335967. [9] H. Gluesing-Luerssen, J. Rosenthal and R. Smarandache, Strongly-MDS convolutional codes, IEEE Trans. Inform. Theory, 52 (2006), 584-598.  doi: 10.1109/TIT.2005.862100. [10] R. Hutchinson, J. Rosenthal and R. Smarandache, Convolutional codes with maximum distance profile, Systems Control Lett., 54 (2005), 53-63.  doi: 10.1016/j.sysconle.2004.06.005. [11] P. Jangisarakul and C. Charoenlarpnopparut, Decoding of $2$-d convolutional codes based on algebraic approach, International Journal of Pure and Applied Mathematics, 97 (2014), 21-30.  doi: 10.12732/ijpam.v97i1.3. [12] J. Lieb, Complete MDP convolutional codes, J. Algebra Appl., 18 (2019), 1950105. doi: 10.1142/S0219498819501056. [13] J. Lieb, R. Pinto and J. Rosenthal, Convolutional codes, in Concise Encyclopedia of Coding Theory (eds. C. Huffman, J. Kim, P. Sole), CRC Press, 2021. [14] R. Lobo, D. L. Blitzer and M. A. Vouk, Locally invertible multidimensional convolutional encoders, IEEE Trans. Inform. Theory, 58 (2012), 1774-1782.  doi: 10.1109/TIT.2011.2178129. [15] 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. [16] V. Strassen, Gaussian elimination is not optimal, Numer. Math., 13 (1969) 354–356. doi: 10.1007/BF02165411. [17] V. Tomas, J. Rosenthal and R. Smarandache, Decoding of convolutional codes Over the erasure channel, IEEE Trans. Inform. Theory, 58 (2012), 90-108.  doi: 10.1109/TIT.2011.2171530. [18] P. A. Weiner, Multidimensional Convolutional Codes, Thesis (Ph.D.) University of Notre Dame. 1998. [19] E. V. York, Algebraic Description and Construction of Error Correcting Codes: A Linear Systems Point of View, Thesis (Ph.D.) University of Notre Dame. 1997.

show all references

##### References:
 [1] P. Almeida, D. Napp and R. Pinto, MDS 2D convolutional codes with optimal 1D horizontal projections, Des. Codes Cryptogr., 86 (2018), 285-302.  doi: 10.1007/s10623-017-0357-1. [2] P. J. Almeida, D. Napp and R. Pinto, Superregular matrices and applications to convolutional codes, Linear Algebra Appl., 499 (2016), 1-25.  doi: 10.1016/j.laa.2016.02.034. [3] P. J. Almeida and J. Lieb, Complete j-MDP convolutional codes, IEEE Trans. Inform. Theory, 66 (2020), 7348-7359.  doi: 10.1109/TIT.2020.3015698. [4] 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. [5] J. Climent, D. Napp, C. Perea and R. Pinto, Maximum distance seperable 2D convolutional codes, IEEE Trans. Inform. Theory, 62 (2016), 669-680.  doi: 10.1109/TIT.2015.2509075. [6] J. Climent, D. Napp, R. Pinto and R. Simoes, Decoding of 2D convolutional codes over an erasure channel, Adv. Math. Commun., 10 (2016), 179-193.  doi: 10.3934/amc.2016.10.179. [7] 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. [8] E. Fornasini and M. E. Valcher, Algebraic aspects of two-dimensional convolutional codes, IEEE Trans. Inform. Theory, 40 (1994), 1068-1082.  doi: 10.1109/18.335967. [9] H. Gluesing-Luerssen, J. Rosenthal and R. Smarandache, Strongly-MDS convolutional codes, IEEE Trans. Inform. Theory, 52 (2006), 584-598.  doi: 10.1109/TIT.2005.862100. [10] R. Hutchinson, J. Rosenthal and R. Smarandache, Convolutional codes with maximum distance profile, Systems Control Lett., 54 (2005), 53-63.  doi: 10.1016/j.sysconle.2004.06.005. [11] P. Jangisarakul and C. Charoenlarpnopparut, Decoding of $2$-d convolutional codes based on algebraic approach, International Journal of Pure and Applied Mathematics, 97 (2014), 21-30.  doi: 10.12732/ijpam.v97i1.3. [12] J. Lieb, Complete MDP convolutional codes, J. Algebra Appl., 18 (2019), 1950105. doi: 10.1142/S0219498819501056. [13] J. Lieb, R. Pinto and J. Rosenthal, Convolutional codes, in Concise Encyclopedia of Coding Theory (eds. C. Huffman, J. Kim, P. Sole), CRC Press, 2021. [14] R. Lobo, D. L. Blitzer and M. A. Vouk, Locally invertible multidimensional convolutional encoders, IEEE Trans. Inform. Theory, 58 (2012), 1774-1782.  doi: 10.1109/TIT.2011.2178129. [15] 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. [16] V. Strassen, Gaussian elimination is not optimal, Numer. Math., 13 (1969) 354–356. doi: 10.1007/BF02165411. [17] V. Tomas, J. Rosenthal and R. Smarandache, Decoding of convolutional codes Over the erasure channel, IEEE Trans. Inform. Theory, 58 (2012), 90-108.  doi: 10.1109/TIT.2011.2171530. [18] P. A. Weiner, Multidimensional Convolutional Codes, Thesis (Ph.D.) University of Notre Dame. 1998. [19] E. V. York, Algebraic Description and Construction of Error Correcting Codes: A Linear Systems Point of View, Thesis (Ph.D.) University of Notre Dame. 1997.
 $\hat{v}_{ij}$ $j=0$ $j=1$ $j=2$ $j=3$ $j=4$ $i=0$ $\ast$ $v_{01,1}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{01,2}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{01,3}$ $\ast$ $v_{03,3}$ $\ast$ $i=1$ $\ast$ $\ast$ $v_{12,1}$ $\ast$ $v_{14,1}$ $\ast$ $\ast$ $v_{12,2}$ $\ast$ $v_{14,2}$ $\ast$ $\ast$ $v_{12,3}$ $v_{13,3}$ $v_{14,3}$ $i=2$ $v_{20,1}$ $\ast$ $\ast$ $\ast$ $v_{24,1}$ $v_{20,2}$ $\ast$ $\ast$ $\ast$ $v_{24,2}$ $v_{20,3}$ $v_{21,3}$ $\ast$ $v_{23,3}$ $v_{24,3}$ $i=3$ $\ast$ $v_{31,1}$ $\ast$ $\ast$ $v_{34,1}$ $\ast$ $v_{31,2}$ $\ast$ $\ast$ $v_{34,2}$ $\ast$ $v_{31,3}$ $\ast$ $v_{33,3}$ $v_{34,3}$ $i=4$ $\ast$ $v_{41,1}$ $\ast$ $\ast$ $v_{44,1}$ $\ast$ $v_{41,2}$ $\ast$ $\ast$ $v_{44,2}$ $\ast$ $v_{41,3}$ $\ast$ $v_{43,3}$ $v_{44,3}$
 $\hat{v}_{ij}$ $j=0$ $j=1$ $j=2$ $j=3$ $j=4$ $i=0$ $\ast$ $v_{01,1}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{01,2}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{01,3}$ $\ast$ $v_{03,3}$ $\ast$ $i=1$ $\ast$ $\ast$ $v_{12,1}$ $\ast$ $v_{14,1}$ $\ast$ $\ast$ $v_{12,2}$ $\ast$ $v_{14,2}$ $\ast$ $\ast$ $v_{12,3}$ $v_{13,3}$ $v_{14,3}$ $i=2$ $v_{20,1}$ $\ast$ $\ast$ $\ast$ $v_{24,1}$ $v_{20,2}$ $\ast$ $\ast$ $\ast$ $v_{24,2}$ $v_{20,3}$ $v_{21,3}$ $\ast$ $v_{23,3}$ $v_{24,3}$ $i=3$ $\ast$ $v_{31,1}$ $\ast$ $\ast$ $v_{34,1}$ $\ast$ $v_{31,2}$ $\ast$ $\ast$ $v_{34,2}$ $\ast$ $v_{31,3}$ $\ast$ $v_{33,3}$ $v_{34,3}$ $i=4$ $\ast$ $v_{41,1}$ $\ast$ $\ast$ $v_{44,1}$ $\ast$ $v_{41,2}$ $\ast$ $\ast$ $v_{44,2}$ $\ast$ $v_{41,3}$ $\ast$ $v_{43,3}$ $v_{44,3}$
 $\hat{v}_{ij}$ $j=0$ $j=1$ $j=2$ $j=3$ $j=4$ $j=5$ $j=6$ $i=0$ $v_{00,1}$ $\ast$ $v_{02,1}$ $\ast$ $v_{04,1}$ $v_{05,1}$ $v_{06,1}$ $v_{00,2}$ $\ast$ $v_{02,2}$ $\ast$ $\ast$ $v_{05,2}$ $v_{06,2}$ $i=1$ $v_{10,1}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{15,1}$ $v_{16,1}$ $v_{10,2}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{15,2}$ $v_{16,2}$ $i=2$ $\ast$ $v_{21,1}$ $v_{22,1}$ $\ast$ $\ast$ $v_{25,1}$ $v_{26,1}$ $\ast$ $v_{21,2}$ $v_{22,2}$ $\ast$ $\ast$ $v_{25,2}$ $v_{26,2}$ $i=3$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{34,1}$ $v_{35,1}$ $\ast$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{34,2}$ $v_{35,2}$ $\ast$ $i=4$ $v_{40,1}$ $v_{41,1}$ $v_{42,1}$ $\ast$ $\ast$ $v_{45,1}$ $v_{46,1}$ $v_{40,2}$ $v_{41,2}$ $v_{42,2}$ $\ast$ $\ast$ $v_{45,2}$ $v_{46,2}$ $i=5$ $v_{50,1}$ $v_{51,1}$ $v_{52,1}$ $\ast$ $\ast$ $v_{55,1}$ $v_{56,1}$ $v_{50,2}$ $v_{51,2}$ $v_{52,2}$ $\ast$ $\ast$ $v_{55,2}$ $v_{56,2}$ $i=6$ $v_{60,1}$ $v_{61,1}$ $v_{62,1}$ $\ast$ $\ast$ $v_{65,1}$ $v_{66,1}$ $v_{60,2}$ $v_{61,2}$ $v_{62,2}$ $\ast$ $\ast$ $v_{65,2}$ $v_{66,2}$
 $\hat{v}_{ij}$ $j=0$ $j=1$ $j=2$ $j=3$ $j=4$ $j=5$ $j=6$ $i=0$ $v_{00,1}$ $\ast$ $v_{02,1}$ $\ast$ $v_{04,1}$ $v_{05,1}$ $v_{06,1}$ $v_{00,2}$ $\ast$ $v_{02,2}$ $\ast$ $\ast$ $v_{05,2}$ $v_{06,2}$ $i=1$ $v_{10,1}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{15,1}$ $v_{16,1}$ $v_{10,2}$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{15,2}$ $v_{16,2}$ $i=2$ $\ast$ $v_{21,1}$ $v_{22,1}$ $\ast$ $\ast$ $v_{25,1}$ $v_{26,1}$ $\ast$ $v_{21,2}$ $v_{22,2}$ $\ast$ $\ast$ $v_{25,2}$ $v_{26,2}$ $i=3$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{34,1}$ $v_{35,1}$ $\ast$ $\ast$ $\ast$ $\ast$ $\ast$ $v_{34,2}$ $v_{35,2}$ $\ast$ $i=4$ $v_{40,1}$ $v_{41,1}$ $v_{42,1}$ $\ast$ $\ast$ $v_{45,1}$ $v_{46,1}$ $v_{40,2}$ $v_{41,2}$ $v_{42,2}$ $\ast$ $\ast$ $v_{45,2}$ $v_{46,2}$ $i=5$ $v_{50,1}$ $v_{51,1}$ $v_{52,1}$ $\ast$ $\ast$ $v_{55,1}$ $v_{56,1}$ $v_{50,2}$ $v_{51,2}$ $v_{52,2}$ $\ast$ $\ast$ $v_{55,2}$ $v_{56,2}$ $i=6$ $v_{60,1}$ $v_{61,1}$ $v_{62,1}$ $\ast$ $\ast$ $v_{65,1}$ $v_{66,1}$ $v_{60,2}$ $v_{61,2}$ $v_{62,2}$ $\ast$ $\ast$ $v_{65,2}$ $v_{66,2}$
 $\hat{v}_{ij}$ $j=0$ $\cdots$ $j=\deg_{z_1}(v(z_1,z_2))$ $i=0$ $\ast$ $\cdots$ $\ast$ $\vdots$ $\vdots$ $\vdots$ $i=(L_1+1)(n-k)$ $\ast$ $\cdots$ $\ast$ $i=(L_1+1)(n-k)+1$ $v_{(L_1+1)(n-k)+1,0}$ $\cdots$ $v_{(L_1+1)(n-k)+1,\deg_{z_1}(v(z_1,z_2))}$ $\vdots$ $\vdots$ $\vdots$ $i=(L_1+1)n$ $v_{(L_1+1)n,0}$ $\cdots$ $v_{(L_1+1)n,\deg_{z_1}(v(z_1,z_2))}$
 $\hat{v}_{ij}$ $j=0$ $\cdots$ $j=\deg_{z_1}(v(z_1,z_2))$ $i=0$ $\ast$ $\cdots$ $\ast$ $\vdots$ $\vdots$ $\vdots$ $i=(L_1+1)(n-k)$ $\ast$ $\cdots$ $\ast$ $i=(L_1+1)(n-k)+1$ $v_{(L_1+1)(n-k)+1,0}$ $\cdots$ $v_{(L_1+1)(n-k)+1,\deg_{z_1}(v(z_1,z_2))}$ $\vdots$ $\vdots$ $\vdots$ $i=(L_1+1)n$ $v_{(L_1+1)n,0}$ $\cdots$ $v_{(L_1+1)n,\deg_{z_1}(v(z_1,z_2))}$
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [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] 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 [14] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [15] Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419 [16] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [17] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [18] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [19] 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 [20] 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

2021 Impact Factor: 1.015