×

Constructing error-correcting binary codes using transitive permutation groups. (English) Zbl 1403.94109

Summary: Transitive permutation groups are recurrent in the study of automorphism groups of combinatorial objects. For binary error-correcting codes, groups are here considered that act transitively on the pairs of coordinates and coordinate values. By considering such groups in an exhaustive manner and carrying out computer searches, the following new bounds are obtained on \(A_2(n,d)\), the maximum size of a binary code of length \(n\) and minimum distance \(d\): \(A_2(17,3)\geq 5632\), \(A_2(20,3)\geq 40960\), \(A_2(21,3)\geq 81920\), \(A_2(22,3)\geq 163840\), \(A_2(23,3)\geq 327680\), \(A_2(23,9)\geq 136\), and \(A_2(24,5)\geq 17920\).

MSC:

94B05 Linear codes (general theory)
05B30 Other designs, configurations

Software:

GAP; Cliquer
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agrell, E.; Vardy, A.; Zeger, K., A table of upper bounds for binary codes, IEEE Trans. Inform. Theory, 47, 3004-3006 (2001) · Zbl 1003.94045
[2] Bose, R. C.; Ray-Chaudhuri, D. K., On a class of error correcting binary group codes, Inf. Control, 3, 68-79 (1960) · Zbl 0104.36402
[3] Cannon, J. J.; Holt, D. F., The transitive permutation groups of degree 32, Exp. Math., 17, 307-314 (2008) · Zbl 1175.20004
[4] Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A., Covering Codes (1997), North-Holland: North-Holland Amsterdam · Zbl 0874.94001
[5] Elssel, K.; Zimmermann, K.-H., Two new nonlinear binary codes, IEEE Trans. Inform. Theory, 51, 1189-1190 (2005) · Zbl 1296.94174
[7] Gijswijt, D. C.; Mittelmann, H. D.; Schrijver, A., Semidefinite code bounds based on quadruple distances, IEEE Trans. Inform. Theory, 58, 2697-2705 (2012) · Zbl 1365.94623
[8] Hashim, A. A.; Pozdniakov, V. S., Computerised search for binary linear codes, Electron. Lett., 12, 350-351 (1976)
[9] Hulpke, A., Constructing transitive permutation groups, J. Symb. Comput., 39, 1-30 (2005) · Zbl 1131.20003
[10] Kabatyanskii, G. A.; Panchenko, V. I., Unit sphere packings and coverings of the hamming space, Probl. Peredach. Inform., 24, 3-16 (1988), (in Russian). English translation in: Probl. Inform. Trans. 24 (1988) 261-272 · Zbl 0679.94015
[11] Kaikkonen, M. K., Codes from affine permutation groups, Des. Codes Cryptogr., 15, 183-186 (1998) · Zbl 0917.94016
[12] Kaski, P.; Östergård, P. R.J., Classification Algorithms for Codes and Designs (2006), Springer: Springer Berlin · Zbl 1089.05001
[13] Litsyn, S., An updated table of the best binary codes known, (Pless, V. S.; Huffman, W. C.; Brualdi, R. A., Handbook of Coding Theory. Vol. I (1998), North-Holland: North-Holland Amsterdam), 463-498 · Zbl 0968.94019
[14] Litsyn, S.; Mounits, B., Improved lower bounds on sizes of single-error correcting codes, Des. Codes Cryptogr., 42, 67-72 (2007) · Zbl 1128.94011
[15] MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), North-Holland: North-Holland Amsterdam · Zbl 0369.94008
[16] Milshtein, M., A new binary code of length 16 and minimum distance 3, Inform. Process. Lett., 115, 975-976 (2015) · Zbl 1337.94108
[17] Mounits, B.; Etzion, T.; Litsyn, S., Improved upper bounds on sizes of codes, IEEE Trans. Inform. Theory, 48, 880-886 (2002) · Zbl 1061.94083
[18] Mounits, B.; Etzion, T.; Litsyn, S., New upper bounds on codes via association schemes and linear programming, Adv. Math. Commun., 1, 173 (2007) · Zbl 1207.94087
[19] Niskanen, S.; Östergård, P. R.J., Cliquer User’s Guide, Version 10, Communications Laboratory, Tech. Rep. T48 (2003), Helsinki University of Technology: Helsinki University of Technology Espoo, Finland
[20] Östergård, P. R.J., Two new four-error-correcting binary codes, Des. Codes Cryptogr., 36, 327-329 (2005) · Zbl 1158.94419
[21] Östergård, P. R.J., On the size of optimal three-error-correcting binary codes of length 16, IEEE Trans. Inform. Theory, 57, 6824-6826 (2011) · Zbl 1365.94527
[22] Östergård, P. R.J.; Baicheva, T.; Kolev, E., Optimal binary one-error-correcting codes of length 10 have 72 codewords, IEEE Trans. Inform. Theory, 45, 1229-1231 (1999) · Zbl 0958.94040
[23] Östergård, P. R.J.; Kaikkonen, M. K., New single-error-correcting codes, IEEE Trans. Inform. Theory, 42, 1261-1262 (1996) · Zbl 0864.94029
[24] Sloane, N. J.A.; Whitehead, D. S., New family of single-error correcting codes, IEEE Trans. Inform. Theory, 16, 717-719 (1970) · Zbl 0206.21201
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.