Article Contents
Article Contents

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

• * Corresponding author: Julia Lieb
• 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.

Mathematics Subject Classification: Primary: 94B10; Secondary: 94B35.

 Citation:

•  $\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$ $\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] 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.

Tables(3)