Further results on the classification of MDS codes

Previous Article
Algebraic structures of MRD codes
AMC Home
This Issue
Next Article
A new family of linear maximum rank distance codes

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

Further results on the classification of MDS codes

Janne I. Kokkala ^1, and Patric R. J. Östergård ^1,

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

Abstract
Related Papers

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.

Keywords: MDS code, Latin hypercube., Classication.

Mathematics Subject Classification: Primary: 94B25; Secondary: 05B1.

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-40. doi: 10.1007/s10623-004-5659-4.
[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-1117. doi: 10.1016/j.jcta.2006.11.005.
[3]	T. L. Alderson and A. Gács, On the maximality of linear codes, Des. Codes Cryptogr., 53 (2009), 59-68. doi: 10.1007/s10623-009-9293-z.
[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-748. doi: 10.4171/JEMS/316.
[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-14. doi: 10.1007/s10623-012-9658-6.
[6]	A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes: Classification by Isometry and Applications, Springer, Berlin, 2006.
[7]	J. Egan and I. M. Wanless, Enumeration of MOLS of small order, Math. Comp., 85 (2016), 799-824. doi: 10.1090/mcom/3010.
[8]	P. Kaski and P. R. J. Östergård, Classification Algorithms for Codes and Designs, Springer, Berlin, 2006.
[9]	P. Kaski and O. Pottonen, Libexact User's Guide, version 1.0, Technical Reports TR 2008-1, Helsinki Inst. Inform. Techn., Helsinki, 2008.
[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-390. doi: 10.1002/jcd.20091.
[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-6492. doi: 10.1109/TIT.2015.2488659.
[12]	J. I. Kokkala and P. R. J. Östergård, Classification of Graeco-Latin cubes, J. Combin. Des., 23 (2015), 509-512. doi: 10.1002/jcd.21400.
[13]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
[14]	B. M. Maenhaut and I. M. Wanless, Atomic Latin squares of order eleven, J. Combin. Des., 12 (2004), 12-34. doi: 10.1002/jcd.10064.
[15]	B. D. McKay, A. Meynert and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007), 98-119. doi: 10.1002/jcd.20105.
[16]	B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput., 60 (2014), 94-112. doi: 10.1016/j.jsc.2013.09.003.
[17]	B. D. McKay and I. M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math., 22 (2008), 719-736. doi: 10.1137/070693874.
[18]	S. Niskanen and P. R. J. Östergård, Cliquer User's guide, Version 1.0, Technical Report T48, Communications Laboratory, Helsinki Univ. Techn., Espoo, 2003.
[19]	P. R. J. Östergård, Constructing combinatorial objects via cliques, in Surveys in Combinatorics 2005 (ed. B. S. Webb), Cambridge Univ. Press, Cambridge, 2005, 57-82. doi: 10.1017/CBO9780511734885.004.
[20]	E. T. Parker, Computer investigation of orthogonal Latin squares of order ten, in Proc. Sympos. Appl. Math., Amer. Math. Soc., Providence, 1963, 73-81.
[21]	V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order, Discrete Math. Appl., 21 (2011), 575-585. doi: 10.1016/j.disc.2010.09.023.
[22]	B. Segre, Curve razionali normali e $k$-archi negli spazi finiti, Ann. Mat. Pura Appl., 39 (1955), 357-379. doi: 10.1007/BF02410779.

show all references

References:

[1]	T. L. Alderson, $(6,3)$-MDS codes over an alphabet of size 4, Des. Codes Cryptogr., 38 (2006), 31-40. doi: 10.1007/s10623-004-5659-4.
[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-1117. doi: 10.1016/j.jcta.2006.11.005.
[3]	T. L. Alderson and A. Gács, On the maximality of linear codes, Des. Codes Cryptogr., 53 (2009), 59-68. doi: 10.1007/s10623-009-9293-z.
[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-748. doi: 10.4171/JEMS/316.
[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-14. doi: 10.1007/s10623-012-9658-6.
[6]	A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes: Classification by Isometry and Applications, Springer, Berlin, 2006.
[7]	J. Egan and I. M. Wanless, Enumeration of MOLS of small order, Math. Comp., 85 (2016), 799-824. doi: 10.1090/mcom/3010.
[8]	P. Kaski and P. R. J. Östergård, Classification Algorithms for Codes and Designs, Springer, Berlin, 2006.
[9]	P. Kaski and O. Pottonen, Libexact User's Guide, version 1.0, Technical Reports TR 2008-1, Helsinki Inst. Inform. Techn., Helsinki, 2008.
[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-390. doi: 10.1002/jcd.20091.
[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-6492. doi: 10.1109/TIT.2015.2488659.
[12]	J. I. Kokkala and P. R. J. Östergård, Classification of Graeco-Latin cubes, J. Combin. Des., 23 (2015), 509-512. doi: 10.1002/jcd.21400.
[13]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
[14]	B. M. Maenhaut and I. M. Wanless, Atomic Latin squares of order eleven, J. Combin. Des., 12 (2004), 12-34. doi: 10.1002/jcd.10064.
[15]	B. D. McKay, A. Meynert and W. Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007), 98-119. doi: 10.1002/jcd.20105.
[16]	B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput., 60 (2014), 94-112. doi: 10.1016/j.jsc.2013.09.003.
[17]	B. D. McKay and I. M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math., 22 (2008), 719-736. doi: 10.1137/070693874.
[18]	S. Niskanen and P. R. J. Östergård, Cliquer User's guide, Version 1.0, Technical Report T48, Communications Laboratory, Helsinki Univ. Techn., Espoo, 2003.
[19]	P. R. J. Östergård, Constructing combinatorial objects via cliques, in Surveys in Combinatorics 2005 (ed. B. S. Webb), Cambridge Univ. Press, Cambridge, 2005, 57-82. doi: 10.1017/CBO9780511734885.004.
[20]	E. T. Parker, Computer investigation of orthogonal Latin squares of order ten, in Proc. Sympos. Appl. Math., Amer. Math. Soc., Providence, 1963, 73-81.
[21]	V. N. Potapov and D. S. Krotov, On the number of $n$-ary quasigroups of finite order, Discrete Math. Appl., 21 (2011), 575-585. doi: 10.1016/j.disc.2010.09.023.
[22]	B. Segre, Curve razionali normali e $k$-archi negli spazi finiti, Ann. Mat. Pura Appl., 39 (1955), 357-379. doi: 10.1007/BF02410779.

[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]	María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021018
[3]	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
[4]	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
[5]	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
[6]	Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. On the weight distribution of the cosets of MDS codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021042
[7]	Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022 doi: 10.3934/jdg.2022010
[8]	Erick Limas. An application of minimal spanning trees and hierarchical trees to the study of Latin American exchange rates. Journal of Dynamics and Games, 2019, 6 (2) : 131-148. doi: 10.3934/jdg.2019010
[9]	Can Xiang, Jinquan Luo. Some subfield codes from MDS codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021023
[10]	Simeon Ball, Guillermo Gamboa, Michel Lavrauw. On additive MDS codes over small fields. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021024
[11]	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
[12]	Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[13]	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
[14]	Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[15]	Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[16]	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
[17]	Sara D. Cardell, Joan-Josep Climent, Daniel Panario, Brett Stevens. A construction of $ \mathbb{F}_2 $-linear cyclic, MDS codes. Advances in Mathematics of Communications, 2020, 14 (3) : 437-453. doi: 10.3934/amc.2020047
[18]	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
[19]	Shi Wang, Yongqiang Li, Shizhu Tian, Xiangyong Zeng. Four by four MDS matrices with the fewest XOR gates based on words. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021025
[20]	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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Janne I. Kokkala Patric R. J. Östergård
on Google Scholar
Janne I. Kokkala Patric R. J. Östergård

[Back to Top]