American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020074

The $[46, 9, 20]_2$ code is unique

Sascha Kurz

Mathematisches Institut, Universität Bayreuth, D-95440 Bayreuth, Germany

Received  September 2019 Revised  January 2020 Published  April 2020

The minimum distance of all binary linear codes with dimension at most eight is known. The smallest open case for dimension nine is length $ n = 46 $ with known bounds $ 19\le d\le 20 $. Here we present a $ [46,9,20]_2 $ code and show its uniqueness. Interestingly enough, this unique optimal code is asymmetric, i.e., it has a trivial automorphism group. Additionally, we show the non-existence of $ [47,10,20]_2 $ and $ [85,9,40]_2 $ codes.

Keywords: Binary linear codes, optimal codes, divisible codes, non-existence of codes, computer search.
Mathematics Subject Classification: Primary: 94B65; Secondary: 94B05.
Citation: Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, doi: 10.3934/amc.2020074
References:
[1]

L. D. Baumert and R. J. McEliece, A note on the Griesmer bound, IEEE Transactions on Information Theory, IT-19 (1973), 134-135.  doi: 10.1109/tit.1973.1054939.  Google Scholar

[2]

I. Bouyukliev, D. B. Jaffe and V. Vavrek, The smallest length of eight-dimensional binary linear codes with prescribed minimum distance, IEEE Transactions on Information Theory, 46 (2000), 1539-1544.  doi: 10.1109/18.850690.  Google Scholar

[3]

I. G. Bouyukliev, What is $Q$-extension?, Serdica Journal of Computing, 1 (2007), 115-130.   Google Scholar

[4]

I. Bouyukliev and D. B. Jaffe, Optimal binary linear codes of dimension at most seven, Discrete Mathematics, 226 (2001), 51-70.  doi: 10.1016/S0012-365X(00)00125-4.  Google Scholar

[5]

S. Dodunekov, S. Guritman and J. Simonis, Some new results on the minimum length of binary linear codes of dimension nine, IEEE Transactions on Information Theory, 45 (1999), 2543-2546.  doi: 10.1109/18.796403.  Google Scholar

[6]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at: http://www.codetables.de, (2007), Accessed on 2019-04-04. Google Scholar

[7]

J. H. Griesmer, A bound for error-correcting codes, IBM Journal of Research and Development, 4 (1960), 532-542.  doi: 10.1147/rd.45.0532.  Google Scholar

[8]

S. Kurz, Lincode - computer classification of linear codes, arXiv: 1912.09357. Google Scholar

[9]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[10]

J. Simonis, Restrictions on the weight distribution of binary linear codes imposed by the structure of reed-muller codes, IEEE transactions on Information Theory, 40 (1994), 194-196.  doi: 10.1109/18.272480.  Google Scholar

[11]

J. Simonis, The $[23, 14, 5]$ Wagner code is unique, Discrete Mathematics, 213 (2000), 269-282.  doi: 10.1016/S0012-365X(99)00187-9.  Google Scholar

[12]

H. C. A. van Tilborg, The smallest length of binary $7$-dimensional linear codes with prescribed minimum distance, Discrete Mathematics, 33 (1981), 197-207.  doi: 10.1016/0012-365X(81)90166-7.  Google Scholar

[13]

H. N. Ward, Divisible codes - a survey, Serdica Mathematical Journal, 27 (2001), 263-278.   Google Scholar

show all references

References:
[1]

L. D. Baumert and R. J. McEliece, A note on the Griesmer bound, IEEE Transactions on Information Theory, IT-19 (1973), 134-135.  doi: 10.1109/tit.1973.1054939.  Google Scholar

[2]

I. Bouyukliev, D. B. Jaffe and V. Vavrek, The smallest length of eight-dimensional binary linear codes with prescribed minimum distance, IEEE Transactions on Information Theory, 46 (2000), 1539-1544.  doi: 10.1109/18.850690.  Google Scholar

[3]

I. G. Bouyukliev, What is $Q$-extension?, Serdica Journal of Computing, 1 (2007), 115-130.   Google Scholar

[4]

I. Bouyukliev and D. B. Jaffe, Optimal binary linear codes of dimension at most seven, Discrete Mathematics, 226 (2001), 51-70.  doi: 10.1016/S0012-365X(00)00125-4.  Google Scholar

[5]

S. Dodunekov, S. Guritman and J. Simonis, Some new results on the minimum length of binary linear codes of dimension nine, IEEE Transactions on Information Theory, 45 (1999), 2543-2546.  doi: 10.1109/18.796403.  Google Scholar

[6]

M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at: http://www.codetables.de, (2007), Accessed on 2019-04-04. Google Scholar

[7]

J. H. Griesmer, A bound for error-correcting codes, IBM Journal of Research and Development, 4 (1960), 532-542.  doi: 10.1147/rd.45.0532.  Google Scholar

