August  2016, 10(3): 489-498. doi: 10.3934/amc.2016020

Further results on the classification of MDS codes

1. 

Department of Communications and Networking, School of Electrical Engineering, Aalto University, P.O. Box 13000, 00076 Aalto, Finland

Received  April 2015 Revised  June 2016 Published  August 2016

An unrestricted $q$-ary maximum distance separable (MDS) code $C$ with length $n$ over an alphabet $\mathcal{A}$ (of size $q$) is a set of $q^k$ codewords that are elements of $\mathcal{A}^n$, such that the smallest Hamming distance between two distinct codewords in $C$ is $d=n-k+1$. Sets of mutually orthogonal Latin squares of orders $q\leq 9$, corresponding to $q$-ary MDS codes of size $q^2$, and $q$-ary one-error-correcting MDS codes for $q\leq 8$ have been classified in earlier studies. These results are used here to complete the classification of all $7$-ary and $8$-ary MDS codes with $d\geq 3$ using a computer search.
Citation: Janne I. Kokkala, Patric R. J.  Östergård. Further results on the classification of MDS codes. Advances in Mathematics of Communications, 2016, 10 (3) : 489-498. doi: 10.3934/amc.2016020
References:
[1]

T. L. Alderson, $(6,3)$-MDS codes over an alphabet of size 4,, Des. Codes Cryptogr., 38 (2006), 31. doi: 10.1007/s10623-004-5659-4. Google Scholar

[2]

T. L. Alderson, A. A. Bruen and R. Silverman, Maximum distance separable codes and arcs in projective spaces,, J. Combin. Theory Ser. A, 114 (2007), 1101. doi: 10.1016/j.jcta.2006.11.005. Google Scholar

[3]

T. L. Alderson and A. Gács, On the maximality of linear codes,, Des. Codes Cryptogr., 53 (2009), 59. doi: 10.1007/s10623-009-9293-z. Google Scholar

[4]

S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis,, J. Eur. Math. Soc., 14 (2012), 733. doi: 10.4171/JEMS/316. Google Scholar

[5]

S. Ball and J. De Beule, On sets of vectors of a finite vector space in which every subset of basis size is a basis II,, Des. Codes Cryptogr., 65 (2012), 5. doi: 10.1007/s10623-012-9658-6. Google Scholar

[6]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes: Classification by Isometry and Applications,, Springer, (2006). Google Scholar

[7]

J. Egan and I. M. Wanless, Enumeration of MOLS of small order,, Math. Comp., 85 (2016), 799. doi: 10.1090/mcom/3010. Google Scholar

[8]

P. Kaski and P. R. J. Östergård, Classification Algorithms for Codes and Designs,, Springer, (2006). Google Scholar

[9]

P. Kaski and O. Pottonen, Libexact User's Guide, version 1.0, Technical Reports TR 2008-1,, Helsinki Inst. Inform. Techn., (2008). Google Scholar

[10]

G. Kéri, Types of superregular matrices and the number of $n$-arcs and complete $n$-arcs in $PG(r, q)$,, J. Combin. Des., 14 (2006), 363. doi: 10.1002/jcd.20091. Google Scholar

[11]

J. I. Kokkala, D. S. Krotov and P. R. J. Östergård, On the classification of MDS codes,, IEEE Trans. Inf. Theory, 61 (2015), 6485. doi: 10.1109/TIT.2015.2488659. Google Scholar

[12]

J. I. Kokkala and P. R. J. Östergård, Classification of Graeco-Latin cubes,, J. Combin. Des., 23 (2015), 509. doi: 10.1002/jcd.21400. Google Scholar

[13]

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

[14]

B. M. Maenhaut and I. M. Wanless, Atomic Latin squares of order eleven,, J. Combin. Des., 12 (2004), 12. doi: 10.1002/jcd.10064. Google Scholar

[15]

B. D. McKay, A. Meynert and W. Myrvold, Small Latin squares, quasigroups, and loops,, J. Combin. Des., 15 (2007), 98. doi: 10.1002/jcd.20105. Google Scholar

[16]

B. D. McKay and A. Piperno, Practical graph isomorphism, II,, J. Symbolic Comput., 60 (2014), 94. doi: 10.1016/j.jsc.2013.09.003. Google Scholar

[17]

B. D. McKay and I. M. Wanless, A census of small Latin hypercubes,, SIAM J. Discrete Math., 22 (2008), 719. doi: 10.1137/070693874. Google Scholar

[18]

S. Niskanen and P. R. J. Östergård, Cliquer User's guide, Version 1.0, Technical Report T48,, Communications Laboratory, (2003). Google Scholar

[19]

P. R. J. Östergård, Constructing combinatorial objects via cliques,, in Surveys in Combinatorics 2005 (ed. B. S. Webb), (2005), 57. doi: 10.1017/CBO9780511734885.004. Google Scholar

[20]

E. T. Parker, Computer investigation of orthogonal Latin squares of order ten,, in Proc. Sympos. Appl. Math., (1963), 73. Google Scholar

[21]

V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order,, Discrete Math. Appl., 21 (2011), 575. doi: 10.1016/j.disc.2010.09.023. Google Scholar

[22]

B. Segre, Curve razionali normali e $k$-archi negli spazi finiti,, Ann. Mat. Pura Appl., 39 (1955), 357. doi: 10.1007/BF02410779. Google Scholar

show all references

