Last modified on August 23, 1999

Table of the best currently known lower and upper bounds on the smallest size of a covering code


Below we present tables with the best known bounds on the size of binary covering codes of length up to 33 and covering radius up to 10. The table is based on Table 6.1 from
G.Cohen, I.Honkala, S.Litsyn, A.Lobstein "Covering Codes", Elsevier, 1997.

Please send any improvements to Simon Litsyn

Go to the table for R= 1,2,3 | 4,5,6 | 7,8,9,10 | Key to the table



Bounds on K(n,R), R=1,2,3
nR=1 R=2R=3
1 1
2 2 1
3 2 2 1
4 c 4 L 2 2
5 c 7 S 2 2
6 f 12 S c 4 L 2
7 a 16 L c 7 Q 2
8 d 32 L p 12 Q c 4 L
9 t 57-62 W q 16 L c 7 Q
10 h 105-120 X s 24-30 Y h 9-12 Q
11 t 180-192 S s 37-44 R h 12-16 L
12 d 342-380 T s 62-78 T i 18-28 T
13 b 598-736 T g 97-128 L j 28-42 T
14 m 1172-1408 T b 157-256 L j 44-64 L
15 a 2048 L s 310-384 U j 70-112 R
16 d 4096 L h 512-768 P s 115-192 T
17 t 7414-8192 L b 859-1536 P s 187-320 T
18 d 14564-16384 L h 1702-2944 T i 316-512 L
19 r 26270-31744 R g 2897-4096 L s 513-1024 L
20 s 52618-63488 P s 5330-8192 L d 889-2048 L
21 r 95403-122880 R d 9893-14336 U g 1475-3072 Q
22 d 190651-245760 P s 17336-24576 U s 2544-4096 L
23 t 352736-393216 R s 30686-32768 U a 4096 L
24 d 699051-786432 P d 60350-65536 P s 8125-8192 L
25 r 1290826-1556480 R g 107203-131072 P h 13896-16384 L
26 d 2581111-3112960 P s 190823-262144 P s 24256-32768 L
27 r 4793959-6029312 R s 380496-524288 L s 40683-65536 L
28 s 9587084-12058624 P s 683972-1048576 L s 80815-131072 L
29 t 17994966-23068672 R s 1231554-2097152 L g 140567-262144 L
30 d 35791395-46137344 P s 2461892-4194304 L g 248218-524288 L
31 a 226L g 4464613-8388480 R s 443515-524288 U
32 d 227 L s 8170308-16776960 P d 854890-1048576 P
33 r 252648562-268435456 L d 16207424-32505856 Q g 1516050-2097152 P

Go to the table for R= 1,2,3 | 4,5,6 | 7,8,9,10 | Key to the table

Bounds on K(n,R), R=4,5,6
nR=4 R=5R=6
4 1
5 2 1
6 2 2 1
7 2 2 2
8 2 2 2
9 2 2 2
10 c 4 L 2 2
11 c 7 Q 2 2
12 c 8-12 Q c 4 L 2
13 h 11-16 L c 7 Q 2
14 s 16-28 Q c 8-12 Q c 4 L
15 i 22-32 V g 9-16 L c 7 Q
16 i 33-64 L g 13-28 Q c 8-12 Q
17 j 52-112 Q i 19-32 Q c 8-16 L
18 h 83-192 Q i 27-64 L s 12-28 Q
19 j 128-256 L i 40-64 L i 16-32 Q
20 j 208-512 L j 62-128 L h 23-64 L
21 j 336-896 Q j 95-256 L j 33-64 L
22 j 553-1536 Q j 150-512 L j 49-128 L
23 s 912-2048 L j 235-640 U j 73-224 Q
24 j 1505-4096 L j 376-1024 L j 113-384 Q
25 s 2558-4096 L j 608-2048 L j 172-512 L
26 s 4273-8192 L j 981-4096 L s 273-1024 L
27 s 7181-14336 Q j 1601-4096 L j 419-1984 Q
28 s 12482-24576 Q s 2646-8192 L j 663-3584 Q
29 j 21098-32768 L s 4355-14336 Q j 1068-4096 L
30 d 37973-65536 L j 7307-24576 Q j 1727-8192 L
31 g 64680-126976 Q j 12220-32768 L j 2808-14336 Q
32 g 110215-245760 Q j 20556-61440 Q j 4597-24576 Q
33 s 193704-393216 Q j 34731-90112 Q j 7476-32768 L

Go to the table for R= 1,2,3 | 4,5,6 | 7,8,9,10 | Key to the table

Bounds on K(n,R), R=7,8,9,10
nR=7 R=8R=9R=10
7 1
8 2 1
9 2 2 1
10 2 2 2 1
11 2 2 2 2
12 2 2 2 2
13 2 2 2 2
14 2 2 2 2
15 2 2 2 2
16 c 4 L 2 2 2
17 c 7 Q 2 2 2
18 c 8-12 Q c 4 L 2 2
19 c 8-16 L c 7 Q 2 2
20 s 11-28 Q c 8-12 Q c 4 L 2
21 i 14-32 Q c 8-16 L c 7 Q 2
22 j 20-64 L s 10-28 Q c 8-12 Q c 4 L
23 j 29-64 L i 13-32 Q c 8-16 L c 7 Q
24 j 41-128 L i 18-64 L i 9-28 Q c 8-12 Q
25 j 60-224 Q j 25-64 L i 12-32 Q c 8-16 L
26 j 88-384 Q j 35-128 L i 16-56 V s 9-28 Q
27 j 132-512 L j 50-224 Q j 22-64 L i 11-32 Q
28 j 202-960 Q j 73-384 Q g 30-128 L s 15-56 Q
29 j 311-1408 Q j 106-512 L s 43-224 Q i 19-64 L
30 s 484-2048 L j 158-896 Q j 61-384 Q j 27-128 L
31 j 743-2048 L j 238-1344 Q j 88-512 L g 37-224 Q
32 j 1179-4096 L j 366-2048 L j 127-896 Q s 53-384 Q
33 j 1878-8192 L j 557-2048 L j 188-1024 Q j 74-512 L

Go to the table for R= 1,2,3 | 4,5,6 | 7,8,9,10 | Key to the table

Key to Table


All the references below are to theorems, tables and bibliography from
G.Cohen, I.Honkala, S.Litsyn, A.Lobstein "Covering Codes", Elsevier, 1997.

Lower bounds:

a sphere-covering bound
b Corollary 6.1.4
c Theorems 6.2.2, 6.2.5 and 6.2.6 and K(n+1,R) > K(n,R)+1
d Theorem 6.3.8 and 6.4.4
e Theorem 6.3.14
f Stanton and Kalbfleisch [617]
g Theorem 6.4.5 or Honkala [312]
h Theorem 6.5.9 and (6.5.8), or Zhang [704]
i Zhang and Lo [705]
j Li and Chen [423]
k Habsieger [269] !
!> m Habsieger [272]
n Honkala [321]
p Blass and Litsyn [85]
q Östergård and Weakley "Classification of binary covering codes", preprint, 1999
r Haas "Binary and ternary codes of covering radius one: several new lower bounds", preprint, 1998
s Habsieger and Plagne "New lower bounds for covering codes", preprint, 1999
t Blass and Litsyn "Several new lower bounds on the size of codes with covering radius one," IEEE Transactions on Information theory, vol.44, 5, 1998, pp.1998-2002

Upper bounds:

L linear code, see Table 7.1
P K(n+1,R) < 2 K(n,R)+1
Q amalgamated direct sum
R Theorems 3.4.3 and 3.4.5
S piecewise constant code (Section 3.3)
T matrix construction (Theorem 3.5.1) and local search:
    Hämäläinen, Honkala, Kaikkonen and Litsyn [275]: K(12,3) < 29, K(13,3)< 43;
    Hämäläinen, Honkala, Litsyn and Östergård [276]: K(16,3) < 193;
    Östergård [516]: K(12,2) < 79;
    Östergård [522]: K(14,1) < 1409;
    Östergård and Hämäläinen [525]: K(13,1) < 737;
    Exoo in [524], [525], Wille [688]: K(12,1) < 381
    Östergård and Kaikkonen [526]: K(18,2) < 2945, K(17,3) < 321.
U blockwise direct sum:
    Example 3.6.2, Theorems 4.5.4 and 4.5.6; or [526]: K(15,2) < 385, K(23,5) < 641;
V from an Hadamard matrix [526]: K(15,4) < 33, K(26,9) < 57;
W Wille [686], [687], [688]
X Wille [686], [687], Östergård [511]
Y Hämäläinen and Rankinen [278], Östergård and Hämäläinen [525]

Go to the table for R= 1,2,3 | 4,5,6 | 7,8,9,10 | Key to the table