[8]

S. Kurz, Lincode - computer classification of linear codes, arXiv: 1912.09357. Google Scholar

[9]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.  Google Scholar

[10]

J. Simonis, Restrictions on the weight distribution of binary linear codes imposed by the structure of reed-muller codes, IEEE transactions on Information Theory, 40 (1994), 194-196.  doi: 10.1109/18.272480.  Google Scholar

[11]

J. Simonis, The $[23, 14, 5]$ Wagner code is unique, Discrete Mathematics, 213 (2000), 269-282.  doi: 10.1016/S0012-365X(99)00187-9.  Google Scholar

[12]

H. C. A. van Tilborg, The smallest length of binary $7$-dimensional linear codes with prescribed minimum distance, Discrete Mathematics, 33 (1981), 197-207.  doi: 10.1016/0012-365X(81)90166-7.  Google Scholar

[13]

H. N. Ward, Divisible codes - a survey, Serdica Mathematical Journal, 27 (2001), 263-278.   Google Scholar

Table 1.  Number of $ [n,k,\{20,24,28,32\}]_2 $ codes
k/n 20 24 28 30 32 34 35 36 37 38 39 40 41 42 43 44
1 1 1 1 0 1 0 0 0 0 0
2 1 1 2 0 3 0 3 0
3 1 1 2 4 6 9
4 1 4 13 26
5 3 15 163
6 24 3649
7 5 337794
Table Options

Download as excel

k/n 20 24 28 30 32 34 35 36 37 38 39 40 41 42 43 44
1 1 1 1 0 1 0 0 0 0 0
2 1 1 2 0 3 0 3 0
3 1 1 2 4 6 9
4 1 4 13 26
5 3 15 163
6 24 3649
7 5 337794
Table 2.  Number of $ [n,k,\{40,48,56\}]_2 $ codes
k/n 40 48 56 60 64 68 70 72 74 75 76 77 78 79 80 81 82 83
1 1 1 1 0 0 0 0 0 0 0 0 0
2 1 1 2 0 2 0 0 2 0 0
3 1 1 2 0 3 0 5 0
4 1 1 2 3 6 10
5 1 3 11 16
6 2 8 106
7 7 5613
Table Options

Download as excel

k/n 40 48 56 60 64 68 70 72 74 75 76 77 78 79 80 81 82 83
1 1 1 1 0 0 0 0 0 0 0 0 0
2 1 1 2 0 2 0 0 2 0 0
3 1 1 2 0 3 0 5 0
4 1 1 2 3 6 10
5 1 3 11 16
6 2 8 106
7 7 5613
Table 3.  Number of $ [84,8,\{40,48,56\}]_2 $ codes per $ A_{56} $
$ A_{56} $ 3 4 5 6 7 8 9
25773 48792 26091 5198 450 17 1
Table Options

Download as excel

$ A_{56} $ 3 4 5 6 7 8 9
25773 48792 26091 5198 450 17 1
[1]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[2]

Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157
[3]

Joaquim Borges, Ivan Yu. Mogilnykh, Josep Rifà, Faina I. Solov'eva. Structural properties of binary propelinear codes. Advances in Mathematics of Communications, 2012, 6 (3) : 329-346. doi: 10.3934/amc.2012.6.329
[4]

Tatsuya Maruta, Yusuke Oya. On optimal ternary linear codes of dimension 6. Advances in Mathematics of Communications, 2011, 5 (3) : 505-520. doi: 10.3934/amc.2011.5.505
[5]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399
[6]

Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Advances in Mathematics of Communications, 2010, 4 (1) : 69-81. doi: 10.3934/amc.2010.4.69
[7]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295
[8]

Hans-Joachim Kroll, Sayed-Ghahreman Taherian, Rita Vincenti. Optimal antiblocking systems of information sets for the binary codes related to triangular graphs. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020107
[9]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83
[10]

Steven T. Dougherty, Esengül Saltürk, Steve Szabo. Codes over local rings of order 16 and binary codes. Advances in Mathematics of Communications, 2016, 10 (2) : 379-391. doi: 10.3934/amc.2016012
[11]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025
[12]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267
[13]

Daniel Heinlein, Sascha Kurz. Binary subspace codes in small ambient spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 817-839. doi: 10.3934/amc.2018048
[14]

Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195
[15]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[16]

Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363
[17]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163
[18]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039
[19]

Gustavo Terra Bastos, Reginaldo Palazzo Júnior, Marinês Guerreiro. Abelian non-cyclic orbit codes and multishot subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 631-650. doi: 10.3934/amc.2020035
[20]

Tsonka Baicheva. All binary linear codes of lengths up to 18 or redundancy up to 10 are normal. Advances in Mathematics of Communications, 2011, 5 (4) : 681-686. doi: 10.3934/amc.2011.5.681

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (31)
  • HTML views (273)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences