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]

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

[2]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049

[3]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060

[4]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124

[5]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[6]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129

[7]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044

[8]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[9]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053

[10]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065

[11]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

[12]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054

[13]

Shanding Xu, Longjiang Qu, Xiwang Cao. Three classes of partitioned difference families and their optimal constant composition codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020120

[14]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[15]

Fengwei Li, Qin Yue, Xiaoming Sun. The values of two classes of Gaussian periods in index 2 case and weight distributions of linear codes. Advances in Mathematics of Communications, 2021, 15 (1) : 131-153. doi: 10.3934/amc.2020049

[16]

Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $ p $-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039

[17]

Tingting Wu, Li Liu, Lanqiang Li, Shixin Zhu. Repeated-root constacyclic codes of length $ 6lp^s $. Advances in Mathematics of Communications, 2021, 15 (1) : 167-189. doi: 10.3934/amc.2020051

[18]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122

[19]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[20]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]