American Institute of Mathematical Sciences

Advanced
August  2021, 15(3): 415-422. 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, 2021, 15 (3) : 415-422. 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]

Yun Gao, Shilin Yang, Fang-Wei Fu. Some optimal cyclic $ \mathbb{F}_q $-linear $ \mathbb{F}_{q^t} $-codes. Advances in Mathematics of Communications, 2021, 15 (3) : 387-396. doi: 10.3934/amc.2020072
[2]

Antonio Cossidente, Sascha Kurz, Giuseppe Marino, Francesco Pavese. Combining subspace codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021007
[3]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[4]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[5]

Muhammad Ajmal, Xiande Zhang. New optimal error-correcting codes for crosstalk avoidance in on-chip data buses. Advances in Mathematics of Communications, 2021, 15 (3) : 487-506. doi: 10.3934/amc.2020078
[6]

Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079
[7]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79
[8]

Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003
[9]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002
[10]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133
[11]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[12]

Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135
[13]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077
[14]

Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075
[15]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[16]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[17]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[18]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102
[19]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825
[20]

Izumi Takagi, Conghui Zhang. Existence and stability of patterns in a reaction-diffusion-ODE system with hysteresis in non-uniform media. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3109-3140. doi: 10.3934/dcds.2020400

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (80)
  • HTML views (449)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences