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

Julia Lieb; Raquel Pinto

doi:10.3934/amc.2021031

Article Contents

2023, Volume 17, Issue 4: 935-959. Doi: 10.3934/amc.2021031

This issue Previous Article Partitioned difference families: The storm has not yet passed Next Article On the number of distinct k-decks: Enumeration and bounds

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

Julia Lieb^1, , and
Raquel Pinto^2,

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

^* Corresponding author: Julia Lieb
^* Corresponding author: Julia Lieb

Received: June 2020

Revised: March 2021

Early access: August 2021

Published: August 2023

Abstract / Introduction Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

$ \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} $

| Show Table

DownLoad: CSV

$ \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} $

| Show Table

DownLoad: CSV

$ \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))} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.