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. Google Scholar

[2]

P. Almeida, D. Napp and R. Pinto, A new class of superregular matrices and MDP convolutional codes,, Linear Algebra Appl., 439 (2013), 2145. doi: 10.1016/j.laa.2013.06.013. Google Scholar

[3]

P. Almeida, D. Napp and R. Pinto, Superregular matrices and applications to convolutional codes,, Linear Algebra Appl., 499 (2016), 1. doi: 10.1016/j.laa.2016.02.034. Google Scholar

[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, (2001). Google Scholar

[5]

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

[6]

M. A. Epstein, Algebraic decoding for a binary erasure channel,, Technical Report 340, (1958). Google Scholar

[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, (2008), 1053. Google Scholar

[8]

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

[9]

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

[10]

H. Gluesing-Luerssen, J. Rosenthal and R. Smarandache, Strongly MDS convolutional codes,, IEEE Trans. Inf. Theory, 52 (2006), 584. doi: 10.1109/TIT.2005.862100. Google Scholar

[11]

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

[12]

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

[13]

R. Hutchinson, R. Smarandache and J. Trumpf, On superregular matrices and {MDP} convolutional codes,, Linear Algebra Appl., 428 (2008), 2585. doi: 10.1016/j.laa.2008.02.011. Google Scholar

[14]

R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding,, IEEE Press, (1999). doi: 10.1109/9780470544693. Google Scholar

[15]

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

[16]

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

[17]

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

[18]

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

[19]

J. Rosenthal, Connections between linear systems and convolutional codes,, in Codes, (2001), 39. doi: 10.1007/978-1-4613-0165-3_2. Google Scholar

[20]

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

[21]

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

[22]

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

[23]

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

[24]

V. Tomás, Complete-MDP Convolutional Codes over the Erasure Channel,, Ph.D thesis, (2010). Google Scholar

[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, (2009), 556. Google Scholar

[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, (2010), 2121. Google Scholar

[27]

V. Tomás, J. Rosenthal and R. Smarandache, Decoding of convolutional codes over the erasure channel,, IEEE Trans. Inf. Theory, 58 (2012), 90. doi: 10.1109/TIT.2011.2171530. Google Scholar

show all references

References:
[1]

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

[2]

P. Almeida, D. Napp and R. Pinto, A new class of superregular matrices and MDP convolutional codes,, Linear Algebra Appl., 439 (2013), 2145. doi: 10.1016/j.laa.2013.06.013. Google Scholar

[3]

P. Almeida, D. Napp and R. Pinto, Superregular matrices and applications to convolutional codes,, Linear Algebra Appl., 499 (2016), 1. doi: 10.1016/j.laa.2016.02.034. Google Scholar

[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, (2001). Google Scholar

[5]

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

[6]

M. A. Epstein, Algebraic decoding for a binary erasure channel,, Technical Report 340, (1958). Google Scholar

[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, (2008), 1053. Google Scholar

[8]

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

[9]

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

[10]

H. Gluesing-Luerssen, J. Rosenthal and R. Smarandache, Strongly MDS convolutional codes,, IEEE Trans. Inf. Theory, 52 (2006), 584. doi: 10.1109/TIT.2005.862100. Google Scholar

[11]

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

[12]

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

[13]

R. Hutchinson, R. Smarandache and J. Trumpf, On superregular matrices and {MDP} convolutional codes,, Linear Algebra Appl., 428 (2008), 2585. doi: 10.1016/j.laa.2008.02.011. Google Scholar

[14]

R. Johannesson and K. S. Zigangirov, Fundamentals of Convolutional Coding,, IEEE Press, (1999). doi: 10.1109/9780470544693. Google Scholar

[15]

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

[16]

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

[17]

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

[18]

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

[19]

J. Rosenthal, Connections between linear systems and convolutional codes,, in Codes, (2001), 39. doi: 10.1007/978-1-4613-0165-3_2. Google Scholar

[20]

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

[21]

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

[22]

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

[23]

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

[24]

V. Tomás, Complete-MDP Convolutional Codes over the Erasure Channel,, Ph.D thesis, (2010). Google Scholar

[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, (2009), 556. Google Scholar

[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, (2010), 2121. Google Scholar

[27]

V. Tomás, J. Rosenthal and R. Smarandache, Decoding of convolutional codes over the erasure channel,, IEEE Trans. Inf. Theory, 58 (2012), 90. doi: 10.1109/TIT.2011.2171530. Google Scholar

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

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175

[19]

Andries E. Brouwer, Tuvi Etzion. Some new distance-4 constant weight codes. Advances in Mathematics of Communications, 2011, 5 (3) : 417-424. doi: 10.3934/amc.2011.5.417

[20]

Joaquim Borges, Josep Rifà, Victor A. Zinoviev. Families of nested completely regular codes and distance-regular graphs. Advances in Mathematics of Communications, 2015, 9 (2) : 233-246. doi: 10.3934/amc.2015.9.233

2018 Impact Factor: 0.879

Metrics

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

Other articles
by authors

[Back to Top]