References:
[1]

T. L. Alderson, $(6,3)$-MDS codes over an alphabet of size 4,, Des. Codes Cryptogr., 38 (2006), 31. doi: 10.1007/s10623-004-5659-4. Google Scholar

[2]

T. L. Alderson, A. A. Bruen and R. Silverman, Maximum distance separable codes and arcs in projective spaces,, J. Combin. Theory Ser. A, 114 (2007), 1101. doi: 10.1016/j.jcta.2006.11.005. Google Scholar

[3]

T. L. Alderson and A. Gács, On the maximality of linear codes,, Des. Codes Cryptogr., 53 (2009), 59. doi: 10.1007/s10623-009-9293-z. Google Scholar

[4]

S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis,, J. Eur. Math. Soc., 14 (2012), 733. doi: 10.4171/JEMS/316. Google Scholar

[5]

S. Ball and J. De Beule, On sets of vectors of a finite vector space in which every subset of basis size is a basis II,, Des. Codes Cryptogr., 65 (2012), 5. doi: 10.1007/s10623-012-9658-6. Google Scholar

[6]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes: Classification by Isometry and Applications,, Springer, (2006). Google Scholar

[7]

J. Egan and I. M. Wanless, Enumeration of MOLS of small order,, Math. Comp., 85 (2016), 799. doi: 10.1090/mcom/3010. Google Scholar

[8]

P. Kaski and P. R. J. Östergård, Classification Algorithms for Codes and Designs,, Springer, (2006). Google Scholar

[9]

P. Kaski and O. Pottonen, Libexact User's Guide, version 1.0, Technical Reports TR 2008-1,, Helsinki Inst. Inform. Techn., (2008). Google Scholar

[10]

G. Kéri, Types of superregular matrices and the number of $n$-arcs and complete $n$-arcs in $PG(r, q)$,, J. Combin. Des., 14 (2006), 363. doi: 10.1002/jcd.20091. Google Scholar

[11]

J. I. Kokkala, D. S. Krotov and P. R. J. Östergård, On the classification of MDS codes,, IEEE Trans. Inf. Theory, 61 (2015), 6485. doi: 10.1109/TIT.2015.2488659. Google Scholar

[12]

J. I. Kokkala and P. R. J. Östergård, Classification of Graeco-Latin cubes,, J. Combin. Des., 23 (2015), 509. doi: 10.1002/jcd.21400. Google Scholar

[13]

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

[14]

B. M. Maenhaut and I. M. Wanless, Atomic Latin squares of order eleven,, J. Combin. Des., 12 (2004), 12. doi: 10.1002/jcd.10064. Google Scholar

[15]

B. D. McKay, A. Meynert and W. Myrvold, Small Latin squares, quasigroups, and loops,, J. Combin. Des., 15 (2007), 98. doi: 10.1002/jcd.20105. Google Scholar

[16]

B. D. McKay and A. Piperno, Practical graph isomorphism, II,, J. Symbolic Comput., 60 (2014), 94. doi: 10.1016/j.jsc.2013.09.003. Google Scholar

[17]

B. D. McKay and I. M. Wanless, A census of small Latin hypercubes,, SIAM J. Discrete Math., 22 (2008), 719. doi: 10.1137/070693874. Google Scholar

[18]

S. Niskanen and P. R. J. Östergård, Cliquer User's guide, Version 1.0, Technical Report T48,, Communications Laboratory, (2003). Google Scholar

[19]

P. R. J. Östergård, Constructing combinatorial objects via cliques,, in Surveys in Combinatorics 2005 (ed. B. S. Webb), (2005), 57. doi: 10.1017/CBO9780511734885.004. Google Scholar

[20]

E. T. Parker, Computer investigation of orthogonal Latin squares of order ten,, in Proc. Sympos. Appl. Math., (1963), 73. Google Scholar

[21]

V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order,, Discrete Math. Appl., 21 (2011), 575. doi: 10.1016/j.disc.2010.09.023. Google Scholar

[22]

B. Segre, Curve razionali normali e $k$-archi negli spazi finiti,, Ann. Mat. Pura Appl., 39 (1955), 357. doi: 10.1007/BF02410779. Google Scholar

[1]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[2]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[3]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[4]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[5]

Ilias S. Kotsireas, Christos Koukouvinos, Dimitris E. Simos. MDS and near-MDS self-dual codes over large prime fields. Advances in Mathematics of Communications, 2009, 3 (4) : 349-361. doi: 10.3934/amc.2009.3.349

[6]

Erick Limas. An application of minimal spanning trees and hierarchical trees to the study of Latin American exchange rates. Journal of Dynamics & Games, 2019, 6 (2) : 131-148. doi: 10.3934/jdg.2019010

[7]

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

[8]

Anna-Lena Horlemann-Trautmann, Alessandro Neri. A complete classification of partial MDS (maximally recoverable) codes with one global parity. Advances in Mathematics of Communications, 2020, 14 (1) : 69-88. doi: 10.3934/amc.2020006

[9]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[10]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[11]

Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh Ray, Susanta Samanta. Cryptographically significant mds matrices over finite fields: A brief survey and some generalized results. Advances in Mathematics of Communications, 2019, 13 (4) : 779-843. doi: 10.3934/amc.2019045

[12]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[13]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[14]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261

[15]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281

[16]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275

[17]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027

[18]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042

[19]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032

[20]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]