Next Previous Contents

1. Table of general binary codes

The table below gives upper and lower bounds for A2(n,d), the maximum number of vectors in a binary code of word length n and with Hamming distance d.

If d > n then this maximum is 1.
Otherwise, if 3d/2 > n then this maximum is 2.
If d = 1 then this maximum is 2^n.
If d = 2 then this maximum is 2^(n-1).
Furthermore, A2(n-1,2e-1) = A2(n,2e).

Thus, in the table below we may restrict ourselves to even d, between 4 and 2n/3. Horizontally we give d, vertically n.


d=4 d=6 d=8 d=10 d=12 d=14 d=16
6 4 2 1 1 1 1 1
7 8 2 1 1 1 1 1
8 16 2 2 1 1 1 1
9 20 4 2 1 1 1 1
10 40 6 2 2 1 1 1
11 72 12 2 2 1 1 1
12 144 24 4 2 2 1 1
13 256 32 4 2 2 1 1
14 512 64 8 2 2 2 1
15 1024 128 16 4 2 2 1
16 2048 256 32 4 2 2 2
17 2816-3276 256-340 36 6 2 2 2
18 5632-6552 512-673 64-70 10 4 2 2
19 10496-13104 1024-1237 128-131 20 4 2 2
20 20480-26168 2048-2279 256 40 6 2 2
21 40960-43688 2560-4096 512 42-47 8 4 2
22 81920-87333 4096-6941 1024 64-84 12 4 2
23 163840-172361 8192-13674 2048 80-150 24 4 2
24 327680-344308 16384-24106 4096 136-268 48 6 4
25 219-599184 17920-47538 4096-5421 192-466 52-55 8 4
26 220-1198368 32768-84260 4104-9275 384-836 64-96 14 4
27 221-2396736 65536-157285 8192-17099 512-1585 128-169 28 6
28 222-4792950 131072-291269 16384-32151 1024-2817 178-288 56 8

The table above is an updated version of the table from M.R. Best, A.E. Brouwer, F.J. MacWilliams, A.M. Odlyzko & N.J.A. Sloane, Bounds for Binary Codes of Length Less than 25, IEEE Trans. Inf. Th. 24 (1978) 81-93 with (rather trivial) columns for d>10 added.

Since people have asked, we supply some more detail on the system of inequalities used in the above paper.

Improvements since 1978:

A(10,4) = 40 and A(20,4) ≥ 20480, see M.R. Best, Binary codes with a minimum distance of four, IEEE Trans. Inf. Th. 26 (1980) 738-742.

A(11,4) = 72 and A(12,4) = 144, see P.R.J. Östergård, T. Baicheva & E. Kolev, Optimal binary one-error-correcting codes of length 10 have 72 codewords, IEEE Trans. Inform. Theory 45 (1999) 1229-1231.

A(17,4) ≥ 2720, see A.M. Romanov, New binary codes of minimal distance 3, Problemy Peredachi Informatsii 19 (1983) 101-102.

A(17,4) ≥ 2816, see Moshe Milshtein, A new binary code of length 16 and minimum distance 3, Information Processing Letters 115 (2015) 975-976.

A(18,4) ≥ 5312, code constructed by T. Etzion (1991). For a description, see G. Cohen, S. Litsyn, A. Lobstein & I. Honkala, Covering codes, 1997, p.58.

A(19,4) ≥ 10496, see H.O. Hämäläinen. Two new binary codes with minimum distance three, IEEE Trans. Inf. Th. 34 (1988) 875.

A(18,4) ≥ 5632 and A(22,4) ≥ 81920 (hence A(21,4) ≥ 40960), see Antti Laaksonen & Patric Östergård, arXiv:1604.06022, Apr 2016. That same paper, in its Jul 2016 version, also has A(24,4) ≥ 327680 and A(24,10) ≥ 136 and A(25,6) ≥ 17920.

A(17,8) = 36, see P.R.J. Östergård, On the size of optimal three-error-correcting binary codes of length 16, preprint, Jan 2011.

A(18,8) ≤ 72 and A(21,10) ≤ 48 and A(22,10) ≤ 88, see C.L.M. van Pul, On bounds on codes, Master's Thesis, Eindhoven, 1982.

A(20,8) = 256, via semidefinite programming by Gijswijt en Schrijver (pers. comm. A. Schrijver, 2009).

The lower bound A(26,8) ≥ 4104 is due to Henk van der Zee (pers. comm., 29 Jan 2012).

A(21,10) ≥ 42, see M.K. Kaikkonen, A new four-error-correcting code of length 20, IEEE Trans. Inf. Th. 35 (1989) 1344.

A(22,10) ≥ 50, A(23,10) ≥ 76, A(28,12) ≥ 178, A(29,10) ≥ 1460. see M.K. Kaikkonen, Codes from affine permutation groups, Des. Codes Cryptogr. 15 (1998) 183-186.

A(22,10) ≥ 64 and A(23,10) ≥ 80, see P.R.J. Östergård, Two new four-error-correcting binary codes, Des. Codes Cryptogr. 36 (2005) 327-329.

A(26,10) ≥ 384, see K. Elssel and K.-H. Zimmermann, Two new nonlinear binary codes, IEEE Trans. Inform. Theory 51 (2005) 1189-1190.

A(25,12) ≤ 56 and A(26,12) ≤ 98 are due to I. Honkala, thesis, 1987.

The values for n in the range 25..28 were taken from E. Agrell, A. Vardy, and K. Zeger, A table of upper bounds for binary codes, IEEE Trans. Inform. Theory 47 (2001) 3004-3006. They also give the bounds A(21,4) ≤ 43689, A(22,6) ≤ 6941 (both improving the previous upper bound by 1 using the "2 mod 4" argument).

The upper bounds A(23,4) ≤ 173015, A(26,6) ≤ 84260, A(27,6) ≤ 157286, A(25,8) ≤ 5557, A(26,8) ≤ 9673, A(26,10) ≤ 990 are from B. Mounits, T. Etzion, and S. Litsyn, Improved upper bounds on sizes of codes, preprint, May 2001.

The upper bounds A(21,4) ≤ 43688, A(25,4) ≤ 599184, A(27,6) ≤ 157285, A(26,8) ≤ 9672, A(28,8) ≤ 32204, A(26,10) ≤ 989 are from the published version of this same paper: B. Mounits, T. Etzion, and S. Litsyn, Improved upper bounds on sizes of codes, IEEE Trans. Inform. Theory 48 (2002) 880-886.

The upper bound A(24,4) ≤ 344308 follows from the Johnson bound.

The upper bounds A(19,6) ≤ 1280, A(19,8) ≤ 142, A(20,8) ≤ 274, A(22,10) ≤ 87, A(23,6) ≤ 13766, A(25,6) ≤ 48008, A(25,8) ≤ 5477, A(25,10) ≤ 503, A(26,10) ≤ 859, A(27,8) ≤ 17768, A(28,8) ≤ 32151 are due to A. Schrijver (pers. comm., March 2004). The preprint New code upper bounds from the Terwilliger algebra further improves this to A(25,6) ≤ 47998, but worsens things to A(26,10) ≤ 886.

The upper bounds A(20,8) ≤ 273 and A(25,6) ≤ 47997 are due to Monique Laurent, Strengthened semidefinite programming bounds for codes, Mathematical Programming (B) 109 (2007) 239-261.

The upper bounds A(22,4) ≤ 87333, A(23,4) ≤ 172361, A(25,6) ≤ 47538 are due to B. Mounits, T. Etzion, and S. Litsyn, New Upper Bounds on Codes via Association Schemes and Linear Programming, Advances of Math. in Communications 1 (2007) 173-195.

The upper bounds A(20,4) ≤ 26168 and A(28,4) ≤ 4792950 are due to W. Haas, On the Failing Cases of the Johnson Bound for Error-Correcting Codes, Electron. J. Combin. 15 (2008) #R55.

The upper bounds A(18,6) ≤ 673, A(19,6) ≤ 1237, A(20,6) ≤ 2279, A(23,6) ≤ 13674, A(19,8) ≤ 135, A(20,8) = 256, A(25,8) ≤ 5421, A(26,8) ≤ 9275, A(27,8) ≤ 17099, A(21,10) ≤ 47, A(22,10) ≤ 84, A(24,10) ≤ 268, A(25,10) ≤ 466, A(26,10) ≤ 836, A(27,10) ≤ 1585, A(28,10) ≤ 2817, A(25,12) ≤ 55, A(26,12) ≤ 96 are due to D.C. Gijswijt, H.D. Mittelmann & A. Schrijver, Semidefinite code bounds based on quadruple distances, IEEE Trans. Inform. Theory 58 (2012) 2697-2705.

The upper bounds A(18,8) ≤ 71, A(19,8) ≤ 131 are due to Hyun Kwang Kim & Phan Thanh Toan, Improved Semidefinite Programming Bound on Sizes of Codes, arXiv:1212.3467, Dec 2012.

The upper bound A(18,8) ≤ 70 is due to Sven Polak, Improved upper bound on A(18,8), arXiv:1612.02178, Dec 2016.

Corrections and improvements are welcome.

Acknowledgement: Iiro Honkala and Moshe Milshtein contributed several of the above references.

Andries Brouwer - aeb@cwi.nl


Next Previous Contents