May  2016, 10(2): 275-290. doi: 10.3934/amc.2016005

Constructing strongly-MDS convolutional codes with maximum distance profile

1. 

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

2. 

Departments of Mathematics, and of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46566, United States

Received  January 2014 Published  April 2016

This paper revisits strongly-MDS convolutional codes with maximum distance profile (MDP). These are (non-binary) convolutional codes that have an optimum sequence of column distances and attains the generalized Singleton bound at the earliest possible time frame. These properties make these convolutional codes applicable over the erasure channel, since they are able to correct a large number of erasures per time interval. The existence of these codes have been shown only for some specific cases. This paper shows by construction the existence of convolutional codes that are both strongly-MDS and MDP for all choices of parameters.
Citation: 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
References:
[1]

A. K. Aidinyan, On matrices with nondegenerate square submatrices, Probl. Peredachi Inf., 22 (1986), 106-108.

[2]

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.

[3]

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

[4]

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. Dependable Computing, Washington, DC, 2001, p.258.

[5]

J. J. Climent, D. Napp, C. Perea and R. Pinto, Maximum distance separable 2D convolutional codes, IEEE Trans. Inf. Theory, 62 (2016), 669-680.

[6]

M. A. Epstein, Algebraic decoding for a binary erasure channel, Technical Report 340, MIT, 1958.

[7]

S. Fashandi, S. O. Gharan and A. K. Khandani, Coding over an erasure channel with a large alphabet size, in Proc. IEEE Int. Symp. Inf. Theory, Toronto, 2008, 1053-1057.

[8]

E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional codes, Linear Algebra Appl., 392 (2004), 119-158. doi: 10.1016/j.laa.2004.06.007.

[9]

G. D. Forney, Jr., Structural analysis of convolutional codes via dual codes, IEEE Trans. Inf. Theory, 19 (1973), 512-518.

[10]

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.

[11]

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

[12]

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

[13]

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.

[14]

R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding, IEEE Press, New York, 1999. doi: 10.1109/9780470544693.

[15]

J. Lacan and J. Fimes, Systematic MDS erasure codes based on Vandermonde matrices, IEEE Commun. Letters, 8 (2004), 570-572.

[16]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes II, North-Holland Publishing Co., Amsterdam, 1977.

[17]

R. J. McEliece, The algebraic theory of convolutional codes, in Handbook of Coding Theory (eds. V. Pless and W.C. Huffman), Elsevier, Amsterdam, 1998, 1065-1138.

[18]

V. Paxson, End-to-end internet packet dynamics, IEEE/ACM Trans. Netw., 7 (1999), 277-292.

[19]

J. Rosenthal, Connections between linear systems and convolutional codes, in Codes, Systems and Graphical Models (eds. B. Marcus and J. Rosenthal), Springer-Verlag, 2001, 39-66. doi: 10.1007/978-1-4613-0165-3_2.

[20]

J. Rosenthal and R. Smarandache, Maximum distance separable convolutional codes, Appl. Algebra Engrg. Comm. Comput., 10 (1999), 15-32. doi: 10.1007/s002000050120.

[21]

J. Rosenthal and E. V. York, BCH convolutional codes, IEEE Trans. Inf. Theory, 45 (1999), 1833-1844. doi: 10.1109/18.782104.

[22]

R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, IEEE Trans. Inf. Theory, 35 (1989), 1314-1319. doi: 10.1109/18.45291.

[23]

R. M. Roth and G. Seroussi, On generator matrices of MDS codes, IEEE Trans. Inf. Theory, 31 (1985), 826-830. doi: 10.1109/TIT.1985.1057113.

[24]

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

[25]

V. Tomás, J. Rosenthal and R. Smarandache, Decoding of MDP convolutional codes over the erasure channel, in Proc. 2009 IEEE Int. Symp. Inform. Theory, Seoul, 2009, 556-560.

[26]

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 Networks Systems - MTNS, Budapest, 2010, 2121-2127.

[27]

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.

show all references

References:
[1]

A. K. Aidinyan, On matrices with nondegenerate square submatrices, Probl. Peredachi Inf., 22 (1986), 106-108.

[2]

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.

[3]

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

[4]

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. Dependable Computing, Washington, DC, 2001, p.258.

[5]

J. J. Climent, D. Napp, C. Perea and R. Pinto, Maximum distance separable 2D convolutional codes, IEEE Trans. Inf. Theory, 62 (2016), 669-680.

[6]

M. A. Epstein, Algebraic decoding for a binary erasure channel, Technical Report 340, MIT, 1958.

[7]

S. Fashandi, S. O. Gharan and A. K. Khandani, Coding over an erasure channel with a large alphabet size, in Proc. IEEE Int. Symp. Inf. Theory, Toronto, 2008, 1053-1057.

[8]

E. Fornasini and R. Pinto, Matrix fraction descriptions in convolutional codes, Linear Algebra Appl., 392 (2004), 119-158. doi: 10.1016/j.laa.2004.06.007.

[9]

G. D. Forney, Jr., Structural analysis of convolutional codes via dual codes, IEEE Trans. Inf. Theory, 19 (1973), 512-518.

[10]

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.

[11]

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

[12]

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

[13]

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.

[14]

R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding, IEEE Press, New York, 1999. doi: 10.1109/9780470544693.

[15]

J. Lacan and J. Fimes, Systematic MDS erasure codes based on Vandermonde matrices, IEEE Commun. Letters, 8 (2004), 570-572.

[16]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes II, North-Holland Publishing Co., Amsterdam, 1977.

[17]

R. J. McEliece, The algebraic theory of convolutional codes, in Handbook of Coding Theory (eds. V. Pless and W.C. Huffman), Elsevier, Amsterdam, 1998, 1065-1138.

[18]

V. Paxson, End-to-end internet packet dynamics, IEEE/ACM Trans. Netw., 7 (1999), 277-292.

[19]

J. Rosenthal, Connections between linear systems and convolutional codes, in Codes, Systems and Graphical Models (eds. B. Marcus and J. Rosenthal), Springer-Verlag, 2001, 39-66. doi: 10.1007/978-1-4613-0165-3_2.

[20]

J. Rosenthal and R. Smarandache, Maximum distance separable convolutional codes, Appl. Algebra Engrg. Comm. Comput., 10 (1999), 15-32. doi: 10.1007/s002000050120.

[21]

J. Rosenthal and E. V. York, BCH convolutional codes, IEEE Trans. Inf. Theory, 45 (1999), 1833-1844. doi: 10.1109/18.782104.

[22]

R. M. Roth and A. Lempel, On MDS codes via Cauchy matrices, IEEE Trans. Inf. Theory, 35 (1989), 1314-1319. doi: 10.1109/18.45291.

[23]

R. M. Roth and G. Seroussi, On generator matrices of MDS codes, IEEE Trans. Inf. Theory, 31 (1985), 826-830. doi: 10.1109/TIT.1985.1057113.

[24]

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

[25]

V. Tomás, J. Rosenthal and R. Smarandache, Decoding of MDP convolutional codes over the erasure channel, in Proc. 2009 IEEE Int. Symp. Inform. Theory, Seoul, 2009, 556-560.

[26]

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 Networks Systems - MTNS, Budapest, 2010, 2121-2127.

[27]

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.

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

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]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019

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

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

[10]

José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018

[11]

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

[12]

Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028

[13]

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

[14]

Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006

[15]

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

[16]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015

[17]

Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273

[18]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038

[19]

Jinmei Fan, Yanhai Zhang. Optimal quinary negacyclic codes with minimum distance four. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021043

[20]

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

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (178)
  • HTML views (0)
  • Cited by (15)

Other articles
by authors

[Back to Top]