Covering Radius

Richard A. Brualdi  Simon Litsyn  Vera S. Pless

May 9, 1997

1 Introduction

The covering radius is a fundamental parameter of a code. It characterizes the maximal error correcting capability in the case of minimum distance decoding. Codes with small covering radius find applications in data compression. The study of the covering radius began in the early 60’s. Since then the subject has generated a great deal of interest. For earlier surveys see Mattson and Schatz [120], Cohen, Karpovsky, Mattson and Schatz [31], van Lint [108] and Cohen, Litsyn, Lobstein and Mattson [33]. The subject is treated in detail in the monograph [30] by Cohen, Honkala, Litsyn and Lobstein.

We begin by recalling some basic facts from Chapter 1 about the covering radius.

Let C ⊆ F_{q}^{n} be a code of length n over the field F_{q} of q elements (if q = 2, q is usually omitted). We say that a vector in F_{q}^{n} is r-covered by C, if it has distance r or less from at least one codeword. The covering radius ρ = ρ(C) of C is the smallest integer r such that every vector in F_{q}^{n} is r-covered. A code C having covering radius ρ is called a ρ-covering.

Let d be the minimum distance between distinct codewords of C. Then

ρ ≥ ⌊\frac{d − 1}{2}⌋

with equality if and only if C is a perfect code. If C is extended perfect, then ρ = d/2. Since the union of the spheres of radius ρ centered at codewords contains all of F_{q}^{n}, we have the following sphere covering bound for the covering radius of C:

ρ ≥ min{r : V_{q}(n, r)|C| ≥ q^{n}}.

Here V_{q}(n, r) denotes the size of the Hamming sphere,

V_{q}(n, r) = ∑_{i=0}^{r} \binom{n}{i}(q − 1)^{i};

in the binary case q is omitted.

For linear codes we have the following characterizations of covering radius [Theorem 2.15, Chapter 1].

Theorem 1.1 Let C be a linear code with an m × n parity check matrix H. Then

(i) ρ(C) is the weight of the coset of C of largest weight;

(ii) ρ(C) is the smallest number r such that every syndrome (vector in F_{q}^{m}) is a linear combination of r or fewer columns of H.

□

Defining a coset C(v) of a nonlinear code C to be a translate v + C of C we observe that part (i) of Theorem 1.1 holds for nonlinear codes as well. An evident corollary of part (ii) is the following.

Corollary 1.2 (Redundancy bound) For every [n, k] code C

ρ(C) ≤ n − k.
□

The following result is proved in [Theorem 2.17, Chapter 1].

Theorem 1.3 Let C be an [n, k] code over F_{q}. Let Ĉ be the extension of C, and let C^{∗} be a code obtained from C by puncturing on some coordinate. Then the following hold:

(i) If C = C_{1} ⊕ C_{2}, then ρ(C) = ρ(C_{1}) + ρ(C_{2});

(ii) ρ(C^{∗}) = ρ(C) or ρ(C^{∗}) = ρ(C) − 1;

(iii) ρ(Ĉ) = ρ(C) or ρ(Ĉ) = ρ(C) + 1;

(iv) Assume that q = 2. If x is a coset leader of C then (x, 1) is a coset leader of Ĉ, in particular, ρ(Ĉ) = ρ(C) + 1;

(v) Assume that c is a coset leader of C. If a vector c′ ∈ F_{q}^{n} is obtained from c by changing some of its nonzero components to zero, then c′ is also a coset leader of C.

□

The following upper bound for the covering radius is proved in [Theorem 10.10, Chapter 1].

Theorem 1.4 (Delsarte bound) Let C be an [n, k] code over F_{q}. Assume that there are s distinct nonzero weights in C^{⊥}. Then ρ(C) ≤ s. □

The fundamental problems for covering radius can be stated as follows:

(CR1) Given a positive integer n and an integer r with 0 ≤ r ≤ n, find a code C ⊆ F_{q}^{n} of smallest cardinality K_{q}(n, r) (of smallest dimension k_{q}[n, r] if C is restricted to be linear) with covering radius equal to r. Less formally, one wishes to find codes with ‘good covering properties’. When investigating codes from the point of view of covering properties, it is common to use the terminology of covering codes.

(CR2) Given a positive integer n and an integer K with 1 ≤ K ≤ q^{n} (an integer k with 0 ≤ k ≤ n if C is restricted to be linear), find a code C ⊆ F_{q}^{n} of cardinality K whose covering radius t_{q}(n, K) (t_{q}[n, k] if C is restricted to be linear) is smallest. (The covering radius function or t-function was first defined in [31] and investigated in detail in [55].)

Let m and r be integers with 1 ≤ r ≤ m. The length function ℓ_{q}(m, r), first defined in [17], is the smallest length n of a linear code C ⊆ F_{q}^{n} with codimension m and covering radius r. The direct sum of the Hamming code of codimension m − r + 1 over F_{q} and the zero code of length r − 1 is a code of codimension m whose covering radius equals r. Hence ℓ_{q}(m, r) is well-defined if 1 ≤ r ≤ m. Clearly, t_{q}[n, k] = r implies that ℓ_{q}(n − k, r) ≤ n, and ℓ_{q}(m, r) = n implies that t_{q}[n, n − m] ≤ r. It follows that

(i) ℓ_{q}(m, r) equals the smallest integer n such that t_{q}[n, n − m] = r; and

(ii) t_{q}[n, k] equals the smallest integer r such that ℓ_{q}(n − k, r) ≤ n.

Hence knowing all the values of ℓ_{q}(m, r) we can determine all the values of t_{q}[n, k], and vice-versa. Thus while the length function and the t-function contain the same information, this information is presented more compactly for moderate lengths by the length function. Indeed knowing ℓ_{q}(m, 1), ℓ_{q}(m, 2), …, ℓ_{q}(m, m) allows us to determine t_{q}[m + j, j] for every integer j ≥ 0.

We will be using the following notation. A code of length n, size M, minimum distance d and covering radius ρ will be denoted (n, M, d)ρ. A corresponding linear code of size M = 2^{k} will be denoted [n, k, d]ρ. If the parameters d or ρ are not relevant, they are omitted. So, for instance, (n, M)ρ stands for a code of length n, size M and covering radius ρ without minimum distance specified.

The following lemma is sometimes useful for obtaining a lower bound on the covering radius of a code.

Lemma 1.5 (Supercode Lemma ) Let C and C′ be codes with C ⊂ C′ and let D(C′, C) be the maximum distance of a vector in C′ to C. Then ρ(C) ≥ D(C′, C).

If C and C′ are linear codes, then ρ(C) ≥ min{wt(x) : x ∈ C′ \ C} Proof. There exists a vector c′ of C′ such that for each codeword c of C, we have d(c′, c) ≥ D(C′, C). Hence ρ(C) ≥ D(C′, C). If both C′ and C are linear, D(C′, C) has the value given in the statement of the lemma. □

2 Direct sum and normality

The covering radius of the direct sum of two codes is described in (i) of Theorem 1.3. The direct sum can be implemented in a more efficient way if the constituent codes are normal . This property and its generalizations are discussed in this section.

We restrict ourselves to binary codes. Let C be a binary code of length n. Let

C^{a,(i)} = {c_{1}c_{2} ⋯ c_{n} ∈ C | c_{i} = a} (a = 0, 1; i = 1, 2, …, n)

be the subset of C consisting of those codewords whose i^{th} coordinate equals a. The norm of C with respect to coordinate i is defined by

N^{(i)}(C) = max{d(x, C^{0,(i)}) + d(x, C^{1,(i)}) | x ∈ F_{2}^{n}} (i = 1, 2, …, n),

where we use the convention that d(x, ∅) = n. Clearly, N^{(i)}(C) ≤ 2(ρ(C) + 1). The norm of C is defined by

N(C) = min{N^{(i)}(C) : 1 ≤ i ≤ n}.

Coordinate i is acceptable provided that N^{(i)}(C) = N(C). A binary code C is normal [55, 36] provided N(C) ≤ 2ρ(C) + 1. A code that is not normal is called abnormal .

Lemma 2.1 Let C be a binary code. Then

ρ(C) ≤ ⌊\frac{N(C)}{2}⌋ .  (1)

If C is normal, then N(C) = 2ρ(C) or 2ρ(C) + 1.

Proof. Without loss of generality, we assume that the first coordinate is acceptable. For each vector x we have

d(x, C) = min\{d(x, C^{0,(1)}), d(x, C^{1,(1)})\} ≤ \frac{d(x, C^{0,(1)}) + d(x, C^{1,(1)})}{2} ≤ \frac{N(C)}{2}.

Hence (1) holds. Now assume that C is normal, and choose x so that d(x, C) = ρ(C). Then d(x, C^{0,(1)}) ≥ ρ(C) and d(x, C^{1,(1)}) ≥ ρ(C). Therefore N(C) ≥ 2ρ(C). Since C is normal, N(C) ≤ 2ρ(C) + 1 and the lemma follows. □

Now let C_{1} and C_{2} be binary codes of lengths n_{1} and n_{2}, respectively. Then clearly their direct sum

C_{1} ⊕ C_{2} = {(c_{1}, c_{2}) | c_{1} ∈ C_{1}, c_{2} ∈ C_{2}}

is a binary code of length n_{1} +n_{2} satisfying |C_{1} ⊕C_{2}| = |C_{1}||C_{2}| and ρ(C_{1} ⊕C_{2}) ≤ ρ(C_{1}) + ρ(C_{2}). The amalgamated direct sum , abbreviated ADS , of C_{1} and C_{2} (with respect to the last coordinate of C_{1} and the first coordinate of C_{2}) is the code A ∪ B of length n_{1} + n_{2} − 1 where

A = {(a, 0, b) : (a, 0) ∈ (C_{1})^{0,(n_{1})}, (0, b) ∈ (C_{2})^{0,(1)}}

and

B = ∪{(a, 1, b) : (a, 1) ∈ (C_{1})^{1,(n_{1})}, (1, b) ∈ (C_{2})^{1,(1)}}

with

|(C_{1})^{0,(n_{1})}||(C_{2})^{0,(1)}| + |(C_{1})^{1,(n_{1})}||(C_{2})^{1,(1)}|

codewords. Now assume that C_{1} and C_{2} are linear codes. Let H_{1} = [H′_{1} h′] be a parity check matrix of C_{1} and let H_{2} = [h′′ H′′_{2}] be a parity check matrix of C_{2}. Then the ADS of C_{1} and C_{2} is a linear code with parity check matrix

[ \begin{matrix}H′_{1} & h′ & O \\ O & h′′ & H′′_{2} \end{matrix} ] .

With the above notation we have the following theorem of Graham and Sloane [55] (the linear case) and Cohen, Lobstein and Sloane [36] (the general case).

Theorem 2.2 Assume that C_{1} and C_{2} are normal codes of lengths n_{1} and n_{2}, respectively, with the last coordinate of C_{1} acceptable and the first coordinate of C_{2} acceptable. Assume also that each of the sets (C_{1})^{0,(n_{1})}, (C_{1})^{1,(n_{1})}, (C_{2})^{0,(1)} and (C_{2})^{1,(1)} is nonempty. Then the covering radius of the ADS C of C_{1} and C_{2} is less than or equal to ρ(C_{1}) + ρ(C_{2}). Moreover, N^{(n_{1})}(C) ≤ N^{(n_{1})}(C_{1}) + N^{(1)}(C_{2}) − 1 and the n_{1}^{th} coordinate of C is acceptable. If the covering radius of C equals ρ(C_{1}) + ρ(C_{2}), then C is also normal.

Proof. It follows from definitions that for z = (x, 0, y) in F_{2}^{n_{1}+n_{2}−1},

d(z, C^{0,(n_{1})}) = d((x, 0), C_{1}^{0,(n_{1})}) + d((0, y), C_{2}^{0,(1)}),

and

d(z, C^{1,(n_{1})}) = d((x, 0), C_{1}^{1,(n_{1})}) + d((0, y), C_{2}^{1,(1)}) − 1.

Therefore

d(z, C^{0,(n_{1})}) + d(z, C^{1,(n_{1})}) ≤ N^{(n_{1})}(C_{1}) + N^{(1)}(C_{2}) − 1.

A similar conclusion holds for vectors (x, 1, y) in F_{2}^{n_{1}+n_{2}−1}, proving the norm assertion in the theorem.

Using Lemma 2.1 we now calculate that

2ρ(C) ≤ N(C) ≤ N(C_{1}) + N(C_{2}) − 1
≤ 2ρ(C_{1}) + 2ρ(C_{2}) + 1

and so ρ(C) ≤ ρ(C_{1})+ρ(C_{2}). Finally, if ρ(C) = ρ(C_{1})+ρ(C_{2}), then the preceding calculation shows that N(C) ≤ 2ρ(C) + 1 and hence C is normal. □

Corollary 2.3 Let C be an [n, k] normal code. Then for each integer i ≥ 1 there exists an [n + 2i, k] normal code whose covering radius equals ρ(C) + i and whose norm equals N(C) + 2i.

Proof. Let C_{1} be the [3, 1] binary repetition code. Then ρ(C_{1}) = 1 and it is easy to check that N(C_{1}) = 3. Hence C_{1} is normal and all coordinates are acceptable. We now apply Theorem 2.2 with C_{2} = C to finish the proof, since the covering radius of the ADS of C_{1} and C_{2} is easily seen to equal ρ(C_{1}) + ρ(C_{2}) = 1 + ρ(C_{2}). □

The reason for the interest in the ADS construction is that it ‘saves’ one coordinate (the ‘overlapping’ coordinate) over the direct sum construction in producing a code whose covering radius is at most equal to the sum of the covering radii of the constituent codes.

Example. Let C be the [7, 4, 3] binary Hamming code. Since C is perfect, ρ(C) = 1. It is easy to check that C is normal and that all coordinates are acceptable. Taking the ADS of C with a code equivalent to C we obtain a code of length 13 and covering radius 2 with the following parity check matrix

[ \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \end{matrix} ]

Considerable effort has been devoted to identifying families of normal codes and to constructing families of (non-linear) abnormal codes. It is conjectured that all linear codes are normal. However, there exist abnormal nonlinear coverings.

The following construction of abnormal coverings has been suggested by Frankl (see [36]). Let B be a code of length n, size at least n, and minimum distance d ≥ 6. Let b_{1}, …, b_{n} be n distinct codewords. Assume that the i-th coordinate of b_{i} is equal to 0. Let S_{i} be the sphere of radius ⌊(d−2)/2⌋, centered at b_{i}, restricted to those vectors whose i-th coordinate is equal to 0.

Theorem 2.4 The code C = F^{n} \ (S_{1} ∪ S_{2} ∪ … ∪ S_{n}) is abnormal.

Proof. If z is not a codeword, then z belongs to a unique S_{i}. Indeed, by the triangle inequality, the S_{i} are disjoint. Let c be obtained from z by changing its i-th coordinate to 1. Then d(c, z) = 1, c ∉ S_{i}, and d(c, b_{i}) ≤ ⌊d/2⌋. Therefore, for all j ≠ i we have d(c, b_{j}) ≥ ⌊d/2⌋. So, c ∉ S_{j}, and c ∈ C. This proves that ρ(C) = 1. For all i, d(b_{i}, C^{0,(i)}) ≥ ⌊d/2⌋ , d(b_{i}, C^{1,(i)}) ≥ 1. So, C has norm at least ⌊d/2⌋ + 1 ≥ 4 = 2ρ(C) + 2, no coordinate is acceptable, and C is not normal. □

The smallest currently known abnormal code is of length 9 and has 118 words and covering radius 1 (see Honkala and Hämäläinen [77]). As a covering code it is quite bad since there exists a (9, 62) code with covering radius 1. Actually, Honkala and Hämäläinen [77] proved that an abnormal code of length 9 and covering radius 1 must have at least 96 codewords. In general, the following lower bound on the size of abnormal codes has been proved [77].

Theorem 2.5 If C is an abnormal (n, M) code then M ≥ K(n, 1) + n, and

M ≥ \frac{2^{n} − nV (n, 2)}{V (n, 1)} + n^{2}.

□

The optimal covering codes are those having the fewest number of words for a given length and covering radius.

Corollary 2.6 All optimal (n, K(n, 1))1 codes are normal. □

Sometimes, knowledge of the minimum distance of a code determinines its normality [49, 86, 160].

Theorem 2.7 Assume that C is an (n, M, d)ρ code. If d ≥ 2ρ, or d = 2ρ − 1 and ρ divides n, then C is normal. □

More can be said about normality of linear codes, see e.g. [36, 55, 83, 98, 140].

Theorem 2.8 A binary linear [n, k, d]ρ code satisfying one of the following is normal:

(i) n ≤ 15;

(ii) k ≤ 5 or n − k ≤ 9;

(iii) d ≤ 4;

(iv) ρ ≤ 3; (v) d ≥ 2ρ − 1.

Proof. We only prove part (iii). Assume d ≤ 3 and that c ∈ C has weight d. Let i be a coordinate in the support of c. Let x ∈ F^{n} be an arbitrary vector, and c′ be the codeword of C closest to x. Since c has weight ≤ 3, then, if d(x, C) ≤ ρ − 1, we have

d(x, c′) + d(x, c + c′) ≤ (ρ − 1) + (ρ + 2) = 2ρ + 1.

So, let d(x, C) = ρ. By the linearity of C we can assume d(x, C^{0,(i)}) = ρ and c′ ∈ C^{0,(i)}. For C to be abnormal it is necessary that d(x, C^{1,(i)}) ≥ ρ + 2. Consequently, x_{i} = 1, otherwise the vector coinciding with x in all coordinates but the i-th is at distance ρ + 1 from C. But then c + c′ agrees with x in the i-th coordinate, and since c has weight d ≤ 3,

d(x, c′) + d(x, c + c′) ≤ ρ + (ρ + 1) = 2ρ + 1.

It is easy to check that normality of a linear code with odd minimum distance yields normality of the extended code, from which the normality of the linear codes with d = 4 also follows.

Notice, that Theorem 2.7 immediately implies that all linear codes with ρ ≤ 2 are normal. Observe also that (iv) follows from (v). □

Normality of some known classes of codes has been studied. Results are summarized in the following theorem (see [55, 83, 90, 78]):

Theorem 2.9 The following codes are normal:

(i) [n, n, 1] codes;

(ii) [n, 1, n] codes;

(iii) [n, n − 1, 2] codes;

(iv) Hamming and extended Hamming codes;

(v) Perfect one-error correcting codes;

(vi) Golay and extended Golay codes;

(vii) Simplex codes;

(viii) First order Reed-Muller codes of length 2^{m} with m even or m = 3, 5, 7;

(ix) Long binary narrow-sense BCH codes.

□

Recall, that the direct sum of any two normal codes is also a normal code. Thus far, we have partitioned a code C into two subcodes according to the

value of vectors in a particular coordinate. A more general definition of partition due to Honkala [68] proves to be useful.

Let C be a code, and C^{0} and C^{1} = C \ C^{0} be its partition into two nonempty subsets. C is said to be subnormal with respect to the partition (C^{0}, C^{1}) if

max{d(x, C^{0}) + d(x, C^{1})|x ∈ F^{n}} ≤ 2ρ(C) + 1.

It is possible to use the amalgamated direct sum construction with two codes, one being normal and another subnormal. Assume C_{1} is an (n_{1}, M_{1})ρ_{1} normal code with the last coordinate acceptable, and C_{2} be an (n_{2}, M_{2})ρ_{2} code subnormal with respect to a partition (C_{2}^{0}, C_{2}^{1}). Then the amalgamated direct sum of C_{1} and C_{2} is the code A ∪ B of length n_{1} + n_{2} − 1 where

A = {(a, b) : (a, 0) ∈ (C_{1})^{0,(n_{1})}, b ∈ C_{2}^{0}},

and

B = {(a, b) : (a, 1) ∈ (C_{1})^{1,(n_{1})}, b ∈ C_{2}^{1}}.

The resulting code has

|(C_{1})^{0,(n_{1})}||C_{2}^{0}| + |(C_{1})^{1,(n_{1})}||C_{2}^{1}|

words, and its covering radius is upperbounded by ρ(C_{1}) + ρ(C_{2}). The proof of the estimate for the covering radius is similar to the proof in the case of two normal codes.

The advantage of this construction is that subnormal codes are more numerous. For example, the following result was proved by Honkala [71].

Theorem 2.10 All binary codes with covering radius one are subnormal. □

In fact, no non-subnormal codes are known, and it is conjectured that all codes are subnormal. If the conjecture is true then the ADS of the normal [3, 1, 3]1 code with an arbitrary (n, M)ρ code gives a (n + 2, M)ρ + 1 code. This tempts one to conjecture that K(n + 2, ρ + 1) ≤ K(n, ρ), ρ ≠ n. In fact, to prove it, it is enough to show that among the optimal covering codes (in particular, linear covering codes) there exists at least one subnormal code. So far the conjecture K(n + 2, ρ + 1) ≤ K(n, ρ) is known to be true for long enough codes for arbitrary ρ, and in case ρ = 1 for all lengths, see [31, 36, 37]. The analogous conjecture for linear codes is: t[n + 2, k] ≤ t[n, k] + 1 for k ≥ 1.

Among other results on subnormality we wish to mention a result of Calderbank [20] who used a counting argument to prove the following

Theorem 2.11 Let C be a binary [n, k]ρ code. If

2^{n−k}(2^{k−⌈(n−ρ)/(ρ+1)⌉} − 1) < 2^{k} − 1,

then C is subnormal. □

The notions of normality and subnormality have been generalized to nonbinary codes [114, 127]. A more general notion of norm, the j-norm, related to a partition into several subcodes was introduced by Honkala [70, 74]. Let C be a binary code of length n that is the union of j subcodes C_{1}, …, C_{j} (not necessary disjoint). The j-norm of C with respect to these subcodes is defined by

N(C) = max{ min_{1≤i≤j}{d(x, C_{i})} + max_{1≤i≤j}{d(x, C_{i})}|x ∈ F_{2}^{n}}.  (2)

This notion is used in the blockwise direct sum construction [70].

Graham and Sloane proposed other constructions generalizing the direct sum and allowing saving more than one coordinate [55].

3 Other constructions

In this section we present some other general constructions of covering codes.

Piecewise constant codes

The piecewise construction was proposed by Cohen, Lobstein and Sloane [36]. Let n = n_{1} + n_{2} + … + n_{s}, where vectors of length n are written as c = (c_{1}, c_{2}, …, c_{s}), for c_{i} ∈ F^{n_{i}}, i = 1, 2, …, s. Let W be a collection of integral vectors (w_{1}, w_{2}, …, w_{s}) of length s with 0 ≤ w_{i} ≤ n_{i}. A piecewise constant code C consists of all vectors c such that (wt(c_{1}), wt(c_{2}), …, wt(c_{s})) ∈ W.

Example. Let n = 5, s = 2, n_{1} = 2, n_{2} = 3, and let W consist of the following four vectors: (0, 0), (0, 3), (1, 0), (2, 2). Then the code C is:

0 0 0 0 0
0 0 1 1 1
1 0 0 0 0
0 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

It is a (5, 7)1 code. To see that the covering radius is indeed 1, we check that for an arbitrary vector x ∈ F^{7}, x = (x_{1}, x_{2}), its weight vector (wt(x_{1}), wt(x_{2})) can be ”approximated” by a vector (w_{1}, w_{2}) from W so that either

wt(x_{1}) = w_{1}, |wt(x_{2}) − w_{2}| ≤ 1,

or

|wt(x_{1}) − w_{1}| ≤ 1, wt(x_{2}) = w_{2}.

No regular method is known to optimize partitioning and choice of W.

Piecewise constant constructions can be used to cover a part of the space while the rest is covered by some alternative method.

Example. Construction of an (11, 192)1 code [36]. It is possible to check that the spheres of radius 1 centered at the 66 blocks of the Steiner system S(4, 5, 11) and their complements cover perfectly all vectors of weight from 4 to 7 in F^{11}. So, we are left with the vectors of weights from 0 to 3 and their complements. To cover them we use the piecewise constant construction with n_{1} = 6, n_{2} = 5 and W consisting of (0, 1), (0, 2) and (2, 0), and (6, 4), (6, 3) and (4, 5).

Variations on the (u, u + v) construction

This construction was proposed independently by Mollard [122] and Katsman and Litsyn (see [36]). Let π(u) = 0 if wt(u) is even and π(u) = 1 otherwise.

Theorem 3.1 Let C be an (n, M)1 code. Then the code

C′ = {(u, u + v, π(u)) : u ∈ F^{n}, v ∈ C}

is a (2n + 1, 2^{n}M)1 code.

Proof. Consider an arbitrary x = (x_{1}, x_{2}, x_{3}), x ∈ F^{2n+1}, x_{1}, x_{2} ∈ F^{n}, x_{3} ∈ F. There is a codeword c ∈ C such that d(x_{1} +x_{2}, c) ≤ 1. If either d(x_{1} +x_{2}, c) = 0 or π(x_{1}) = x_{3}, then

c = (x_{1}, x_{1} + c, π(x_{1}))

satisfies d(x, c) ≤ 1. Otherwise, change x_{1} in one coordinate to obtain a vector x′_{1} such that x′_{1} + x_{2} = c ∈ C, and then π(x′_{1}) = x_{3} and

c′ = (x′_{1}, x′_{1} + c, π(x′_{1}))

satisfies d(c′, x) = 1. □

For example, from the (11, 192)1 code we obtain a (23, 3 · 2^{17})1 code.

Honkala and Hämäläinen [76] suggested the following generalization. Suppose W is a set of s weights included in {0, 1, …, n + 1}, 1 ≤ s ≤ n + 1, W = {w_{1}, w_{2}, …, w_{s}}, with w_{1} < w_{2} < … < w_{s}. Let j be an integer satisfying

w_{i+1} − w_{i} ≤ j + 1 for i = 1, 2, …, s − 1,

w_{1} ≤ \frac{j + 1}{2}; w_{s} ≥ n + 1 − \frac{j + 1}{2}.

Denote by C_{w}^{n+1} the set of all elements in F^{n+1} having weight w. Let C_{1} = ∪_{w∈W} C_{w}^{n+1}, and C_{2} be an (n, M)j code. Finally, define

C = {(u, u + v, u_{0}) : u ∈ F^{n}, (u, u_{0}) ∈ C_{1}, v ∈ C_{2}}.

Theorem 3.2 C is a normal (2n + 1, M ∑_{i=1}^{s} \binom{n}{w_{i}}) j code. □

Example. If j = 1, s = ⌊\frac{n+1}{2}⌋, W = \{0, 2, …, 2 · ⌊\frac{n+1}{2}⌋\}, and C_{2} is an (n, M)1 code, we have the construction of Theorem 3.1.

Let n = 4m − 1, j = 2m − 1, and W = \{m, 3m\}. Hence, |C_{1}| = 2\binom{4m}{m}. Let C_{2} be a repetition code of length n. The resulting code is a normal (8m − 1, 4\binom{4m}{m}) 2m − 1 code. In particular, m = 3 gives K(23, 5) ≤ 880.

Matrix constructions

The idea of the construction (Blokhuis and Lam [11] for ρ = 1, Carnielli [22] and van Lint, Jr. [109] for the general case) is to take as the code a union of cosets of a linear code. Every coset can be defined by its syndrome. Restrictions imposed on the set of the syndromes guarantee that the code is a covering.

Let A = (I_{k}, D) be a k ×n binary matrix, I_{k} being the k ×k identity matrix. A set S ⊆ F^{k} is said to t-cover F^{k} using A if every x ∈ F^{k} can be represented as a sum of exactly one element of S plus a sum of at most t columns of A. In other words, for every x ∈ F^{k} we can find y ∈ F^{n} of weight at most t and s ∈ S such that x = Ay + s.

Theorem 3.3 If S is a ρ-covering of F^{k} using A then the code

C = {c ∈ F^{n} : Ac ∈ S}

is a (n, |S|2^{n−k})ρ binary code.

Proof. Suppose z ∈ F^{n}. We can find a vector y ∈ F^{n} of weight at most ρ such that Az = Ay + s, for some s ∈ S. Then A(z + y) ∈ S, and thus z + y ∈ C, d(z, z + y) ≤ ρ. □

Blockwise direct sum

The following construction, suggested by Honkala [70], and using the notion of j-norm (2), can be easily checked.

Theorem 3.4 Assume that A and B are codes of length n_{A} and n_{B} respectively. Let A be the union of j subcodes A_{1}, …, A_{j}, and B be the union of B_{1}, …, B_{j}. Let the codes A and B have j-norms N_{A} and N_{B}. The blockwise sum of A and B is

C = ∪_{1≤i≤j} {A_{i} ⊕ B_{i}}.

Then the code C has length n_{A} + n_{B}, size ∑_{1≤i≤j} |A_{i}||B_{i}|, and covering radius at most ⌊(N_{A} + N_{B})/2⌋. □

Example. This example is due to Etzion and Greenberg [48]. Let m ≥ 4 be even. It is known that the extended Hamming code A of length 2^{m} can be partitioned into 2^{m−1} translates of the Preparata code. The set B = F^{2^{m−1}−1} can be partitioned into 2^{m−1} translates of the Hamming code of length 2^{m−1}−1. The blockwise direct sum of A and B is the code of length 2^{m} + 2^{m−1} − 1, size 2^{2^{m}+2^{m−1}−2m−1} and covering radius 2. For m = 4 this is an (23, 2^{15})2 code.

Cascading construction

Sometimes it is useful to combine binary and nonbinary coverings using a suitable variant of cascading that gives a code whose length is the product of the lengths of the constituent codes. Let A_{0} be an (n, M_{0})ρ_{0} binary covering code. Let A_{1}, A_{2}, …, A_{q−1} be translates of A_{0} and the code A = A_{0} ∪A_{1} ∪…∪A_{q−1} have covering radius ρ_{A}. Let B ⊆ F_{q}^{n} be an (N, M_{B})ρ_{B} covering, where the elements of F_{q} are denoted by {0, 1, …, q − 1}.

Theorem 3.5 The code

C = ⋃_{(b_{1},b_{2},...,b_{N})∈B} A_{b_{1}} ⊕ A_{b_{2}} ⊕ … ⊕ A_{b_{N}}

is an (nN, M_{0}^{N}M_{B})ρ, ρ ≤ ρ_{B}ρ_{0} + (N − ρ_{B})ρ_{A}, binary covering code.

Proof. Let (x_{1}, x_{2}, …, x_{N}), x_{i} ∈ F^{n}, be arbitrary. For each i choose y_{i} ∈ F_{q} such that d(x_{i}, A_{y_{i}}) ≤ ρ_{A}. Since the covering radius of B is at most ρ_{B}, there exists a word b = (b_{1}, b_{2}, …, b_{N}) ∈ B, whose distance to y = (y_{1}, y_{2}, …, y_{N}) is at most ρ_{B}. Now consider the code A_{b_{1}} ⊕ A_{b_{2}} ⊕ … ⊕ A_{b_{N}}. If y_{i} = b_{i} then d(x_{i}, A_{b_{i}}) ≤ ρ_{A}, otherwise, if y_{i} ≠ b_{i} then d(x_{i}, A_{b_{i}}) ≤ ρ_{0}, and the claim follows.

Example. Let A_{0} be the [3, 1, 3]1 code, and A be the union of its four distinct translates, the [3, 3, 1]0 code. Let B be the quaternary Hamming [N = (4^{m} − 1)/3, N − m, 3]1 code. The resulting code C is the [4^{m} − 1, 4^{m} − 2m − 1]1 binary Hamming code.

Actually, for each of the N coordinates different A_{0} and A may be chosen, and B can be a mixed code (its coordinates are over different alphabets).

Example. Etzion and Greenberg [48] constructed a perfect mixed (17, 2^{11})2 code B with sixteen binary coordinates and one coordinate (say, the last) over the alphabet F_{8}. For the binary coordinates we choose A_{0} to consist of only one word (0) of length one, and A to be the [1, 1]0 code. For the last coordinate we choose as A_{0} the piecewise (5, 7)1 code, and as A_{i} the translates of A_{0} by (0, 0, i_{2}, i_{1}, i_{0}), where (i_{2}, i_{1}, i_{0}) is the binary representation of i, 1 ≤ i ≤ 7. Clearly, A is the (5, 32)1 code. The resulting covering C is a (21, 7 · 2^{11})2 code.

For other applications of the construction see [48, 63, 94, 126].

Simulated annealing

Several best known short covering codes have been found using the technique called simulated annealing. It is a recursive procedure starting from a random (n, M) code C. The optimized function σ(C) is the number of vectors in F^{n} that are not covered by the spheres of radius j centered at the codewords. If σ(C) = 0 then all vectors are covered and the code is actually an (n, M)j covering. The process is implemented in the following way. An initial high ”temperature” T is chosen for the code (for instance, T = n), and then T is slowly lowered (for instance, by multiplying it by 0.9), until it reaches a fixed threshold (for example, T = 0.01n), where the algorithm stops (unless it has succeded before). For each temperature T, the following subprogram is repeated a fixed number of times (unless it succeeds): randomly change C to C′ by changing one coordinate in one codeword; if σ(C′) ≤ σ(C) then accept this transition; otherwise, the change is accepted only if

exp (\frac{σ(C′) − σ(C)}{T}) > r,

for a randomly chosen r ∈ [0, 1]. So, the higher the temperature, the more easily accepted a transition which increases the function σ. The algorithm stops either when a code with σ = 0 has been found, or when temperature T has reached its threshold (the code is frozen).

Examples of codes found by simulated annealing are given in [47, 103, 166]. A ternary (6, 73)1 code was found using an initial temperature 2, reducing factor 0.995, and with 1000 transitions at each temperature. Simulated annealing was used to find relevant matrices in the matrix construction [1, 126, 127, 165].

Linear constructions

The constructions of linear coverings suggested by Davydov et al. [39, 40, 41, 52] employ a recursive technique. Namely, starting from some short [n_{0}, n_{0} − r_{0}]ρ code, we construct a family of [n = 2^{m}n_{0} + N(m), n − r_{0} − mρ]ρ codes, where m ranges from some lower bound m_{0} to infinity, and N(m) ≥ 0.

The basic idea is given by the following construction. Let

H_{0} = [h_{1}, h_{2}, …, h_{n_{0}}]

be the parity check matrix of an [n_{0}, n_{0} − r_{0}]ρ code C_{0}. Suppose there exists a collection of n_{0} matrices H_{i} of size mρ × 2^{m} having the property that for every subset of ρ matrices H_{i_{1}}, H_{i_{2}}, …, H_{i_{ρ}}, we can express any vector from F^{mρ} as a sum of at most ρ columns x_{1} + x_{2} + … + x_{ρ}, where x_{j} is a column of H_{i_{j}}. Let P (h) stand for the 2^{m}-fold repetition of the column h, so P (h) is of size r_{0} × 2^{m}.

Theorem 3.6 The parity check matrix

H = [ \begin{matrix}P (h_{1}) & P (h_{2}) & … & P (h_{n_{0}}) \\ H_{1} & H_{2} & … & H_{n_{0}} \end{matrix} ]

defines an [n = 2^{m}n_{0}, n − r_{0} − mρ]ρ code.

Proof. Consider an arbitrary syndrome vector (y_{1}, y_{2})^{T}, y_{1} ∈ F^{r_{0}}, y_{2} ∈ F^{mρ}. Since the covering radius of C_{0} is ρ, there are at most ρ columns h_{i} summing up to y_{1}^{T}. By the property of H_{i}’s from the corresponding (at most ρ) matrices H_{i} we can take (at most ρ) columns, one from each, summing up to y_{2}^{T}. □

Usually, the matrix H can be further extended by adding N(m) columns with n_{0} first zeros. Algebraic constructions for matrices H_{i} were proposed in [39, 52]. Moreover, if H_{0} is such that every syndrome can be expressed as a sum of at most ρ and at least 0 < ρ_{0} ≤ ρ columns of H_{0}, the construction can be further improved. The following theorem summarizes the parameters of linear codes constructed by this technique.

Theorem 3.7 There exist linear binary codes with the following parameters:

ρ = 2 k = n − 2m,  n = 27 · 2^{m−4} − 1,  for m ≥ 4;
k = n − 2m + 1, n = 5 · 2^{m−2} − 1,  for m ≥ 2.
ρ = 3 k = n − 3m, n = 155 · 2^{m−6} − 2, for m ≥ 6;
n = 76 · 2^{m−5} − 1,  for m ≥ 9;
k = n − 3m + 1, n = 2^{m+1} − 1,  for m ≥ 5;
n = 411 · 2^{m−8} − 2,  for m ≥ 9;
n = 821 · 2^{m−9} − 1,  for m ≥ 14;
k = n − 3m + 2, n = 3 · 2^{m−1} − 1,  for m ≥ 8;
ρ = 4 k = n − 4m, n = 48 · 2^{m−4} − 2, for m ≥ 6;
n = 47 · 2^{m−4} − 1,  for m = 5, m ≥ 11;
k = n − 4m + 1 n = 11 · 2^{m−2} − 2,  for m ≥ 5;
n = 39 · 2^{m−4} − 3,  for m ≥ 11;
n = 1247 · 2^{m−9} − 1, for m = 9, m ≥ 16;
k = n − 4m + 2 n = 19 · 2^{m−3} − 2,  for m ≥ 7;
n = 31 · 2^{m−4} − 2,  for m ≥ 9;
n = 31 · 2^{m−4} − 3,  for m ≥ 11;
n = 991 · 2^{m−9} − 1,  for m ≥ 16;
k = n − 4m + 3 n = 2^{m+1} − 2,  for m ≥ 5;
n = 15 · 2^{m−3} − 2,  for m ≥ 7;
n = 14 · 2^{m−3} − 2,  for m ≥ 9;
n = 14 · 2^{m−3} − 3,  for m ≥ 11;
n = 895 · 2^{m−9} − 1,  for m ≥ 16.
□

4 Lower bounds

In this section we discuss lower bounds on K(n, ρ), the minimum number of words in a covering of radius ρ of length n. The simplest one is the sphere covering bound. Since parameters of all perfect codes are known, in most of the cases this bound can be improved.

Using embedded codes

These bounds were proposed by Cohen, Lobstein and Sloane [36]. The idea is to estimate the maximal number of pairwise nonintersecting spheres centered at the codewords of an (n, M)ρ covering. Let A(n, d) denote the maximal number of codewords in any binary code of length n and minimal distance d.

Theorem 4.1

K(n, ρ) ≥ \frac{2^{n} − A(n, 2ρ + 1)\binom{2ρ}{ρ}}{V (n, ρ) − \binom{2ρ}{ρ}},

provided the denominator is positive.

Proof. Suppose C has covering radius ρ, and let C_{0} be a maximal subcode of C with minimal distance at least 2ρ + 1. The spheres of radius ρ around codewords of C_{0} are disjoint and cover precisely |C_{0}|V (n, ρ) vectors. The rest of the codewords from C\C_{0} cannot cover V (n, ρ) additional vectors since otherwise the code C_{0} is not maximal. The number of vectors covered jointly by two spheres of radius ρ with centers being at distance at most 2ρ is at least \binom{2ρ}{ρ}. So, the total number of covered vectors is

|C_{0}|V (n, ρ) + (|C| − |C_{0}|) (V (n, ρ) − \binom{2ρ}{ρ})

≤ |C| (V (n, ρ) − \binom{2ρ}{ρ}) + A(n, 2ρ + 1)\binom{2ρ}{ρ},

and the claim follows. □

Clearly this bound is always better than the sphere covering bound. Several embedded codes can be used [31].

The balance bound

A code C containing M codewords is balanced if in each coordinate position of the codeword matrix the difference between the number of ones and the number of zeros is at most 1. The optimal covering codes cannot be too ”unbalanced” (actually, it is conjectured that among optimal codes there is at least one that is balanced).

Theorem 4.2 In every (n, M)ρ code C, for all i and a ∈ {0, 1},

|C^{a,(i)}| ≥ \frac{2^{n−1} − MV (n − 1, ρ − 1)}{\binom{n−1}{ρ}}.

Proof. Consider how the vectors with zero in the i-th place are covered. The codewords from C^{0,(i)} each cover V (n−1, ρ) vectors in C^{0,(i)}, and the codewords from C^{1,(i)} each cover V (n − 1, ρ − 1) in C^{0,(i)}. So,

|C^{0,(i)}|V (n − 1, ρ) + |C^{1,(i)}|V (n − 1, ρ − 1) ≥ 2^{n−1}.

Now the claim follows from |C^{0,(i)}| + |C^{1,(i)}| = M. □

Analogous results can be obtained for the pairs of coordinates [31].

Example. We prove K(5, 1) ≥ 7. Assume there exists a (5, 6)1 code. It follows from the theorem that the code has to be balanced. Let us write the codewords in a 6 × 5 array. The array has all distinct columns. Indeed if there are two equal columns, say the first and the second, then the vector (01x_{1}x_{2}x_{3}), where none of the codewords is of the form (∗ ∗ x_{1}x_{2}x_{3}) (there are only six codewords, so such a vector exists) is at distance more than 1 from the code. Without loss of generality assume the first codeword is (00000). There are six inequivalent ways to choose a set of five distinct columns of size 5 with two zeros. None of the corresponding six codes has covering radius 1.

The ”balance” bound was given by by Stanton and Kalbfleisch [147] for ρ = 1, and by Cohen, Lobstein and Sloane [36] in the general case.

Linear programming

The idea [36] is to construct a system of inequalities involving components of the distance distribution.

Suppose a covering (n, M)ρ code C exists. Assume C contains the zero word. Denote by A_{i}(x) = |{c ∈ C : d(c, x) = i}|, i = 0, 1, …, n, the components of the weight distribution of the coset x + C, and by

B_{i} = (1/M) ∑ ; c∈C A_{i}(c)

the components of its distance distribution. Clearly, B_{0} = 1, B_{i} ≥ 0, B_{0} + B_{1} + … + B_{n} = M. The B_{i}’s satisfy the Delsarte inequalities

∑_{i=0}^{n} B_{i}P_{k}(i) ≥ 0,

for k = 0, 1, …, n, where P_{k}(i) is the k-th Krawtchouk polynomial. Other inequalities can be obtained from covering considerations.

Let ρ = 1. Since every vector must be within distance 1 of the code, we have for every x ∈ F^{n}

(n − i + 1)A_{i−1}(x) + A_{i}(x) + (i + 1)A_{i+1}(x) ≥ \binom{n}{i},

for i = 0, 1, …, n (A_{j} = 0 for j ∉ [0, n]). Averaging over x ∈ C we get an analogous inequality for the B_{i}’s.

Summarizing, we formulate the following linear programming problem. Minimize M = B_{0} + B_{1} + … + B_{n} under the constraints

∑_{i=0}^{n} B_{i}P_{k}(i) ≥ 0 for k = 0, 1, …, n;

B_{−1} = B_{n+1} = 0, B_{0} = 1, B_{i} ≥ 0 for i = 0, 1, …, n;

(n − i − 1)B_{i−1} + B_{i} + (i + 1)B_{i+1} − \binom{n}{i} ≥ 0 for i = 0, 1, …, n.

The solution M of this linear programming problem gives a lower bound on K(n, ρ).

For further generalizations see [21, 168, 169, 170].

Excess bounds

The idea of the method is to estimate the number of vectors in F^{n} that are necessarily covered several times. If there are such vectors clearly the sphere covering bound cannot be achieved.

Let C ⊆ F^{n} be a code having covering radius ρ = ρ(C). For x ∈ F^{n} we define the excess E(x) as one less than the number of times x is covered by spheres of radius ρ centered at codewords. So, if a point x is covered once then E(x) = 0. Since C is a ρ-covering, for every x we have E(x) ≥ 0, and

∑_{x∈F^{n}} E(x) = |C|V (n, ρ) − 2^{n}.

The definition of excess can be extended naturally to subsets V ⊆ F^{n}, as E(V) = ∑_{x∈V} E(x). Denote Z_{i} = {x ∈ F^{n} : E(x) = i}.

For example, for n even consider the excess of a code having covering radius one on a sphere B_{1}(x) of radius 1 centered in x. Let A = F^{n} \ C. If x ∈ A then E(B_{1}(x)) ≥ 1. Indeed, if there are two codewords at distance 1 from x, then x is covered twice, otherwise, since the vectors at distance 1 from x must be covered, there are at least n/2 codewords at distance 2 from x, and there is at least one vector at distance one from x which is covered at least twice. Therefore,

2^{n} − |C| ≤ ∑_{x∈A} E(B_{1}(x)) = ∑_{x∈A} ∑_{i>0} i|Z_{i} ∩ B_{1}(x)|

= ∑_{i>0} i ∑_{z∈Z_{i}} |A ∩ B_{1}(z)| ≤ (n − 1) ∑_{i>0} i|Z_{i}| = (n − 1)(|C|V (n, 1) − 2^{n}).

The last inequality is by

|A ∩ B_{1}(z)| = V (n, 1) − i − 1 ≤ n − 1

for z ∈ Z_{i}, i > 0.

This proves the following result of van Wee [159].

Theorem 4.3 For n even

K(n, 1) ≥ 2^{n}/n.
□

The direct sum of a Hamming code and F = {0, 1} gives [2^{m}, 2^{m} −m]1 codes attaining this bound.

Corollary 4.4

K(2^{m}, 1) = 2^{2^{m}−m}.
□

Now consider excess on the spheres of radius s > 1. Assume n+1 is divisible by an odd prime s + 1. Noticing that the spheres of radius one and s intersect in s + 1 or n + 1 points (if they intersect), we conclude that

E(B_{s}(x)) = −V (n, s) mod (s + 1) = −1 mod (s + 1).

Therefore, E(B_{s}(x)) ≥ s, and

2^{n}s ≤ ∑_{x∈F^{n}} E(B_{s}(x)) = V (n, s) ∑_{x∈F^{n}} E(x) = V (n, s)(|C|(1 + n) − 2^{n}),

that proves the following result of Honkala [75]:

Theorem 4.5 If n + 1 is divisible by an odd prime s + 1, then

K(n, 1) ≥ \frac{(V (n, s) + s)2^{n}}{V (n, s)(n + 1)} .

□

Choosing s = 2 we get [159]:

Corollary 4.6 If n = 2 ( mod 3),

K(n, 1) ≥ \frac{(V (n, 2) + 2)2^{n}}{V (n, 2)(n + 1)} .

□

This was improved by Honkala in [72]:

Theorem 4.7 If n = 5 ( mod 6),

K(n, 1) ≥ \frac{(V (n, 2) + 5)2^{n+1} − 9A(n, 3)(n + 1)}{(2V (n, 2) − 3)(n + 1)}.

□

The excess arguments can be generalized to arbitrary covering radius. Consider a vector x such that d(x, C) = ρ. Shifting the code by x we necessarily have a codeword of weight ρ. To cover all vectors of weight one we need at least ⌈(n − ρ)/(ρ + 1)⌉ extra vectors of weight ρ or ρ + 1. So, all in all, there are at least ⌈(n+1)/(ρ+1)⌉ codewords of weight ρ or ρ+1. Each of them covers ρ+1 vectors from B_{1}(x). So, for every x, such that d(x, C) = ρ,

E(B_{1}(x)) = (ρ + 1)⌈(n + 1)/(ρ + 1)⌉ − (n + 1).

Using arguments analogous to those used to prove Theorem 4.3 we get

Theorem 4.8 If n > ρ, then

K(n, ρ) ≥ \frac{(n − ρ + ε)2^{n}}{(n − ρ)V (n, ρ) + εV (n, ρ − 1)},

where ε = (ρ + 1)⌈(n + 1)/(ρ + 1)⌉ − (n + 1). □

There are many further generalizations based on considering the excess on the spheres of greater radius. We will mention the following one due to Honkala [69].

Theorem 4.9 If ρ ≥ 2, n ≥ 2ρ + 1 and

ε = (ρ + 1)⌈(n + 1)/(ρ + 1)⌉ − (n + 1) ≤ ρ − 1,

then

K(n, ρ) ≥ \frac{(τ + ε)2^{n}}{τV (n, ρ) + εV (n, ρ − 1)},

where

τ = \{ \begin{matrix}n − 3 + 2/n & if & ρ = 2 \\ n − ρ − 1 & if & ρ ≥ 3. \end{matrix}

□

For other bounds see [21, 23, 56, 57, 68, 69, 72, 84, 85, 107, 137, 149, 150, 163, 168, 169, 170].

Bounds for short coverings

The following estimates are valid for codes of small size.

Theorem 4.10 For all ρ ≥ 1,

(i) K(n, ρ) = 2 if ρ + 1 ≤ n ≤ 2ρ + 1;

(ii) K(2ρ + 2, ρ) = 4;

(iii) K(2ρ + 3, ρ) = 7;

(iv) 8 ≤ K(2ρ + 4, ρ) ≤ 12.

Proof. (i) is evident; the upper bound on (ii) is obtained from a linear construction, the lower bound is by the balance bound; (iii) is by a piecewise construction, and the linear programming bound. The upper bound in (iv) is by a piecewise construction (see [36]). The lower bound is a combination of the sphere covering bound for small ρ and induction. □

The best known upper and lower bounds for codes of length n ≤ 33 and ρ ≤ 3 (see for references [30, 33]) are summarized in Table 1.

5 Upper bounds on the covering radius

In this section we study upper bounds on the covering radius. It is necessary to distinguish between finding constructive upper bounds for the minimum covering radius given the length and size of a code (the functions t(n, K) and t[n, k]) and the considered problem. Here, given length, size and maybe distance we wish to estimate the maximal possible value of the covering radius, i.e. to find in a sense the worst covering.

Let H be a parity check matrix of a linear code C in the standard form H = (I_{n−k}|P).

Theorem 5.1 Let j be the maximal weight of a column of P, then

ρ(C) ≤ ⌈j/2⌉ + (n − k − j).

Proof. Without loss of generality the code has parity check matrix

H = ( \begin{matrix}I_{j} & & 1 1 ⋮ 1 & ∗ & ∗ \\ & 0 & & ∗ & I_{n−k−j} \end{matrix} ) .

Table 1: Table of lower and upper bounds for K(n, ρ), 1 ≤ n ≤ 33, 1 ≤ ρ ≤ 3.

n ρ = 1  ρ = 2  ρ = 3
1 1
2 2  1
3 2  2  1
4 4  2  2
5 7  2  2
6 12  4  2
7 16  7  2
8 32  12  4
9 55–62  15–16  7
10 105–120  23–30  9–12
11 178–192  36–44  12–16
12 342–380  61–78  18–28
13 598–736  97–128  28–42
14 1172–1408  157–256  44–64
15 2048  309–480  70–112
16 4096  512–768  114–192
17 7399–8192  859–1536  186–320
18 14564–16384  1702–2944  316–512
19 26261–31744  2897–4096  511–1024
20 52456–63488  5328–8192  889–2048
21 95330–122880  9893–14336  1475–3072
22 190651–245760  17316–24576  2539–4096
23 352448–393216  30677–32768  4096
24 699051–786432  60350–65536  8123–8192
25 1290562–1556480  107203–131072  13896–16384
26 2581111–3112960  190775–262144  24210 – 32768
27 4793641–6029312  380328–524288  40675–65536
28 9587064–12058624 683910–1048576 80720–131072
29 17988086–23068672 1231356–2097152 140567–262144
30 35791395–46137344 2461754–4194304 248218–524288
31 2^{26}  4464613–8388480 443248–524288
32 2^{27} 8168458–2^{24} 854890–2^{20}
33 252645140–2^{28}  16207424–31 · 2^{20} 1516050–2^{21}

Denote by H_{1} the j×(j+1) block in the upper left hand corner. Let s = (s_{1}, s_{2})^{T} be arbitrary, where s_{1} ∈ F^{j} and s_{2} ∈ F^{n−k−j}. The claim is clear, because every column in F^{n−k−j} is a sum of at most n − k − j columns of I_{n−k−j}, and every column in F^{j} is a sum of at most ⌈j/2⌉ columns of H_{1}, a parity check matrix of the binary repetition code of length j + 1. □

For generalizations of the theorem see [91, 96, 117, 118, 119, 120].

More accurate bounds than the redundancy bound may be obtained [33] by taking the minimum distance of a code into account.

Lemma 5.2 The existence of an [n, k, d]ρ code implies the existence of an [n − ρ, k, ⌈d/2⌉] code.

Proof. Let x be a vector such that d(x, C) = ρ and wt(x) = ρ. Such a vector always exists if the code is linear. If c is a nonzero codeword of weight d then

ρ ≤ d(x, c) = wt(x) + wt(c) − 2wt(x ∩ c) = ρ + d − 2wt(x ∩ c).

Thus wt(x ∩ c) ≤ ⌊d/2⌋. Puncturing the code on the positions of the support of x we get a linear code having length n − ρ, the same dimension (x cannot cover any codeword but 0), and the minimum nonzero weight at least

d − wt(x ∩ c) ≥ d − ⌊d/2⌋ = ⌈d/2⌉.
□

Nonexistence results for codes having the parameters of the punctured code lead to bounds on the maximal covering radius of a linear [n, k, d] code. Denote by a[n, d] the maximal dimension of a linear code of length n and minimum distance d, and denote by n[k, d] the smallest length of a binary code of dimension k and minimum distance d.

Theorem 5.3 Let j be the largest number such that a[n − j, ⌈d/2⌉] ≥ k. Then for every [n, k, d]ρ code

ρ ≤ j.

Proof. Obviously follows from the preceding lemma. □

Another possible statement for the previous theorem uses the notion of n[k, d].

Theorem 5.4 For every [n, k, d]ρ code

ρ ≤ n − n[k, ⌈d/2⌉].

Along with Theorem 5.4 the Griesmer bound gives the following [91]:

Theorem 5.5 For every [n, k, d]ρ code

ρ ≤ n − ∑_{i=1}^{k} ⌈\frac{d}{2^{i}} ⌉.

The bound of Theorem 5.5 gives good results if the minimum distance is relatively large. If it is relatively small another approach should be adopted. The following result is by Godlewski (see [167]).

Theorem 5.6 If an [n, k, d]ρ code exists, then

a[ρ, d] + k ≤ a[n, d].

Proof. Let C be an [n, k, d]ρ code and let x be such that d(x, C) = ρ and wt(x) = ρ. Without loss of generality we may assume that the support of x occupies the first ρ positions. Consider a linear code of length ρ and distance d having 2^{a[ρ,d]} codewords. Appending n − ρ zeros at the end of every codeword gives us a [n, a[ρ, d], d] code C̃. We construct a new code

C + C̃ = {c + c̃ : c ∈ C, c̃ ∈ C̃}.

This new linear code is a linear code of length n and dimension ≤ k+a[ρ, d]. We prove its distance is d. To do this it is enough to estimate the minimal weight of the code constructed. Let c̃ be a nonzero codeword of C̃. Then

wt(c + c̃)  = d(c, c̃)
≥ d(c, x) − d(c̃, x) ≥ ρ − (ρ − d) = d.
□

We may apply now the sphere packing (Theorem 2.13 of Chapter 1) upper bound a[n, d]. Theorem 5.6 gives the following result.

Theorem 5.7 Let d be odd and j be the maximal number such that a[j, d] ≤ (n − k) − ⌈log_{2} V (n, (d − 1)/2)⌉. Then for every [n, k, d]ρ code

ρ ≤ j.
□

To lower estimate a[j, d] we might use known results on constructions of best codes. Particularly, for d = 3 we have

a[n, 3] = n − 1 − ⌊log_{2} n⌋,

the lower bound due to the existence of shortened Hamming codes.

Theorem 5.8 Let j be the maximal integer such that j − ⌊log_{2} j⌋ ≤ (n − k) − ⌊log_{2} n⌋. Then for every [n, k, 3]ρ code ρ ≤ j. □

If a code satisfies the Griesmer bound then we may present an upper bound taking into account these gaps in behaviour of a[n, d] (see [7, 18, 44]).

Theorem 5.9 If an [n, k, d]ρ code satisfies the Griesmer bound then

ρ ≤ d − \frac{d}{2^{k}} .

Proof. If C satisfies the Griesmer bound then

n = ∑_{i=0}^{k−1} ⌈\frac{d}{2^{i}} ⌉.

By Theorem 5.5

ρ(C) ≤ n − ∑_{i=1}^{k} ⌈\frac{d}{2^{i}} ⌉ = d − \frac{d}{2^{k}} .

□

Codes with known strength

Let C be an (n, M) binary code. The codeword matrix of C is the M by n matrix M whose rows are the codewords of C in some order. Let s be an integer with 1 ≤ s ≤ n. The code C has strength s provided in each set of s columns of M, each binary s-tuple occurs the same number |M|/2^{s} of times. If C has strength s ≥ 2, then C also has strength s−1. If C has strength s then so does each coset v + C. If C is linear, then C has strength s if and only if the minimum weight of its dual is at least s + 1, that is, every s columns of a generator matrix of C are linearly independent. The dual distance of a code is the first nonzero index of a nonzero element in the MacWilliams transform of the distance distribution of the code. It is known (see e.g. [116]) that the dual distance equals the strength of the code incremented by 1.

A binary code C is self-complementary provided for each vector u in C, the complementary vector \overline{u} is also in C. Note that if C is self-complementary, then so is v + C for each vector v. In particular, each coset of a self-complementary linear code is self-complementary. If a code is self-complementary its dual distance is even.

The bounds presented in the next theorem are usually called Norse bounds [66].

Theorem 5.10 Let C be an (n, M) binary code and let M be its M by n codeword matrix. If C has strength 1, then ρ(C) ≤ ⌊n/2⌋. If C has strength 2 and C is self-complementary, then ρ(C) ≤ ⌊(n − \sqrt{n})/2⌋.

Proof: First assume that C has strength 1. Then for each binary n-tuple v, the codeword matrix Mv for v + C also has strength 1, from which it follows that

∑_{u∈v+C} wt(u) = \frac{nM}{2} ,

equivalently,

∑_{i=0}^{n} iA_{i}(v) = \frac{nM}{2}  (3)

where (A_{i}(v) | 0 ≤ i ≤ n) is the weight distribution of v + C. Equation (3) implies that the average distance between v and the codewords of C is n/2. Thus the distance between v and some codeword is at most n/2, and we conclude that ρ(C) ≤ n/2.

Now assume that M, and hence Mv, has strength 2. Then the binary 2tuple (1,1) occurs M/4 times in each pair of columns of Mv. Summing over all unordered pairs of columns we obtain

∑_{u∈v+C} \frac{wt(u)(wt(u) − 1)}{2} = \frac{n(n − 1)}{2} \frac{M}{4} .

Combining this with (3) we obtain

∑_{i=0}^{n} i^{2}A_{i}(v) = \frac{n(n + 1)M}{4} .  (4)

Equations (3) and (4) imply that

∑_{i=0}^{n}(2i − n)^{2}A_{i}(v) = nM.  (5)

Equation (5) implies that there is an i with A_{i}(v) ≠ 0 such that (2i − n)^{2} ≥ n. Such an i satisfies

(a) i ≤ \frac{n − \sqrt{n}}{2} or (b) i ≥ \frac{n + \sqrt{n}}{2}.

Suppose that v + C is self-complementary. Then there is an i satisfying (a) with A_{i}(v) ≠ 0, that is, a vector u ∈ v + C with weight at most (n − \sqrt{n})/2. Hence ρ(C) ≤ ⌊(n − \sqrt{n})/2⌋. □

Theorem 5.10 and its proof imply the following.

Corollary 5.11 Let C be a self-complementary binary code of length n and strength 2. If ρ(C) = (n − \sqrt{n})/2 and d(v, C) = ρ(C), then half of the vectors in the v + C have weight (n − \sqrt{n})/2 and half have weight (n + \sqrt{n})/2.

We see that the strength or dual distance of the code imply an essential restriction on the covering radius. The Norse bounds give such a bound for a strength equal to 1 and 2. For greater strengths see [42, 80, 111, 142, 143, 144, 154, 155].

6 Descendants and Orphans

Let n be a positive integer. For vectors x = x_{1}x_{2} ⋯ x_{n} and y = y_{1}y_{2} ⋯ y_{n} in F_{2}^{n}, we define x ≤ y provided that y_{i} = 1 for all i such that x_{i} = 1 and thereby make F_{2}^{n} into a partially ordered set (abbreviated poset).^{1}

Let C be a binary linear code of length n, and let C′ and C′′ be two cosets of C. We write C′ ≤ C′′ provided that there is a coset leader x′ of C′ and a coset leader x′′ of C′′ such that x′ ≤ x′′. Using this definition the collection of cosets of C becomes a poset for which C is the unique minimal element. If C′ < C′′, then C′ is called a descendant of C′′ (and C′′ is an ancestor of C′). If C′ is a descendant of C′′, then clearly wt(C′) ≤ wt(C′′) − 1. If C′ is a descendant of C′′ and wt(C′) = wt(C′′) − 1, then C′ is a child of C′′ (and C′′ is a parent of C′). It follows from (v) of Theorem 1.3 that if C′ ≤ C′′ and wt(C′) < wt(C′′) − 1, then there is a coset C′′′ such that C′ ≤ C′′′ ≤ C′′.^{2} A coset of C is called an orphan provided it has no parents, that is, provided it is a maximal element of the poset of all cosets of C. Each coset of C of weight ρ(C) is clearly an orphan but the converse does not hold in general. The presence of orphans with weight less than ρ(C) contributes towards the difficulty in computing the covering radius of a code.

Theorem 6.1 Let C be a binary linear code and let C′ be a coset of weight w of C. Let a be an integer with 0 < a < w. Then the number of descendants of weight a of C′ equals the number of descendants of weight w − a.

Proof. The leaders of the descendants of weight a (respectively, w − a) of C′ are the vectors of weight a (respectively, of weight w − a) covered by a weight w vector of C′. Let x and y be vectors of weight a and let x′ and y′ be vectors of weight w in C′ such that x ≤ x′ and y ≤ y′. Suppose that x and y belong to the same coset of C. Then y − x is in C, and since x′ − y′ is in C, so is

(x′ − x) − (y′ − y) = (x′ − y′) + (y − x).

Hence there are as many different descendants of weight a of C′ as there are descendants of weight w − a. □

If C′ and C′′ are two cosets of C with C′ < C′′, then the following theorem shows how to obtain the coset leaders of C′ from one coset leader of C′ and the coset leaders of C′′ [14].

1This poset is isomorphic to the poset of all subsets of a set of n elements.

2It thus follows that the partially ordered set of cosets of C is a ranked poset, with the rank of a poset equal to its weight, satisfying the Jordan-Dedekind chain condition.

Theorem 6.2 Let C′ and C′′ be two cosets of a binary linear code C and assume that C′ < C′′. Let x′ and x′′ be coset leaders of C′ and C′′, respectively, satisfying x′ < x′′. Let u = x′′ − x′. Then a vector x is a coset leader of C′ if and only if there is a coset leader y of C′′ such that u ≤ y and x = y − u.

Proof. First suppose that y is a coset leader of C′′ with u ≤ y. Then

(y − u) − x′ = y − (u + x′) = y − x′′ ∈ C

and thus y − u is in C′. Since

wt(y − u) = wt(y) − wt(u) = wt(x′′) − wtu) = wt(x′),

y − u is a coset leader of C′.

Now suppose that x is a coset leader of C′. then

(x + u) − x′′ = (x + x′′ − x′) − x′′ = x − x′ ∈ C,

and thus x + u is in C′′. Since

wt(x + u) ≤ wt(x) + wt(u) = wt(x′) + wt(u) = wt(x′′),

x + u is a coset leader of C′′. □ The following corollary [67] is an immediate consequence of Theorem 6.2.

Corollary 6.3 Let C′ and C′′ be two cosets of a binary linear code C and assume that C′ ≤ C′′. Then for each leader x′ of C′ there is a leader x′′ of C′′ such that x′ ≤ x′′. □

It follows from Corollary 6.3 that to determine all the ancestors of a coset C′ it suffices to know only one leader of C′. However, to determine all the descendants of C′′ it does not suffice in general to know only one leader of C′′. For example, let C be the binary repetition code of length 4. Then 1100 is a leader of the coset C′′ = {1100, 0011}. The coset C′ = {1110, 0001} is a child of C′′ but its leader 0001 is not a descendant of 1100.

The following theorem contains a characterization of orphans [12, 13].

Theorem 6.4 Let C′ be a coset of weight w of a binary linear code C. Then C′ is an orphan if and only if each coordinate position is covered by a vector in C′ of weight w or w + 1.

If the minimum distance of C is greater than 2, then there is a one-to-one correspondence between the children of C′ and the coordinate positions covered by the leaders of C′.

If the minimum distance of C is greater than 2 and C contains only even weight vectors, then there is a one-to-one correspondence between the parents of C′ and the coordinate positions not covered by the leaders of C′; in particular, C′ is an orphan if and only if each coordinate position is covered by a leader of C′.

Proof. Let n be the length of C and let e_{i} denote the weight 1 vector of length n with a 1 in position i (1 ≤ i ≤ n). It follows from Corollary 6.3 that each parent of C′ equals C′ + e_{i} for some i. The coset C′ + e_{i} has weight w − 1, w or w + 1 and contains a vector of weight w − 1 or w if and only if C′ contains a vector of weight w or w + 1 with a 1 in position i. This proves the first assertion of the theorem.

Now assume that the minimum distance of C is greater than 2. Then for i ≠ j, the cosets C′ + e_{i} and C′ + e_{j} are distinct. If, in addition, C contains only even weight vectors, then the vectors in any coset have same parity. The other assertions in the theorem now follow from these observations. □

Theorem 6.1 and the last assertion of Theorem 6.4 imply the following result.

Corollary 6.5 Let C be a binary linear code of length n containing only even weight vectors having minimum distance greater than 2. Then an orphan of C of weight w has n descendants of weight 1 and n children. □

Corollary 6.6 If C is a binary linear code containing only even weight vectors and the minimum distance of C is greater than 2, then a coset of weight w having exactly t coset leaders where tw < n is not an orphan. □

It follows from Theorem 6.1 that if code C has exactly one orphan of some weight w then for each integer i with 0 < i < w, the number of cosets of weight i of C equals the number of weight w − i.

Example 6.7 Let C be the [6, 3, 2] self-dual binary linear code C_{2} ⊕ C_{2} ⊕ C_{2} where C_{2} is the [2, 1, 2] code. The complete coset weight distribution of C is given in the following table.

number of vectors

coset of given weight

number

weight 0 1 2 3 4 5 6
0  1 0 3 0 3 0 1  1
1  0 2 0 4 0 2 0  3
2  0 0 4 0 4 0 0  3
3  0 0 0 8 0 0 0  1

The covering radius of C is 3 and C has a unique orphan. The poset of cosets of C is isomorphic to the poset of the subsets of a three element set partially ordered by inclusion.

7 Covering radius of subcodes of a code

Let C and C_{0} be codes such that C_{0} ⊆ C. Then we call C_{0} a subcode of C, and it follows that ρ(C) ≤ ρ(C_{0}).

Now assume that C is an [n, k] binary linear code, and that C_{0} is an [n, k_{0}] binary linear code which is a subcode of C. Then the codimensions m = n − k and m_{0} = n − k_{0} of C and C_{0}, respectively, satisfy m ≤ m_{0} and applying the redundancy bound to C and C_{0} we obtain the basic relationships

ρ(C) ≤ m and ρ(C) ≤ ρ(C_{0}) ≤ m_{0}.

The number m_{0} − m = k − k_{0} is the codimension of C_{0} in C.

Example 7.1 In this example we show how the covering radius of a subcode C_{0} of codimension 1 of a code C can be quite independent of the covering radius of C. Let H be a parity check matrix of a binary code with covering radius ρ, and let C be the code with parity check matrix given by

[ H H ] .

Then clearly ρ(C) = ρ. Let C_{0} be the subcode of codimension 1 in C with parity check matrix

[ \begin{matrix}H & H \\ 0 ⋯ 0 & 1 ⋯ 1 \end{matrix} ] .

We also clearly have ρ(C_{0}) = ρ.

Now let t ≥ 2 be an integer and consider a parity check matrix H_{t} of the [2^{t} − 1, 2^{t} − 1 − t, 3] binary Hamming code. Let H′_{t} be the t by 2^{t} − 2 matrix obtained from H_{t} by deleting its column of all 1’s. Let r be a positive integer. Then the matrix

H′ = [ 1 1 ⋮ 1 \begin{matrix}H′_{t} & O & ⋯ & O \\ O & H′_{t} & ⋯ & O \\ ⋮ & ⋮ & ... & ⋮ \\ O & O & ⋯ & H′_{t} \end{matrix} ]

is a parity check matrix of a code C′ of length r(2^{t} − 2) + 1 with covering radius r. (C′ is the successive amalgamation of Hamming codes.) The matrix

H′_{0} = [ \frac{H′}{1 0 ⋯ 0} ]

is a parity check matrix of a subcode C′_{0} of codimension 1 in C′ with covering radius 2r + 1 (since the syndrome of weight 1 with a 1 in its last position is not the sum of 2r or fewer columns of H′_{0}.) That the code C′ and its subcode C′_{0} exhibit an extreme behavior is a consequence of the next theorem.

The covering radius of a subcode C_{0} of a code C is bounded below by the covering radius of C. The following theorem due independently to Brualdi and Pless [14] and Simonis [138] (see Adams [2] for the case i = 1) gives an upperbound for the covering radius of C_{0} in terms of the covering radius of C and the codimension of C_{0} in C.

Theorem 7.2 Let C_{0} be a subcode of codimension i in a binary linear code C. Then

ρ(C_{0}) ≤ (i + 1)ρ(C) + i.  (6)

Proof. If i = 0, then (6) holds with equality. Assume i ≥ 1 and let

H_{0} = [ \frac{H}{H_{1}} ]

be a parity check matrix of C_{0} such that H is a parity check matrix for C. Let the columns of H_{0}, H and H_{1} be respectively, h_{0}^{j}, h^{j} and h_{1}^{j} for j = 1, 2, …, n.

Let ρ = ρ(C) and ρ_{0} = ρ(C_{0}). Assume to the contrary that ρ_{0} > (i + 1)ρ + i, that is, that ρ_{0} ≥ (i + 1)(ρ + 1). Thus there is a syndrome s_{0} ∈ F_{2}^{m+i} which is not the sum of any set of (i + 1)(ρ + 1) − 1 or fewer columns of H_{0}. Without loss of generality, we may assume that

s_{0} = ∑_{j=1}^{ρ_{0}} h_{0}^{j}.

Let J_{1}, J_{2}, …, J_{i+1} be a partition of {1, 2, …, ρ_{0}} into sets of cardinality at least ρ + 1. Since the covering radius of C equals ρ, there exist sets I_{1}, I_{2}, …, I_{i+1} of cardinality at most ρ such that

∑_{j∈I_{r}} h^{j} = ∑_{j∈J_{r}} h^{j} (r = 1, 2, …, i + 1).

The set of vectors

{∑_{j∈I_{r}} h_{1}^{j} − ∑_{j∈J_{r}} h_{1}^{j} : r = 1, 2, …, i + 1}

in F_{2}^{i} are linearly dependent. It follows that there exists a nonempty subset K of {1, 2, …, i + 1} such that

∑_{j∈∪_{i∈K}I_{i}} h_{1}^{j} = ∑_{j∈∪_{i∈K}J_{i}} h_{1}^{j}.

But then

s_{0} = ∑_{r=1}^{i+1} ∑_{j∈J_{r}} h_{0}^{j} = ∑_{r∈K} ∑_{j∈J_{r}} h_{0}^{j} + ∑_{r∉K} ∑_{j∈J_{r}} h_{0}^{j}
= ∑_{r∈K} ∑_{j∈I_{r}} h_{0}^{j} + ∑_{r∉K} ∑_{j∈J_{r}} h_{0}^{j}.

Since K is nonempty, this contradicts our assumption that s_{0} cannot be expressed as a sum of (i + 1)(ρ + 1) − 1 or fewer columns of H_{0}. □

As noticed in [138], if C is an even code, then a slight modification of the proof of Theorem 7.2 leads to an improvement of (6).

Theorem 7.3 Let C_{0} be a subcode of codimension i in an even binary linear code C. Then

ρ(C_{0}) ≤ (i + 1)ρ(C).  (7)

Proof. We proceed as in the proof of Theorem 7.2 but to obtain a contradiction, we assume that ρ_{0} ≥ (i + 1)ρ + 1. We consider sets J_{1}, J_{2}, …, J_{i} whose union is {1, 2, …, ρ_{0}} which are pairwise disjoint except for the fact that all contain the element 1. □

The inequality (6) can be improved considerably for codes that are direct sums of other codes [15].

Theorem 7.4 Let C = C^{1} ⊕ C^{2} ⊕ ⋯ ⊕ C^{t} be the direct sum of t binary linear codes C^{1}, C^{2}, …, C^{t}, and let C_{0} be a subcode of codimension i in C. Then

ρ(C_{0}) ≤ ρ(C) + i max{ρ(C^{j}) : j = 1, 2, …, t} + i.

Proof. Let

H_{0} = [ \frac{H^{1} ⊕ H^{2} ⋯ ⊕ H^{t}}{K} ]

be a parity check matrix for C_{0} where H^{1} ⊕ H^{2} ⊕ ⋯ ⊕ H^{t} is a parity check matrix for C and K has i rows. Using elementary row operations on H_{0} we can obtain a parity check matrix for C_{0} of the form

[ \begin{matrix}H^{1} & O & ⋯ & O \\ O & H^{2} & ⋯ & O \\ ⋮ & ⋮ & ... & ⋮ \\ O & O & ⋯ & H^{t} \\ H_{0}^{1} & ∗ & ⋯ & ∗ \\ O & H_{0}^{2} & ⋯ & ∗ \\ ⋮ & ⋮ & ... & ⋮ \\ O & O & ⋯ & H_{0}^{t} \end{matrix} ]

where the matrix

[ \begin{matrix}H^{j} \\ H_{0}^{j} \end{matrix} ]  (8)

has linearly independent rows for each j = 1, 2, …, t. Let a_{j} be the number of rows of H_{0}^{j} and let C_{0}^{j} be the code for which (8) is a parity check matrix. We have i = a_{1} + a_{2} + ⋯ + a_{t}, and C_{0}^{j} is a subcode of codimension a_{j} in C_{0}^{j} for j = 1, 2, …, t. Arguing inductively on t from Theorem 7.2, we obtain

ρ(C_{0}) ≤ ∑_{j=1}^{t}(a_{j} + 1)ρ(C_{j}) + ∑_{j=1}^{t} a_{j}

= ρ(C) + ∑_{j=1}^{t} a_{j}ρ(C^{j}) + i,

and the theorem follows. □

A different approach to bounding the covering radius of a subcode was initiated by Calderbank [19] and further exploited by Hou [87]. This approach is based on estimating the chromatic number of a graph. A graph G is a pair consisting of a set V of vertices and a set E of edges (unordered pairs of vertices). A coloring with color set P of G is a map f : V → P such that f(x) ≠ f(y) whenever {x, y} is an edge. The chromatic number of G is the smallest integer χ(G) for which G has a coloring with color set of cardinality χ(G).

A stable set of a graph is a collection of its vertices no two of which form an edge. Let G be a graph with n vertices and let f be a coloring of G. The set of vertices of G with a given color is a stable set. Hence if l is an integer such that no stable set of G has cardinality larger than l, then χ(G) ≥ n/l.

Let G(n, s) be the graph with vertex set equal to F_{2}^{n} where two vertices u, v ∈ F_{2}^{n} form an edge if and only if their distance is greater than s. (The vertices of G(n, s) can be regarded as the subsets of {1, 2, …, n} and the edges as pairs {A, B} of subsets for which |A \ B| + |B \ A| > s).) The Kneser graph K(n, r + 1) is the subgraph of G(n, 2r) induced by the subset of F_{2}^{n} consisting of those vertices of weight r + 1. Thus two elements u, v ∈ F_{2}^{n} of weight r + 1 form an edge of K(n, r + 1) if and only if no coordinate equals 1 in both u and v. It was proved by Lovász [115] (see also [6]) that

χ(K(n, r + 1)) = n − 2r if n ≥ 2r + 2.  (9)

The following theorem of Calderbank [20] gives an upper bound on the covering radius of a subcode.

Theorem 7.5 Let C_{0} be a subcode of codimension i ≥ 1 in a binary linear code C. Then

ρ(C_{0}) ≤ 2ρ(C) + 2^{i} − 1.  (10)

Proof. As before let

H_{0} = [ \frac{H}{H_{1}} ]

be a parity check matrix of C_{0} such that H is a parity check matrix for C, and let the columns of H_{0}, H and H_{1} be respectively, h_{0}^{j}, h^{j} and h_{1}^{j} for j = 1, 2, …, n.

Let ρ = ρ(C) and ρ_{0} = ρ(C_{0}). If ρ_{0} ≤ 2ρ + 1, the theorem clearly holds. Now assume that ρ_{0} ≥ 2ρ + 2. Without loss of generality, we may assume that

s_{0} = ∑_{j=1}^{ρ_{0}} h_{0}^{j}

cannot be expressed as the sum of ρ_{0} −1 or fewer columns of H_{0}. We write each vector v ∈ F_{2}^{n} as (v′, v′′) where v′ is in F_{2}^{ρ_{0}}.

It follows from the definition of covering radius that for each vector v′ ∈ F_{2}^{ρ_{0}}, there is a vector x_{v′} ∈ C such that the distance between (v′, 0) and x_{v′} is at most ρ. We define a mapping f from the vectors v′ of F_{2}^{ρ_{0}} of weight ρ + 1 to the 2^{i} − 1 nonzero vectors of F_{2}^{i} by

f(v′) = H_{1}x_{v′}.

We have H_{1}x_{v′} ≠ 0 because otherwise, since x_{v′} is in C, s_{0} can be expressed as a sum of ρ_{0} − 1 columns of H_{0}.

Let {v′, w′} be an edge of the Kneser graph K(ρ_{0}, ρ + 1), and assume that f(v′) = f(w′), that is, that H_{1}x_{v′} = H_{1}x_{w′}. Then v′ + w′ has weight 2ρ + 2, and the distance between (v′ + w′, 0) and x_{v′} + x_{w′} is at most 2ρ. Since H_{1}(x_{v′} + x_{w′}) = 0, we see that s_{0} can be expressed as a sum of at most ρ_{0} − 2 columns of H_{0}, a contradiction. Hence f(v′) ≠ f(w′) whenever {v′, w′} is an edge, and f is a coloring of the Kneser graph K(ρ_{0}, ρ + 1) with 2^{i} − 1 colors. Applying (9) we obtain

ρ_{0} − 2ρ = χ(K(ρ_{0}, ρ + 1)) ≤ 2^{i} − 1.
□

The following theorem of Kleitman [99] gives an upper bound on the cardinality of a stable set of the graph G(n, 2r), and hence a lower bound on its chromatic number.

Theorem 7.6 Let n and r be positive integers with n ≥ 2r + 1. Then each stable set of G(n, 2r) has cardinality at most

\binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{r},

and hence

χ(G(n, 2r)) ≥ \frac{2^{n}}{\binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{r}}.

The following theorem is due to Hou [87] and often improves (6) and (10).

Theorem 7.7 Let C_{0} be a subcode of codimension i ≥ 1 in a binary linear code C. Then

\frac{2^{ρ_{0}}}{\binom{ρ_{0}}{0} + \binom{ρ_{0}}{1} + ⋯ + \binom{ρ_{0}}{r}} ≤ 2^{i},  (11)

that is,

ρ(C_{0}) ≤ log_{2} (\binom{ρ_{0}}{0} + \binom{ρ_{0}}{1} + ⋯ + \binom{ρ_{0}}{r}) + i.

Proof. Let ρ = ρ(C) and ρ_{0} = ρ(C_{0}). If ρ_{0} ≤ 2ρ, then (11) is trivially true. Assume that ρ_{0} ≥ 2ρ + 1. In the proof of the preceding theorem we consider f as a map from the vertices of G(ρ_{0}, 2ρ) to F_{2}^{i}. As before it follows that f is a coloring of G(ρ_{0}, 2ρ) with 2^{i} colorings and the result is a consequence of Theorem 7.6. □

8 The binary length and covering radius functions

We recall from Section 1 that for 1 ≤ r ≤ m, the length function ℓ_{q}(m, r) is defined to be the smallest length n of a linear code C ⊆ F_{q}^{n} with codimension m and covering radius r. Also for 1 ≤ k ≤ n, the covering radius function t_{q}(n, k) is the smallest covering radius of an [n, k] code over F_{q}. In this section we investigate the binary length and covering radius functions, and we use ℓ(m, r) in place of ℓ_{2}(m, r). and t[n, k] in place of t_{2}[n, k]. Thus ℓ(m, r) is the smallest number n of vectors v_{1}, …, v_{n} in F_{2}^{m} such that every vector in F_{2}^{m} is a sum of r or fewer of v_{1}, …, v_{n}. The vectors v_{1}, …, v_{n} are the columns of a parity check matrix of a code of length n and codimension m whose covering radius equals r. Because of the economical benefits of the length function in recording data, we concentrate on the length function.

In the next theorem we collect elementary properties of ℓ(m, r) given in [17].

Theorem 8.1 The following properties hold:

(i) m ≤ ℓ(m, r) ≤ 2^{m} − 1 with equality at the lower end if and only if r = m (the zero code) and equality at the upper end if and only if r = 1 (the Hamming codes);

(ii) (sphere covering bound)

min\{n : ∑_{i=0}^{r} \binom{n}{i} ≥ 2^{m}\} ≤ ℓ(m, r);

(iii) ℓ(m, r + 1) ≤ ℓ(m, r);

(iv) ℓ(m, r) ≤ ℓ(m + 1, r) − 1; (v) ℓ(m + 1, r + 1) ≤ ℓ(m, r) + 1;

(vi) ℓ(m, r) = m + 1 if ⌈m/2⌉ ≤ r < m;

Proof. Properties (i)-(v) follow easily. We give the proofs of (iii) and (v). Let n = ℓ(m, r) and let H = [I_{m} A] be an m×n parity check matrix of an [n, n−m] code C of covering radius r. Of all such parity check matrices H choose one for which A has a column, say w, of smallest weight. Let w′ and H′ be obtained by replacing a 1 in w by 0. By our choice of A, H′ is an m × n parity check matrix of a code C′ of covering radius r + 1 or more. Because w = w′ + u for some unit vector u (and hence column of H′), it follows that the covering radius of C′ equals r + 1, proving (iii). To prove (v), we note that H ⊕ I_{1} is an (m + 1) × (n + 1) parity check matrix of an [n + 1, n − m] code whose covering radius equals r + 1.

To prove (vi), let

H = [ I_{m} 1 ] .

Then H is a parity check matrix for a code of length m + 1 and codimension m whose covering radius equals ⌈m/2⌉. Since a code of codimension m with covering radius less than m has length at least m + 1, (vi) follows from (i) and (iii). □

We next prove two theorems [31] which are useful only when k is small.

Theorem 8.2 Let k and n be integers with 2 ≤ k ≤ 1 + log_{2} n. Then

t[n, k] ≥ ⌈\frac{n}{2}⌉ − 2^{k−2}.

Proof. Let C be an [n, k] code with generator matrix G whose covering radius equals t[n, k]. Each column of G represents in base 2 an integer between 1 and 2^{k} − 1, and we let n_{i} be the number of columns of G which represent the integer i. We may assume that

G = [ G_{0} G_{1} ⋯ G_{2^{k}−1} ]

where G_{0} has distinct columns, each column of G_{0} is a column of some G_{i} with i ≥ 1, and each G_{i} with i ≥ 1 has 2⌊n_{i}/2⌋ columns each representing the integer i. Let C_{i} be the code generated by G_{i} (i = 0, 1, …, 2^{k} − 1). Then C_{0} is the simplex code of length 2^{k} − 1 punctured s = 2^{k} − 1 − ∑_{i≥1}(n_{i} − 2⌊n_{i}/2⌋) times, and C_{i} is a binary repetition code of even length 2⌊n_{i}/2⌋ for i ≥ 1. Let C′ be the code obtained from C by puncturing the coordinates corresponding to C_{0}. Then

ρ(C′) = ∑_{i≥1} ⌊\frac{n_{i}}{2} ⌋ .  (12)

It follows that

t[n, k] = ρ(C) ≥ ρ(C_{0}) + ρ(C′)
= ρ(C_{0}) + ∑_{i≥1} ⌊\frac{n_{i}}{2} ⌋ .  (13)

It will be shown in Section 9 that the covering radius of the [2^{k} − 1, k] simplex code is 2^{k−1} − 1. Hence by (ii) of Theorem 1.3 we have

ρ(C_{0}) ≥ 2^{k−1} − 1 − s
= ∑_{i≥1} (n_{i} − 2 ⌊\frac{n_{i}}{2} ⌋) − 2^{k−1}
= n − 2^{k−1} − ∑_{i≥1} 2 ⌊\frac{n_{i}}{2} ⌋ .  (14)

Now by hypothesis, n/2 − 2^{k−2} ≥ 0. If ∑_{i≥1} ⌊n_{i}/2⌋ ≥ n/2 − 2^{k−2}, then the inequality in the lemma follows trivially from (13) and (12). Assume that ∑_{i≥1}⌊n_{i}/2⌋ < n/2 − 2^{k−2}. Then the inequality in the theorem follows from (14) and (12). □

Theorem 8.3 We have

(i) t[n, k] ≤ ⌈\frac{n−k}{2} ⌉,

(ii) t[n, k] ≤ ⌊n/2⌋ − ⌊2^{(k−4)/2}⌋ for n ≥ 2^{k−2}, and

(iii) t[n, k] ≥ t[n − 2, k] + 1 for n > 2^{k} − max{2^{(k−2)/2}, k}.

Proof. Assertion (i) of the theorem follows by choosing an [n, k] code with a parity check matrix of the form

[ I_{n−k} 1 A ] .

To prove assertion (ii), let m = k − 2, and consider the code C which is the direct sum of the [2^{m}, m+1] 1st order Reed-Muller code R(1, m) and the binary repetition code of length n − 2^{m}. By Theorem 9.1, R(1, m) has covering radius at most

2^{m−1} − 2^{(m−2)/2},

and (ii) now follows by a simple calculation.

For (iii), let C be an [n, k] code with ρ(C) = t[n, k]. Suppose that a generator matrix G of C does not have two identical columns. Then C is obtained from the simplex code of length 2^{k} − 1 by puncturing 2^{k} − 1 − n coordinates and hence

ρ(C) ≥ 2^{k−1} − 1 − (2^{k} − 1 − n) = n − 2^{k−1}.

On the other hand, by (i) and (ii) we have

ρ(C) ≤ min \{\frac{n}{2} − 2^{(k−4)/2}, ⌈\frac{n − k}{2} ⌉\} .

The assumption on the size of n now give a contradiction. Therefore C contains two identical columns and hence C is a concatenation of a [n − 2, k′] code with a [2,1] code where k′ ≤ k. Hence

ρ(C) ≥ t[n − 2, k′] + 1 ≥ t[n − 2, k] + 1

and this proves (iii). □

It is easy to verify that t[n, 2] = ⌊(n − 1)/2⌋ for n ≥ 2. We now determine t[n, 3] and t[n, 4] [31, 55].

Theorem 8.4 We have t[n, 3] = ⌈(n−2)/2⌉ for n ≥ 4 and t[n, 4] = ⌊(n−4)/2⌋ for n ≥ 6.

Proof. Let n ≥ 4 be an integer. The direct sum of the binary repetition code of length n − 2 and F_{2}^{2} is an [n, 3] code with covering radius ⌈(n − 2)/2⌉. It follows from Theorem 8.2 that no [n, 3] code has smaller covering radius, that is, t[n, 3] = ⌈(n − 2)/2⌉.

Now let n ≥ 6. Applying Theorem 2.2 to the [6, 4] code of covering radius 1 given by the direct sum of the binary repetition code of length 3 and F_{2}^{3} (n even), or the [7, 4] Hamming code (n odd), we obtain an [n, 4] code with covering radius equal to ⌊(n − 4)/2⌋. We now show that no [n, 4] code has smaller covering radius, and thus that t[n, 4] = ⌊(n − 4)/2⌋ for n ≥ 6. We do this by showing that t[2s + 1, 4] ≥ s − 2 and t[2s, 4] ≥ s − 2 for s ≥ 3. The first of these is clear for s ≤ 4, and the second is clear for s ≤ 5

It follows directly from the sphere covering bound that t[11, 4] ≥ 3. Starting from this fact and repeatedly using (iii) of Theorem 8.3 we obtain t[2s + 1, 4] ≥ s − 2 for s ≥ 5. Now consider a [12,4] code C with ρ(C) = t[12, 4]. Suppose that ρ(C) = 3. Then a generator matrix of C has two identical columns, for otherwise C is obtained from the [15, 4] simplex code (with covering radius 7) by puncturing three columns and hence has covering radius equal to 4 or more. Hence t[12, 4] = 4 and applying (iii) of Theorem 8.3 as above gives t[2s, 4] ≥ s−2 for s ≥ 6. □

In the next theorem we determine some values of ℓ(m, r) [16, 17].

Theorem 8.5 We have

(i) ℓ(2s + 1, s) = 2s + 5 if s ≥ 1,

(ii) ℓ(2s, s − 1) = 2s + 6 if s ≥ 4, and

(iii) ℓ(2s + 1, s − 1) = 2s + 7 if s ≥ 6.

Proof. If s = 1, clearly (i) holds. Assume that s > 1. By Theorem 8.4 t[n, 3] = ⌊(n−2)/2⌋ and hence t[2s+4, 3] = s+1. Therefore ℓ(2s+1, s) > 2s+4. As shown in the proof of Theorem 8.4, there exists an [n, 4] code with covering radius equal to ⌊(n − 4)/2⌋. Hence ℓ(2s + 1, s) ≤ 2s + 5. Thus (i) follows. (ii) Let n ≥ 7 be an integer. By taking the direct sum of an [n − 1, 4] code with covering radius ⌊(n − 5)/2⌋ (the existence of such a code is established in the proof of (i) above) with F_{2}^{1} we obtain an [n, 5] code whose covering radius is ⌊(n−5)/2⌋. It was established in [55] using computer calculations that if n ≤ 31, no [n, 5] code has smaller covering radius. Suppose that n ≥ 32 and let C be an [n, 5] code with covering radius equal to t[n, 5]. Each generator matrix of C has a repeated column and hence using the distance definition of covering radius, we see that ρ(C) ≥ ρ(C′) + 1 where C′ is the [n − 2, k′ ≤ 5] code obtained from C by puncturing two repeated columns in a generator matrix. Hence ρ(C) ≥ r + 1 where r is the smallest covering radius of an [n − 2, 5] code. Thus by induction, t[n, 5] ≥ ⌊(n − 5)/2⌋ for n ≥ 7 and so t[2s + 5, 5] = s for s ≥ 1. Therefore

ℓ(2s, s − 1) > 2s + 5 (s ≥ 1).  (15)

We next observe that the [14, 6] and [19, 6] codes with generator matrices,

[ \begin{matrix}1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \end{matrix} ]

and

[ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} ]

have covering radius 3 and 5, respectively. Moreover, it can be shown that each of these codes is normal with all coordinates acceptable. Applying Corollary 2.3, we conclude that there are [14 + 2i, 6] codes with covering radius 3 + i, and [19 + 2i, 6] codes with covering radius 5 + i for each i ≥ 0. Hence t[n, 6] ≤ ⌊(n − 8)/2⌋ for n ≥ 18, n = 14 and n = 16, and so t[2s + 6, 6] ≤ s − 1 for s ≥ 6. Therefore

ℓ(2s, s − 1) ≤ 2s + 6 (s ≥ 6).  (16)

Combining (15) and (16) we obtain (ii) for s ≥ 6.. The [14,6] code C above also shows that (ii) holds for s = 4. By taking the ADS of C with the [3,1] Hamming

Table 2: Lower and upper bounds for ℓ(m, r)

m/r 2  3  4  5  6  7  8  9  10
2  2
3  4  3
4  5  5  4
5  9  6  6  5
6  13  7  7  7  6
7  19  11  8  8  8  7
8  25-26  14  9  9  9  9  8
9  34-39  17-18  13  10  10  10  10  9
10  47-53  21-22  16  11  11  11  11  11  10
11  65-79  23  17-20  15  12  12  12  12  12
12  92-107  31-37  19-23  18  13  13  13  13  13
13  129-159  38-53  23-25  19  17  14  14  14  14
14  182-215  47-63  27-29  21-24  20  15  15  15  15
15  257-319  60-75  32-37  23-27  21  19  16  16  16
16  363-431  75-95  37-49  27-31  22-25 22  17  17  17
17  513-639  93-126  44-62  30-35  24-29 23  21  18  18
18  725-863  117-153 53-77  34-41  27-33 24-27 24  19  19
19  1025-1279 148-205 62-84  39-47  30-36 25-30 25  23  20
20  1449-1727 187-255 73-93  44-59  33-40 28-31 26-29 26  21
21  2049-2559 235-308 86-125  51-75  37-44 30-38 27-32 27  25
22  2897-3455 295-383 103-150 57-88  41-45 33-41 29-33 28-31 28
23  4097-5119 371-511 122-174 65-98  46-59 37-45 31-37 29-34 29
24  5794-6911 467-618 144-190 76-107 51-73 40-47 34-41 30-35 30-33

code we obtain a [16,6] code whose covering radius is easily computed to be 4 and this yields (ii) for s = 5. (iii) Let s = 6 + i. It was shown in (ii) above that t[n, 6] ≤ ⌊(n − 8)/2⌋ for n ≥ 18, and hence there exists a [2s + 7, 6] code with covering radius at most s − 1 for each s ≥ 6. Hence ℓ(2s + 1, s − 1) ≤ 2s + 7. On the other hand, by (iv) of Theorem 8.1 and (ii) we have for s ≥ 4,

ℓ(2s + 1, s − 1) ≥ ℓ(2s, s − 1) + 1 ≥ 2s + 7,

and (iii) follows. □

We remark that (ii) of Theorem 8.5 fails for s = 1, 2, and 3. Also (i) of Theorem 8.5 fails for s ≤ 4, but it is not known whether or not (i) holds for s = 5 that is, whether or not ℓ(11, 4) = 17.

We summarize known results for ℓ(m, r) in Table 2. A code C of codimension m and covering radius r is said to be r-short if it has length ℓ(m, r). Most of the single values in the table (which correspond to r-short codes) are due to Theorems 8.5 and 8.1 (especially part (vi)). The existence of the Golay code gives ℓ(11, 3) = 23. There are constructions for all the r-short codes in the table. Many of the entries in the table give intervals for ℓ(m, r). An upper bound always represents a construction; some of these are ADS sums of other codes in the table. Most of the constructions for the upper bounds in the table for ρ = 2, 3, 4 (some for ρ = 5) are due to Davydov et al. and are described in Theorem 3.7.

The sphere covering bound provides a lower bound on ℓ(m, r), although most of the lower bounds in Table 2 are larger than that given by this inequality. In [17] it was conjectured that ℓ(2m − 1, 2) ≥ 2^{m} + 1 whenever m ≥ 3. This was shown to be true by Struik [150] using Theorems 4.3 and 8.7 (see below). This inequality for ℓ(2m − 1, 2) gives all the lower bounds in the table for ρ = 2, m odd and ≥ 11. For references on all bounds in Table 2 see [113]. Parts (iii) and (iv) of Theorem 8.1 which say that values in a row of this table are non-increasing and values in a column are strictly decreasing give many lower bounds.

Many of the other lower bounds, mainly for ρ = 2 or 3, have been demonstrated by investigating the dual code. It can sometimes be shown that this code cannot exist or else that conditions on it make the specified covering radius impossible. We will show what is involved. The following theorem was demonstrated in [17] for r even and for all r in [150]. Recall that \overline{u} denotes the complement of u.

Theorem 8.6 If C and C′ have parity check matrices

H = [ \begin{matrix}1 & u \\ 0 & A \end{matrix} ] and H′ = [ \begin{matrix}1 & \overline{u} \\ 0 & A \end{matrix} ]

respectively, then C and C′ have the same covering radius.

Proof. The vector c = (c_{1}, c_{2}, …, c_{n}) is in C if and only if the vector c′ = (∑_{i=1}^{n} c_{i}, c_{2}, …, c_{n}) is in C′. Hence C and C′ have equivalent extensions and so these extensions have the same covering radius. By Theorem 1.3 (iv), C and C′ also have the same covering radius. □

Theorem 8.7 ([17, 150]) If C is a length n binary code of codimension m and covering radius 2 and w is the weight of a vector in C^{⊥}, then the following hold:

(i) w(n + 1 − w) ≥ 2^{m−1};

(ii) w2^{(n−w)−(m−1)} ≥ k[n − w, 1].

Proof. Let x be a vector in C^{⊥} of weight w. Then we can suppose that C has the following parity check matrix, where x is the first row of H:

H = \binom{1 … 1 0 … 0}{A S} .

Consider the syndromes which begin with 1. There are 2^{m−1} such syndromes and each is either one the first w columns of H or a sum of such a vector and one of the last n−w columns of H. Hence w +w(n−w) = w(n+1−w) ≥ 2^{m−1} demonstrating (i).

Part (ii) follows from Theorem 3.3 as S 1-covers F^{m−1} using A. □

To illustrate how these theorems work we show that ℓ(6, 2) = 13. This was first demonstrated in [55] using a Cray computer. A computer-free proof was omitted from [17] but included in [150].

Theorem 8.8 ℓ(6, 2) = 13.

Proof. As there exists a [13, 7]2 code [17], ℓ(6, 2) ≤ 13. Suppose that C is a [12, 6]2 code. By Theorem 8.7 (i), if w is the weight of a vector in C^{⊥}, then 4 ≤ w ≤ 9. By Theorem 8.6 we can suppose that either C^{⊥} contains vectors of both weights 4 and 9 or else has exactly one vector of weight 4 and maximum weight 8 or less. It is not hard to show that the latter situation is impossible. Hence C has a parity check matrix of the following form where X is a 5 × 9 matrix and Y is a 5 × 3 matrix:

H = \left[{1 … 1 0 … 0 \atop X Y}\right] .

Since X is 2-short, the rank of Y is 2 or 3. First suppose that the rank of Y is 3. Then the maximal subcode of C^{⊥} consisting of those vectors with 0’s in the last three positions has dimension 3. Since C^{⊥} has minimum weight 4, this subcode contains vectors only of weights 0, 4, 5 and 9 and two distinct vectors of weight 4 have 1’s in exactly 2 common positions. It follows that we can assume H is of the following form:

H = [ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & & & & & 0 & & & 0 & 1 & 0 & 0 \\ 0 & α & β & γ & δ & 0 & ϵ & ρ & 0 & 0 & 1 & 0 \\ 0 & & & & & 0 & & & 0 & 0 & 0 & 1 \end{matrix} ] .

If we consider the syndromes beginning with 110 or 101 we can conclude that α and δ have weight 3. If we consider syndromes beginning with 111 or 100 we find that β and γ are complementary vectors as are ϵ and ρ. Now we see that we cannot obtain all syndromes beginning with 001.

Suppose now that the rank of Y is 2. Then we can assume that H has the following form:

H = [ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & & 0 & 0 & 0 & 0 \\ & & & x & & & & & a & & 1 & 0 & 1 \\ & & & y & & & & & b & & 0 & 1 & 1 \end{matrix} ] .

As the first 4×7 portion of H is a basis of the [7, 4, 3]1 code we can suppose that either wt(x) = wt(y) = 1 or wt(x) = 1 and wt(y) = 0. In the latter situation, H is uniquely determined as follows:

H = [ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{matrix} ] .

Now it can be seen that the only syndrome which cannot be obtained as a single column of H or a sum of two columns of H is (0, 1, 0, 1, 1, 0)^{t}. In case wt(y) is also 1 either a and b are as above or both are unit vectors. In these cases it can be seen that some syndromes cannot be obtained. □

In [17] conditions were given on the number of 1’s two vectors in C^{⊥} can have in common. This was used in both [17] and [150] to get further lower bounds for ρ = 2 and 3. Also Struik generalized Theorem 8.7 for codes of covering radius 3 [150]. In particular, he obtains the following.

Theorem 8.9 Let C be a binary [n, k]3 code and m = n − k. Then the weights w in C^{⊥} satisfy w(n + 1 − w)^{2} ≥ 2^{m} or w ≥ m. □

Other techniques utilizing a graph obtained from syndromes of a code have been applied to provide specific lower bounds [15, 21]. It remains an open problem to reduce the intervals in the table further.

9 Covering radius of Reed-Muller codes

Let ρ_{RM}(r, m) denote the covering radius of the r-th order Reed-Muller code of length 2^{m}, R(r, m). We start with estimating the covering radius of first order Reed-Muller codes. By the Norse bound ρ_{RM}(1, m) is upperbounded as follows.

Theorem 9.1

ρ_{RM}(1, m) ≤ 2^{m−1} − 2^{(m−2)/2}.
□

To obtain a lower bound the following recurrence relation is of use.

Lemma 9.2 For m ≥ 2

ρ_{RM}(1, m) ≥ 2ρ_{RM}(1, m − 2) + 2^{m−2}.

Proof. Let c̄ denote the complement of c. From the inductive definition of Reed-Muller codes the vectors of R(1, m) belong to one of the following types:

(v|v|v|v), (v|v̄|v̄|v), (v|v̄|v|v̄), (v|v|v̄|v̄),  (17)

where v ∈ R(1, m−2). Choose a 2^{m−2}-vector x such that it realizes the covering radius of R(1, m − 2), i.e.

d(v, x) ≥ ρ_{RM}(1, m − 2)

for all v ∈ R(1, m − 2). Next, consider the 2^{m}-vector y = (x, x, x, x̄). Notice, that

d(x, v̄) = d(x̄, v) = 2^{m−2} − d(x, v) = 2^{m−2} − d(x̄, v̄).

Let c ∈ R(1, m) be of one of the four types in (17). Then,

d(y, c) = 3d(x, v) + d(x̄, v) = 2^{m−2} + 2d(x, v) ≥ 2^{m−2} + 2ρ_{RM}(1, m − 2),

or

d(y, c) = d(x, v) + 3d(x̄, v) = 2^{m−2} + 2d(x, v̄) ≥ 2^{m−2} + 2ρ_{RM}(1, m − 2),

depending on the particular type of the vector c. □

Now, we have ρ_{RM}(1, 1) = 0 and ρ_{RM}(1, 2) = 1, thus giving ρ_{RM}(1, m) ≥ 2^{m−1} − 2^{(m−2)/2} for even m and

ρ_{RM}(1, m) ≥ 2^{m−1} − 2^{(m−1)/2}  (18)

for odd m. By Theorem 9.1 we get the exact result for the covering radius of the first order Reed-Muller codes when m is even [66].

Theorem 9.3 For even m, ρ_{RM}(1, m) = 2^{m−1} − 2^{(m−2)/2}.

For odd m the situation is much more complicated. To analyze the problem we relate it to the existence of some linear codes with parameters depending on the covering radius of the first order Reed-Muller codes.

Lemma 9.4 The covering radius of R(1, m) is t if and only if t is the maximal integer such that there exists a [t, m + 1, d ≥ t − 2^{m−2}] self-complementary code C having d^{⊥} ≥ 3.

Proof. Assume that the covering radius of R(1, m) is t. Let x be a covering radius orphan, and wt(x) = t. The support of x selects t columns from G(1, m), the generator matrix of R(1, m). Let G denote the (m+1)×t-matrix formed by these columns. Then up to permutation G(1, m) = (G, G′). Represent a vector c ∈ R(1, m) as (c_{0}, c_{1}) where the two parts are of lengths t and 2^{m} − t. In this notation x is just (1^{t}, 0^{n−t}). Let C be the code of length t generated by G. Let c be a vector of R(1, m) different from the all-zero and the all-one vectors. Then

wt(c) = wt(c_{0}) + wt(c_{1}) = 2^{m−1}.  (19)

We have

d(x, c) = t − wt(c_{0}) + wt(c_{1}) ≥ t.

Thus, wt(c_{1}) ≥ wt(c_{0}), and from (19) we get

wt(c_{0}) ≤ 2^{m−2}.

Since the vector c̄ also belongs to R(1, m), then c̄_{0} is in the code C. Evidently, wt(c̄_{0}) ≥ t−2^{m−2}. So, the weight of any non-zero vector of C is at least t−2^{m−2} and at most 2^{m−2}, or equals 0 or t. So, the minimum distance d of C satisfies d ≥ t − 2^{m−2}. If the dimension of C were < m + 1, then there would be a combination of the rows of G which is the zero vector. Let c be the vector in R(1, m) which is this combination of the rows of G(1, m). Then the weight of c̄ + x equals 2^{m−1} − t. By (18) t > 2^{m−2} so that c̄ + x would be a vector in the same coset as x but of smaller weight. This contradicts the choice of x showing that C has dimension m + 1. Notice, that being a submatrix of G(1, m), G contains the all-one row, and thus, is self-complementary; moreover, G can not have identical columns. The converse statement is proved by simply reversing the previous arguments. □

Note, that the non-existence of an [n, k, d] code satisfying the requirements implies non-existence of such codes with parameters [n+i, k, d+i]. This follows from the possibility of puncturing i coordinates in the last code which does not violate the desired properties of the code.

To demonstrate how the lemma works let us consider the case of R(1, 5). From (18) we get ρ_{RM}(1, 5) ≥ 12. If ρ_{RM}(1, 5) ≥ 13 then there exists a linear code [13, 6, 5]. But such code does not exist due to the Griesmer bound. Namely, the existence of such a code would imply the existence of a [8, 5, 3] code which is clearly impossible. To prove ρ_{RM}(1, 7) = 56 it is necessary to demonstrate the non-existence of a self-complementary [57, 8, 25] code. Actually, a linear code with such parameters does exist, but as it was proved in [124] that such code can not be self-complementary.

Relying on numerical evidence it was tempting to conjecture that apparently the lower bound 2^{m−1} − 2^{(m−1)/2} is tight for ρ_{RM}(1, m). This was disproved for m = 15 in [134, 135]. Namely, a vector was exhibited at distance 16 276 = 2^{14}−2^{7}+20 from R(1, 15). All these results and Lemma 9.8 allow us to formulate the following theorem.

Theorem 9.5 For m odd

ρ_{RM}(1, m) = 2^{m−1} − 2^{(m−1)/2}
for m = 1, 3, 5;
2^{m−1} − 2^{(m−1)/2}  ≤ ρ_{RM}(1, m) ≤ 2^{m−1} − 2^{(m−2)/2}
for m = 7, 9, 11, 13;
2^{m−1} − (27/32) · 2^{(m−1)/2} ≤ ρ_{RM}(1, m) ≤ 2^{m−1} − 2^{(m−2)/2}
for m ≥ 15.

The following two conjectures about ρ_{RM}(1, m) were stated in [134] and [13], respectively.

Conjecture 9.6

lim_{m→∞} \frac{2^{m−1} − ρ_{RM}(1, m)}{2^{(m−2)/2}} = 1.

Conjecture 9.7 For m ≥ 3, ρ_{RM}(1, m) is even.

Now we continue with Reed-Muller codes of order greater than 1. We will use the following simple, however essential, lemma.

Lemma 9.8

2ρ_{RM}(r, m − 1) ≤ ρ_{RM}(r, m),  (20)
ρ_{RM}(r − 1, m − 1) ≤ ρ_{RM}(r, m),  (21)
ρ_{RM}(r, m) ≤ ρ_{RM}(r, m − 1) + ρ_{RM}(r − 1, m − 1).  (22)

Proof. Reed-Muller codes are inductively defined by

R(r, m) = {(u, u + v) : u ∈ R(r, m − 1), v ∈ R(r − 1, m − 1)}.

Since R(r − 1, m − 1) ⊂ R(r, m − 1), we have u + v ∈ R(r, m − 1). Let x be a vector of length 2^{m−1} such that d(x, u) ≥ ρ_{RM}(r, m−1) for all u ∈ R(r, m−1). Then (x, x) guarantees (20). To prove (21) consider a vector (0, y) where y is a vector such that d(y,R(r − 1, m − 1)) = ρ_{RM}(r − 1, m − 1). We have

d((u, u + v), (0, y)) = wt(u) + d(u + v, y) ≥
wt(u) + d(v, y) − wt(u) = d(v, y) ≥ ρ_{RM}(r − 1, m − 1),

and (21) follows from the inductive definition of R(r, m). Now, let (x_{1}, x_{2}) be an arbitrary vector. Then it can be approximated by first choosing u, a closest word to x_{1} in R(r, m−1), and then v, a closest word to x_{2}+u in R(r−1, m−1). Thus

d((x_{1}, x_{2}), (u, u + v)) = d(x_{1}, u) + d(x_{2}, u + v)
≤ ρ_{RM}(r, m − 1) + ρ_{RM}(r − 1, m − 1).
□

Now consider the second order Reed-Muller codes.

Clearly, ρ_{RM}(2, 2) = 0, ρ_{RM}(2, 3) = 1, ρ_{RM}(2, 4) = 2, ρ_{RM}(2, 5) = 6. Since ρ_{RM}(1, 5) = 12, from (22) we have ρ_{RM}(2, 6) ≤ 18. Actually, there exists a binary 64-tuple associated with the polynomial

v_{6}(v_{1}v_{2}v_{3} + v_{1}v_{4}v_{5} + v_{2}v_{3} + v_{2}v_{4} + v_{3}v_{5}) + (v_{6} + 1)(v_{1}v_{2}v_{3} + v_{1}v_{4}v_{5}), (23)

which has been verified [136] to be at distance 18 from any codeword of R(2, 6). Hence, ρ_{RM}(2, 6) = 18. The value of ρ_{RM}(2, 7) is still not known.

Now we proceed with considering the covering radius of R(m − 3, m). The codes R(2, m) and R(m − 3, m) are dual. The weight distribution of R(2, m) contains m+1 or m+2 nonzero components for, correspondingly, odd and even m. Knowledge of the number of nonzero weights in R(2, m) along with the Delsarte theorem give us a tight bound for ρ_{RM}(m − 3, m) [121].

Theorem 9.9

ρ_{RM}(m − 3, m) = \{ \begin{matrix}m + 2 & for m even, \\ m + 1 & for m odd. \end{matrix}

□

Now consider the general case. In the table the best known numerical bounds for ρ_{RM}(r, m), m ≤ 9 are presented. The table uses inequalities (20) and (21). However, it is possible to improve on repeated use of (20) and (21). Such inequalities have been obtained by Hou in [88, 89]. Their proofs are quite technical and are omitted.

Lemma 9.10 If 2 ≤ k ≤ m − r − 1, then

ρ_{RM}(r + k, m + k) ≥ ρ_{RM}(r, m) + 2(k − 1).  (24)

Moreover, if R(r, m) has a coset with minimal weight ρ_{RM}(r, m) that does not contain any vector of weight ρ_{RM}(r, m) + 2, then

ρ_{RM}(r + k, m + k) ≥ ρ_{RM}(r, m) + 2k.  (25)
□

Lemma 9.11 For r ≤ m − 2

ρ_{RM}(r + 1, m + 2) ≥ 2ρ_{RM}(r, m) + 2,  (26)
□

Table 3: Bounds for covering radii of Reed-Muller codes

r \ m 1 2 3 4 5 6  7  8  9
1  0 1 2 6 12 28  56  120  240-244
2  0 1 2 6 18^{s} 40^{h1}-44^{h2} 84^{h1}-100 171^{c}-220
3  0 1 2 8 20^{h1}-23 ^{h1} 43^{c}-67 111^{c}-167
4  0 1 2  8  22^{h1}-31 58^{c} - 98
5  0 1  2  10  23^{c} - 41
6  0  1  2  10
7  0  1  2
8  0  1
9  0

All unmarked upper bounds are from (22); For r = 1, Theorem 9.3 is used for m even and Theorem 9.5 is used for m odd; For r = m − 3 a result from [121] is used; c - sphere covering bound; h1 - obtained in [88]; h2 - obtained in [89]; s - the upper bound (22), and the lower bound from constructing a vector corresponding to the polynomial (23) (see [136]) at distance 18 from the code;

Although for finite lengths there are still many unknown exact values, asymptotically for long Reed-Muller codes it is possible to derive reasonably tight bounds. The lower bound is simply the sphere covering one. The upper bound is derived from a thorough use of inequality (22) with properly chosen initial conditions. G.Cohen and S.Litsyn [32] derived tight asymptotic bounds on ρ_{RM}(r, m).

The [2^{m} − 1, m, 2^{m−1}] simplex code is obtained from from R(1, m) by shortening, and its covering radius is easy to obtain.

Theorem 9.12 The covering radius ρ of the [2^{m} − 1, m, 2^{m−1}] simplex code C is 2^{m−1} − 1.

Proof. As the columns of a generator matrix of C consist of all the distinct nonzero binary vectors of length m, C has strength 1. Hence by the Norse bound, ρ ≤ 2^{m−1} − 1. Recall that all non-zero vectors (except the all-one vector) in R(1, m) have weight 2^{m−1}. As C is obtained from R(1, m) by shortening, the coset of C containing the all-one vector has weight 2^{m−1}−1. Hence 2^{m−1}−1 ≤ ρ. □

In [67] Helleseth and Mattson study orphans (which they call urcosets) of the simplex code. Among other things they prove that a length 2^{m} − 1 simplex code has no orphans of weight 2^{m−1} − 2 for m ≥ 5 and none of weight 2^{m−1} − 3 for m ≥ 7. The next theorem due to Brualdi and Pless [13] ensures the existence of many even weight orphans of R(1, m).

Theorem 9.13 Let m and i be integers with 2 ≤ i ≤ m and m ≡ i (mod 2). Then R(1, m) has orphans of weight 2^{m−1}−2^{(m+i−4)/2} whose weight distribution is as follows.

A_{2^{m−1}±2^{(m+i−4)/2}} = 2^{m−i+2}, A_{2^{m−1}} = 2^{m+1} − 2^{m−i+3}.

When m = i, each such orphan has four disjoint coset leaders.

If a coset of R(1, m) has four coset leaders of weight 2^{m−2}, then this coset is an orphan and its weight distribution is the same as the previous one for m = i. There are \binom{2^{m}−1}{2}/3 such cosets. □

If m is even and i = 2, a coset of weight 2^{m−1} − 2^{(m−2)/2} is a coset whose weight is the covering radius of R(1, m), hence necessarily an orphan. The weight distribution of this orphan in Theorem 9.13 is that given in Corollary 5.11.

In [12] it was shown that for m ≥ 2, R(1, m) has an orphan of even weight w whenever 2^{m−2} ≤ w ≤ 2^{m−1} − 2^{⌊(m−1)/2⌋}.

All the orphans of R(1, m) have been identified for 1 ≤ m ≤ 5 [13]. For r ≤ 4, all the orphans in R(1, m) are those described in Theorem 9.13. For r = 5 there are orphans as given in Theorem 9.13 in addition to orphans of weight 10 (consistent with the result of [12]). The covering radius of R(1, 5) is 12 and there are orphans of this weight whose distance distribution is given in Theorem 9.13. However there are other orphans of weight 12.

10 Covering radius of algebraic codes

We denote by B(t, m) the binary primitive narrow-sense BCH code of length 2^{m} − 1 and designed distance 2t + 1. Denote ρ(B(t, m)) by ρ_{B}(t, m).

Clearly, ρ_{B}(1, m) = 1. Let t > 1. We start with a lower bound on ρ_{B}(t, m).

Lemma 10.1 If t ≤ 2^{⌊(m−1)/2⌋} then

ρ_{B}(t + 1, m) ≥ 2t − 1.

Proof. Follows from B(t, m) ⊂ B(t + 1, m) and the supercode lemma. □

The following theorem is due to Gorenstein, Peterson and Zierler [54].

Theorem 10.2 For m ≥ 3

ρ_{B}(2, m) = 3.

Proof. The lower bound follows from Lemma 10.1. The upper bound is from Delsarte’s theorem. □

For t = 3 it is necessary to analyze many more cases to prove

Theorem 10.3 For m ≥ 4

ρ_{B}(3, m) = 5.

Proof. (sketch) The lower bound is again due to Lemma 10.1. For odd m we may use Delsarte’s theorem, and the fact that the duals of BCH codes have 5 nonzero weights gives the equality sought [4]. For even m there are already 7 nonzero weights in B^{⊥}(3, m) and Delsarte’s theorem does not work properly. However, an ad hoc analysis of solvability of a relevant system of equations gives the claim. This was proved for m ≡ 0 (mod 4) by van der Horst and Berger [81], for m ≡ 2 (mod 4) by Helleseth [64], and for m ≡ 1, 3 (mod 4) by Assmus and Mattson [4]. □

Not much is known about ρ_{B}(t, m) for t > 3. Computer calculations were done for cyclic codes of length up to 63 [45, 46]. The results on primitive narrow-sense BCH codes are summarized in Table 4.

In spite of our poor knowledge about covering radii of short BCH codes, we can show that for long enough BCH codes the lower bound in Lemma 10.1 is the true bound. We start, however, from a weaker result due to F.Levy-dit-Vehel and S.Litsyn [105]:

Theorem 10.4 ρ_{B}(t, m) ≤ 2t, provided Table 4: Covering radius of binary primitive narrow-sense BCH codes

\begin{matrix}n & k & t & d & ρ \\ 7 & 4 & 1 & 3 & 1 \\ 15 & 11 & 1 & 3 & 1 \\ 15 & 7 & 2 & 5 & 3 \\ 15 & 5 & 3 & 7 & 5 \\ 31 & 26 & 1 & 3 & 1 \\ 31 & 21 & 2 & 5 & 3 \\ 31 & 16 & 3 & 7 & 5 \\ 31 & 11 & 4 & 11 & 7 \\ 31 & 6 & 6 & 15 & 11 \\ 63 & 57 & 1 & 3 & 1 \\ 63 & 51 & 2 & 5 & 3 \\ 63 & 45 & 3 & 7 & 5 \\ 63 & 39 & 4 & 9 & 7 \\ 63 & 36 & 5 & 11 & 9 \end{matrix}

(i) m ≥ 15 for t = 4;

(ii) m ≥ 20 for t = 5;

(iii) 2^{m} ≥ 4(t − 1)^{2}(t!)^{2}.

Proof. By the form of the parity-check matrix of B(t, m), we have that ρ_{B} is the smallest integer such that for any (b_{1}, …, b_{t}) in F_{2^{m}}^{t} \ {0} and for at least one i ≤ ρ_{B}(t, m), the system

\{ \begin{matrix}x_{1} + … + x_{i} & = & b_{1} \\ x_{1}^{3} + … + x_{i}^{3} & = & b_{2} \\ ⋮ & ⋮ & ⋮ \\ x_{1}^{2t−1} + … + x_{i}^{2t−1} & = & b_{t} \end{matrix}  (27)

has a solution (x_{1}, …, x_{i}) ∈ (F_{2^{m}} \ {0})^{i}, with x_{l} ≠ x_{j} for l ≠ j. (Note that, if (b_{1}, …, b_{t}) = 0, it corresponds to the zero codeword, and, by convention, we assume in this case that i = 0). Using an idea of Tietäväinen [152] (see also [65]), we consider the homogeneous system

\{ \begin{matrix}x_{1} + … + x_{i} & = & b_{1}y \\ x_{1}^{3} + … + x_{i}^{3} & = & b_{2}y^{3} \\ ⋮ & ⋮ & ⋮ \\ x_{1}^{2t−1} + … + x_{i}^{2t−1} & = & b_{t}y^{2t−1} \end{matrix}  (28)

If this system has a solution (x_{1}, …, x_{i}, y) = (ξ_{1}, …, ξ_{i}, ζ), with ζ ∈ F_{2^{m}} \ {0}, then the first one has the solution (ξ_{1}/ζ, …, ξ_{i}/ζ).

A straightforward consequence of the fact that

∑_{x∈F_{2^{m}}}(−1)^{T r(α x)} = 2^{m}δ_{α,0}

(T r being the trace function from F_{2^{m}} onto F_{2}), is that the number of solutions (x_{1}, …, x_{i}, y) ∈ (F_{2^{m}} \ {0})^{i+1} of (28), with x_{i} ≠ x_{j} for i ≠ j, is

N_{i} = \frac{1}{2^{mt}} ∑_{0<x_{1}<...<x_{i},y≠0}

∑_{α_{1}∈F_{2^{m}}}(−1)^{T r(α_{1}(x_{1}+...+x_{i}+b_{1}y))} … ∑_{α_{t}∈F_{2^{m}}}(−1)^{T r(α_{t}(x_{1}^{2t−1}+...+x_{i}^{2t−1}+b_{t}y^{2t−1}))},

(after having chosen an order on F_{2^{m}}).

Recalling the definition of MacWilliams transform, we get :

2^{mt}N_{i} = ∑_{α_{1},...,α_{t}} P_{i}(w\underline{α}) ∑_{y≠0}(−1)^{T r(α_{1}b_{1}y+...+α_{t}b_{t}y^{2t−1})},  (29)

where P_{i} is the i-th Krawtchouk polynomial, and w\underline{α} is the weight of the word c\underline{α} :

w\underline{α} = \frac{2^{m} − 1 − ∑_{x∈F_{2^{m}} \\{0\}}(−1)^{T r(α_{1}x+...+α_{t}x^{2t−1})}}{2} .

We are interested in showing that, for m large enough, there exists (at least one) i ≤ 2t, such that N_{i} ≠ 0. If, for a non-zero tuple (a_{0}, …, a_{2t}), we have :

∑_{i=0}^{2t} a_{i}N_{i} ≠ 0,

then at least one N_{i} is non-zero, and thus ρ_{B}(t, m) ≤ 2t.

We show here that, for a non-zero (2t+1)-tuple (a_{0}, …, a_{2t}), ∑_{i=0}^{2t} a_{i}N_{i} > 0 starting from some length.

In order to find the best lower bound for 2^{m}, we have to choose a polynomial g_{2t}(x) = ∑_{i=0}^{2t} a_{i}, non-negative in [d′, 2^{m} − d′], positive in 0 and of degree 2t, with maximum ratio \frac{g_{2t}(0)}{a_{0}}.

If one chooses the polynomial

g_{2t}(x) = (∑_{i=0}^{t} P_{i}(x))^{2},  (30)

the result follows after some calculations. □

A better bound was obtained by A. Tietäväinen [153] using Deligne’s bound:

Theorem 10.5 If q = 2^{m} ≥ (2t)^{4t−2} and e is of the form 2^{u} + 1 then

ρ_{B}(t, m) = 2t − 1.
□

Vlädut and Skorobogatov [157] using algebraic geometry and a deep theorem of Lang and Weil proved that at least for very long BCH codes the lower bound is attained.

Theorem 10.6 There is a constant m_{0} depending on e such that for all m ≥ m_{0}

ρ_{B}(t, m) = 2t − 1.
□

S. D. Cohen [38] has proved that m_{0} can be upperestimated as

2^{m_{0}} ≤ (2t − 3)((2t − 1)!)^{2}.

The nonprimitive case can be treated in a more easy way [105]:

Theorem 10.7 The t-error correcting BCH-code of length n = \frac{2^{m}−1}{h}, h > 1, has covering radius ρ = 2t, provided

2^{m} ≥ ((2t − 1)N − 1)^{2}(t!)^{2}.

Proof. The proof is essentially the same as that in the primitive case, so that we just outline the main idea.

Instead of system (28), we consider the system

\{ \begin{matrix}x_{1}^{h} + … + x_{i}^{h} & = & b_{1}y^{h} \\ x_{1}^{3h} + … + x_{i}^{3h} & = & b_{2}y^{3h} \\ ⋮ & ⋮ & ⋮ \\ x_{1}^{(2t−1)h} + … + x_{i}^{(2t−1)h} & = & b_{t}y^{(2t−1)h} \end{matrix}

Analogously to the primitive case we conclude that under the conditions in the theorem the covering radius is at most 2t. The proof is concluded by demonstrating that there exists a coset of minimum weight 2t, see [105, 157] for details. □

For estimates of the covering radius of cyclic codes see [45, 46, 65, 156].

Duals of BCH codes

Determining the covering radius ρ_{B}^{⊥}(t, m) of duals of BCH codes B(t, m) is related to lower bounds on exponential sums. Tietäväinen [154] using knowledge of dual distance and a generalization of the Norse bounds proved

Theorem 10.8

ρ_{B}^{⊥}(t, m) ≤ 2^{m−1} − 1 − (\sqrt{t} − ^{6} \sqrt{t})\sqrt{2^{m} − t − 2} .
□

Goppa codes

Consider a Goppa code Γ(L, g), where g(x) is a polynomial over F_{q}, q = 2^{m}, of degree t. Moreover, assume that g(x) has no roots in F_{q} (i.e. L = F_{q}). To estimate covering radius we study solvability of the system

\begin{aligned}1/g(x_{1})+ & … & +1/g(x_{r}) & = β_{1} \\ x_{1}/g(x_{1})+ & … & +x_{r}/g(x_{r}) & = β_{2} \\ … & … & … & … \\ x_{1}^{e−1}/g(x_{1})+ & … & +x_{r}^{e−1}/g(x_{r}) & = β_{e}. \end{aligned}

The approach is similar to the one in case of BCH codes, but in this case O.Moreno and C.Moreno [123] proposed using the Bombieri bound instead of the Deligne bound. This yields the following result of F.Levy-dit-Vehel and S.Litsyn [104, 106]:

Theorem 10.9 Provided 2^{m} ≥ 4(1 + ε(t))(t − 1)^{4t+2},

ρ(Γ(L, g)) ≤ 2t + 1,

where ε(2) = 1023, ε(3) = 8.610^{−5}, ε(t) ≤ 1.0510^{−7} for t ≥ 4. □

For estimates of covering radius of algebraic-geometric codes see [92, 93, 139].

Self-dual codes

The covering radius of extremal doubly even self-dual codes was studied by Assmus and Pless [5]. The bounds on ρ_{S}(m), the covering radius of extremal doubly even self-dual code of length n = 8m are given in Table 5. It is not necessarily so that all extremal doubly-even codes with the same parameters have the same covering radius. There are some [40, 20, 8] doubly-even codes with covering radius 7 and some with covering radius 8 [112].

Theorem 10.10

0.88..m = 8mH^{−1}(0.5) < ∼ρ_{S}(m) ≤ 2m − 2⌊m/3⌋.

Proof. The upper bound is simply the Delsarte bound, the lower bound is the asymptotic form of the sphere covering bound. □

Table 5: Covering radii of extremal doubly even codes of length ≤ 64

\begin{matrix}n & 8 & 16 & 24 & 32 & 40 & 48 & 56 & 64 \\ k & 4 & 8 & 12 & 16 & 20 & 24 & 28 & 32 \\ d & 4 & 4 & 8 & 8 & 8 & 12 & 12 & 12 \\ ρ_{S}(m) & 2 & 2 & 4 & 6 & 6–8 & 8 & 8–10 & 8–12 \end{matrix}

11 Asymptotical problems

We now study several asymptotical problems related to covering radius. We are interested in the behavior of parameters of codes when the length n tends to infinity. It is convenient to study values normalized to the length n of an (n, M, d)ρ code C, i.e. the normalized covering radius ϱ(C) = ρ/n, normalized minimum distance δ(C) = d/n, normalized dual distance δ^{⊥}(C) = d^{⊥}/n, rate R(C) = (log_{2} M)/n, etc.

Coverings of exponential size

We start by considering the problem of finding the smallest cardinality of a binary code having a prescribed covering radius. By the sphere covering bound for any (n, M)ρ code C the cardinality is lowerbounded by

M ≥ 2^{n}/V (n, ρ).

Taking logarithms on both sides we obtain

log_{2} M ≥ n − log_{2} V (n, ρ),

and for growing n we have

ρ(C) = log_{2} M/n ≥ 1 − H(ϱ(C)).  (31)

Below it is demonstrated (see [43]) that virtually all codes have covering radius asymptotically achieving (31).

Theorem 11.1 For any n and ρ ≤ n there exist (n, M)ρ codes with

M = ⌈n2^{n} ln 2/V (n, ρ)⌉.

Proof. Given a radius ρ and a code C, define the set Q_{ρ}(C) of vectors in F^{n} that are not covered, i.e. have distance more than ρ from every codeword. Consider the normalized cardinality

q(C) = q_{ρ}(C) = 2^{−n}|Q_{ρ}(C)|.

Let C_{M} denote the set of all codes (repeated words allowed) of size M. Clearly

|C_{M}| = \binom{2^{n}}{M}.

Now, let us estimate ∑ q_{ρ}(C), where the sum is taken over all C ∈ C_{M}.

∑_{C∈C_{M}} q_{ρ}(C) = 2^{−n} ∑_{C∈C_{M}} |Q_{ρ}(C)|

= 2^{−n} ∑_{C∈C_{M}}  ∑_{x∈F^{n}:d(x,C)>ρ} 1

= 2^{−n} ∑_{x∈F^{n}}  ∑_{C∈C_{M}:d(x,C)>ρ} 1

= 2^{−n} ∑_{x∈F^{n}} \binom{2^{n} − V (n, ρ)}{M} = \binom{2^{n} − V (n, ρ)}{M}.

The last expression counts the number of codes of size M such that spheres of radius ρ centered at their codewords do not cover a particular vector of F^{n}. Now, in the set C_{M} there exists at least one code, say C^{∗}, with

q_{ρ}(C^{∗}) ≤ \frac{∑_{C∈C_{M}} q_{ρ}(C)}{|C_{M}|} = \binom{2^{n} − V (n, ρ)}{M}/\binom{2^{n}}{M}

≤ \frac{(2^{n} − V (n, ρ))(2^{n} − V (n, ρ) − 1) … (2^{n} − V (n, ρ) − M + 1)}{2^{n}(2^{n} − 1) … (2^{n} − M + 1)}

≤ \frac{(2^{n} − V (n, ρ))^{M}}{(2^{n})^{M}} = (1 − 2^{−n}V (n, ρ))^{M}.

Let us choose M = ⌈n2^{n} ln 2/V (n, R)⌉, which, by

(1 − 1/x)^{x} ≤ e^{−1} for x ≥ 1,

implies

q_{ρ}(C^{∗}) < 2^{−n},

and thus

|Q_{ρ}(C^{∗})| < 1.

But |Q_{ρ}(C^{∗})| is an integer, so |Q_{ρ}(C^{∗})| = 0, and C^{∗} has covering radius ρ, proving the claim. □

In terms of normalized parameters of codes we proved the following.

Theorem 11.2 Let 0 ≤ ϱ < 1/2. Then there exists an infinite sequence of codes C_{n} of growing length n with ϱ(C_{n}) → ρ such that

1 − H(ϱ) ≤ R(C_{n}) ≤ 1 − H(ϱ) + O(n^{−1} log n).
□

A simple refinement of the argument shows that the bound of the theorem holds for almost all codes.

Theorem 11.3 For any positive real number ε, the fraction α of (n, M)ρ coverings with

M = ⌈(1 + ε)n2^{n} ln 2/V (n, R)⌉ ,

satisfies

α ≥ 1 − 2^{−εn}.

Proof. Notice that if C is not a ρ-covering then q_{ρ}(C) ≥ 2^{−n}. If the proportion of non-coverings in C_{M} exceeds 1 − α,

∑_{C∈C_{M}} q_{ρ}(C) ≥ 2^{−n}(1 − α)|C_{M}|.

On the other hand, choosing M as in the statement of the theorem we have

∑_{C∈C_{M}} q_{ρ}(C) ≤ 2^{−n(1+ε)}|C_{M}|.

Comparing the last two inequalities gives the lower bound on α. □

Consider now the case of linear codes.

Lemma 11.4 For any U ⊂ F^{n} there exists x ∈ F^{n} such that

|U ∩ (U + x)| ≤ |U|^{2}/2^{n}.

Proof. The multiset V = ∪_{x∈F^{n}}(U + x) is just the |U|-times repetition of F^{n}. Hence every element of U appears in V exactly |U| times, and there are all in all |U|^{2} elements from U in V. Since V consists of 2^{n} cosets of U, there is at least one coset containing at most |U|^{2}/2^{n} elements from U. □

The lemma allows us to obtain the following result [25, 53] (see [26, 27]):

Theorem 11.5 For any n and ρ ≤ n there exist [n, k]ρ codes with

k = ⌈n − log_{2} V (n, ρ) + log_{2} n + log_{2}(ln 2)⌉.

Proof. We construct the desired code in a recursive manner. We start from the code C_{0} consisting of one word 0^{n}. At the i-th step of the procedure we add a coset C_{i} + x_{i} to C_{i}, thus constructing C_{i+1}. The x_{i} is chosen to minimize |Q_{ρ}(C_{i+1})|. Noticing that

Q_{ρ}(C_{i} + x) = x + Q_{ρ}(C_{i}),

and

Q_{ρ}(C_{i+1}) = Q_{ρ}(C_{i}) ∩ Q_{ρ}(C_{i} + x) = Q_{ρ}(C_{i}) ∩ (x + Q_{ρ}(C_{i})).

From the lemma we deduce

|Q_{ρ}(C_{i+1})| ≤ |Q_{ρ}(C_{i})|^{2}/2^{n},

or, in the normalized form

q_{ρ}(C_{i+1}) ≤ (q_{ρ}(C_{i}))^{2}.  (32)

Since q_{ρ}(C_{0}) = (1 − 2^{−n}V (n, ρ)) we get

q_{ρ}(C_{i}) ≤ (1 − 2^{−n}V (n, ρ))^{2^{k}},

and the proof ends exactly like in the case of unrestricted codes. □

In terms of normalized parameters of codes we proved the following.

Theorem 11.6 Let 0 ≤ ϱ < 1/2. Then there exists an infinite sequence of codes C_{n} of growing length n with ϱ(C_{n}) → ρ and

1 − H(ϱ) ≤ R(C_{n}) ≤ 1 − H(ϱ) + O(n^{−1} log n).
□

V.Blinovskii [8] (see also [9, 10]) proved that the proportion of linear codes achieving the bound claimed is quite big. The proof proceeds in two stages. First it is checked that if we choose the size of codes in such a way that every point is on average ρ-covered by n^{α}, α > 1, codewords, then almost all codes are almost ρ-coverings, i.e. ρ-cover all the space except for maybe a small number of vectors. The procedure of successive appending ⌈log_{2} n⌉ cosets to these almost ρ-coverings will convert them into complete ρ-coverings without essentially decreasing their proportion.

Theorem 11.7 Let 0 ≤ ϱ < 1/2. Let C_{k,n} be the set of 2^{kn} linear codes generated by all possible binary k × n matrices. Let ρ_{n} = ⌊ϱn⌋. Then there exists a sequence k_{n} with

k_{n}/n ≤ 1 − H(ϱ) + O(n^{−1} log n)

such that the fraction of codes C_{n} ∈ C_{k,n} that are ρ_{n}-coverings tends to 1. □

The fact that almost every linear code achieves asymptotically the sphere covering bound allows, as mentioned by R. Roth (personal communication), the following construction of infinite length coverings. Given R, let us take a sequence of numbers k(n) such that k(n)/n → R when n tends to infinity. Given k(n) we construct C = ∑ ⊕C_{i}, the direct sum of all linear codes C_{i} ∈ C_{2^{k(n)}}. Notice, that this procedure is constructive: we set all possible 0 − 1 matrices of size k(n)×n on the diagonal of a block-diagonal k(n)2^{k(n)n}×n2^{k(n)n} (generator) matrix, and put zeros elsewhere. The parameters of the resulting code are

[N = n2^{k(n)n}, k(n)2^{k(n)n}]ρ = ∑ ρ(C_{i}).

By the theorem the parameters of the code satisfy asymptotically the sphere covering bound. So, in contrast to error-correcting codes, for coverings we achieve the best asymptotic bound constructively.

Density of coverings

Now we consider the asymptotical behaviour of code parameters when the covering radius is fixed and the length grows. The density of a covering, defined for an (n, M)ρ code C as

μ(C) = M V (n, ρ) 2^{−n},

i.e. the ratio between the total size of spheres in the covering and the size of the space. Given n and ρ we define the minimal density

μ(n, ρ) = K(n, ρ) V (n, ρ) 2^{−n}.

Analogously, we define for linear codes

μ[n, ρ] = k[n, ρ] V (n, ρ) 2^{−n}.

By the sphere covering bound, the density is at least 1, and equals 1 only for perfect codes. So, for the Hamming codes

μ(H_{m}) = μ(2^{m} − 1, 1) = μ[2^{m} − 1, 1] = 1, m = 1, 2, ….

The sphere covering bound along with codes that are direct sums of Hamming codes and a total space yields

k[n, 1] = n − ℓ, if 2^{ℓ} ≤ n + 1 < 2^{ℓ+1},

and

μ[n, 1] = 2^{−ℓ}(n + 1), if 2^{ℓ} ≤ n + 1 < 2^{ℓ+1},  (33)

giving

1 ≤ μ[n, 1] < 2.

Define

μ^{∗}(ρ) = lim_{n→∞} sup μ(n, ρ),

and

μ^{∗}[ρ] = lim_{n→∞} sup μ[n, ρ],

the asymptotically (worst) densities for coverings of given radius. Clearly, μ^{∗}(ρ) ≤ μ^{∗}[ρ].

The above results on the density of linear coverings of radius 1 yield

μ^{∗}[1] = 2.

Theorem 11.8 For fixed ρ

1 ≤ μ^{∗}(ρ) ≤ μ^{∗}[ρ] < const

Proof. From (33),

K(n, 1) ≤ k[n, 1] < \frac{2^{n+1}}{n + 1},

so for the ρ-times direct sum of a code achieving this bound with itself

K(ρn, ρ) ≤ k[ρn, ρ] < \frac{2^{nρ+ρ}}{(n + 1)^{ρ}} .

Therefore,

μ(n, ρ) ≤ μ[n, ρ] < \frac{2^{ρ}V (ρn, ρ)}{(n + 1)^{ρ}}

= \sqrt{\frac{ρ}{2π}} (2e)^{ρ}(1 + o(1)),

as N = ρn → ∞, as claimed. □

We now prove that μ^{∗}(1) = 1. First we need some recursive relations for the density of coverings.

Lemma 11.9 If C is a covering of F^{n}, then there exists a covering C′ of F^{n+ℓ}, ℓ = 0, 1, 2, …, with density

μ(C′) = μ(C)\frac{1 + n + ℓ}{1 + n}.

Proof. Choose C′ = C ⊕ F^{ℓ}. □

Thus, for growing n having a code of some constant density, we have the same density for the interval of lengths [n, n + o(n)].

Lemma 11.10 If there exists a 1-covering C of F^{n} then there exist 1-coverings of F^{N}, N = 2^{j}n + 2^{j} − 1, j = 0, 1, 2, …, with the same density as C.

Proof. The lemma follows by using the (u, u + v)-construction j times. □

Define the density of a q-ary (n, M)1 covering C analogously to the binary case, namely,

μ(C) = MV_{q}(n, 1)/q^{n} = M(1 + (q − 1)n)q^{−n}.

Lemma 11.11 If there exists a 2^{ℓ}-ary (N, M)1 covering V then there exists a binary (N(2^{ℓ} − 1), 2^{N(2^{ℓ}−ℓ−1)}M)1 covering with density μ(V).

Proof. Let H_{ℓ} be the Hamming code of length n = 2^{ℓ} − 1. Partition the space F^{n} to the cosets of H_{ℓ}, namely,

F^{n} = (C_{0} = H_{ℓ}) ∪ C_{1} ∪ … C_{n−1}.

Every vector in F^{n} belongs exactly to one coset C_{i} and is at distance one from all other cosets C_{j}, j ≠ i. The size of every coset is 2^{ℓ}. Now the cascading construction (Theorem 3.5) can be applied with B = V. □

To construct nonbinary covering codes we use the following ”supercode” construction. We formulate it for the particular case we need.

Lemma 11.12 Let q be a prime power with q ≤ 2^{ℓ}, and let C be a linear [N, k]1 covering code. Then there exists a (nonlinear) 2^{ℓ}-ary (N, M)1 covering code V with

M ≤ q^{k−N}2^{ℓN},

and density

μ(V) ≤ μ(C)\frac{1 + (2^{ℓ} − 1)n}{1 + (q − 1)n}.

Proof. Assume some partition of F_{2^{ℓ}} into q distinct parts, and use it to establish a (surjective) one-to-many mapping σ : F_{q} → F_{2^{ℓ}}. As the supercode V we take all vectors (v_{1}, …, v_{n}) ∈ (F_{2^{ℓ}})^{n} such that

σ^{−1}(v) = (σ^{−1}(v_{1}), …, σ^{−1}(v_{n})) ∈ C.

Clearly, V is a 1-covering. Indeed, for every x ∈ (F_{2^{ℓ}})^{n} there is a vector generated by a σ^{−1}(v) ∈ C, where d(σ^{−1}(v), σ^{−1}(x)) ≤ 1, which 1-covers x. Now we have to estimate the size of the code. This is difficult to do for a particular code, but is easy to compute its average over all the cosets of the code. Let us partition (F_{q})^{n} to the q^{n−k} cosets of C, and then apply the defined transform to the 2^{ℓ}-ary vectors with all the words of (F_{q})^{n}. This gives rise to (2^{ℓ})^{n} different vectors, partitioned to q^{n−k} cosets. Having in mind that every coset of C is also a 1-covering, and that there exists a part having at most the average number of words, we establish the claim. □

Applying Lemma 11.12 to the q-ary Hamming codes with parameters [N = (q^{i} −1)/(q−1), k = N −i]1, and using the evident inequality (1+(2^{ℓ} −1)n)/(1+ (q − 1)n) < (2^{ℓ} − 1)/(q − 1) for q ≤ 2^{ℓ}, we get the following corollary.

Corollary 11.13 For q a prime power with q ≤ 2^{ℓ}, there exist 1-coverings V of F_{q}^{N}, N = (q^{i} − 1)/(q − 1), i = 1, 2, …, of density

μ(V) < \frac{2^{ℓ} − 1}{q − 1}.

□

Now from Lemma 11.11, coverings from the previous corollary and Lemma 11.10 we conclude

Lemma 11.14 For prime power q with q ≤ 2^{ℓ}, and i = 1, 2, …, j = 0, 1, …, there exist 1-coverings C(l, i, j) of length

2^{j}(2^{l} − 1)\frac{q^{i} − 1}{q − 1} + 2^{j} − 1

and of density

μ(C(l, i, j)) < \frac{2^{l} − 1}{q − 1}.

□

We see that choosing as q the maximal prime power less than 2^{ℓ}, we get a sequence of coverings of density approaching 1 when n grows and q/2^{ℓ} → 1. We adopt the following strategy. Given l we choose i and j in such a way that the lengths of the resulting coverings belong to the same interval [2^{m−1}, 2^{m} − 1]. We show that for big enough ℓ the lengths of the resulting codes form a dense subsequence of lengths, i.e. every value of length in the interval exceeds some point at the subsequence by o(n), and finally we use Lemma 11.9 to cover all the interval. This result was proved by Kabatyanskii and Panchenko [94] (see [133] for the nonbinary case).

Theorem 11.15

μ^{∗}(1) = 1.

Proof. Let q = 2^{ℓ}(1 − ε), as ℓ grows. From results on the density of prime numbers it is known that ε is O(2^{βℓ}), β < 1. Let z = ⌊−1/ log_{2}(1−ε)⌋. Noticing that for l big enough we get by Lemma 11.14 the sequence of lengths 2^{j+ℓ}q^{i−1}(1+ o(1)), we assume that j is always chosen such that j = l(z − i), and so i ≤ z. Then the sequence of lengths becomes

2^{ℓz}(1 − ε)^{i−1}(1 + o(1)).

If i runs from 1 to z the length changes from 2^{ℓz}(1 + o(1)) to 2^{ℓz}(1 − ε)^{z−1} = 2^{ℓz−1}(1 + o(1)). Checking that the distance between two consecutive lengths is o(2^{ℓz}), we conclude that the values of lengths constitute a dense subsequence of points in the interval [2^{ℓz−1}, 2^{ℓz}] where the density of C(ℓ, i, j) is at most (2^{ℓ}−1)/(q−1) → 1. Application of Lemma 11.9 fully covers the interval. Further applying Lemma 11.10 in turn with Lemma 11.9 to the obtained coverings allows extending the conclusion to the next interval [2^{ℓz}, 2^{ℓz+1}], etc. □

Conjecture 11.16 For ρ ≥ 2, a constant, μ^{∗}(ρ) = 1. □

The problem seems to be very difficult. Define μ_{∗}(ρ) (resp. μ_{∗}[ρ]) analogously to μ^{∗}(ρ) (resp. μ^{∗}[ρ]) substituting lim sup by lim inf, we can estimate the density of the most sparse infinite families of codes. The best known results for radii 2, 3 and 4 are

μ^{∗}[2] ≤ 1.424, μ^{∗}[3] ≤ 1.375, μ^{∗}[4] ≤ 2.34,

due to Davydov and Drozhzhina-Labinskaya [41]. Struik [151] indicated an infinite subsequence of lengths for which μ_{∗}(2) = 1. The codes are constructed as the blockwise sum of the Hamming codes partitioned into the cosets of Preparata codes, and a direct sum of Hamming codes.

Coverings of small size

As the following theorem demonstrates, the sphere covering bound cannot be improved for a family of codes of size n^{α} with α > 1.

Theorem 11.17 There exist (n, M)ρ codes with

n/2 − \sqrt{n log_{2} M ln 2/2} ≤ ρ ≤ n/2 − \sqrt{n (log_{2} K − log_{2} n + O(1))\frac{ln 2}{2}} .

Proof. Only the lower bound is non-trivial. The sphere covering bound gives the exact bound valid for all M and ρ:

H(ϱ) ≥ 1 − R.

Using the easily checked inequality

H (1/2 + \sqrt{x}) ≤ 1 − 2x/ ln 2,

we infer

1 − 2\frac{(1/2 − ϱ)^{2}}{ln 2} ≥ 1 − R,

giving the claim. □

However, the sphere covering bound can be further improved for codes of size O(n^{1+o(1)}). The bounds rely heavily on bounds for discrepancy of sets, a concept extensively studied in combinatorics (see Alon and Spencer [3] and references therein). We omit details.

Theorem 11.18 For every (n, M)ρ code

ρ ≥ n/2 − const \sqrt{n ln(M/n)} if M = n^{1+o(1)};
ρ ≥ n/2 − 5.32 · \sqrt{n} if M = n;
ρ ≥ n/2 − 12\sqrt{M} if M = o(n).
□

Normalized covering radius as a function of dual distance

Here we derive asymptotic bounds for the normalized covering radius ϱ as a function of normalized dual distance δ^{⊥}.

Let C = (C_{n})_{n=1}^{∞} be a sequence of codes C_{n} of length n, dual distance d^{⊥} = d^{⊥}(n) and covering radius ρ = ρ(n) where ρ/n → ϱ and d^{⊥}/n → δ^{⊥} when n → ∞.

We start with a lower bound.

Theorem 11.19 There exist sequences C such that, for 0 < δ^{⊥} < \frac{1}{2},

ϱ ≥ H_{2}^{−1}(1 − H_{2}(δ^{⊥})),  (34)

Proof. Duals of codes satisfying the Varshamov-Gilbert bound have the claimed lower bound on covering radius due to the sphere covering bound. □

Now we proceed with upper bounds. By a result of Tietäväinen [154, 155] the covering radius is upperbounded by x_{d^{⊥}/2}^{n}, the smallest zero of P_{d^{⊥}/2}^{n}(x), the Krawtchouk polynomial of degree d^{⊥}/2. Asymptotically,

lim_{n→∞} \frac{x_{δ^{⊥}n/2}}{n} = \frac{1}{2} − \sqrt{δ^{⊥}/2(1 − δ^{⊥}/2)} .

Theorem 11.20

ρ ≤ H_{2}(\frac{1}{2} − \sqrt{δ^{⊥}(1 − δ^{⊥})}).  (35)
□

Another type of bound can be found if one uses Chebyshev polynomials. This approach is due to Litsyn and Tietäväinen [111] and Honkala, Litsyn and Tietäväinen [80].

Theorem 11.21 Let (C_{n})_{n=1}^{∞} be a sequence of binary linear codes C_{n} of length n, dual distance d′ and covering radius ρ where ρ/n → ϱ and d^{⊥}/n → δ^{⊥} when n → ∞. Then

ϱ ≤ \frac{H(\frac{1}{2} − \sqrt{δ^{⊥}(1 − δ^{⊥})})}{log_{2}(^{\frac{(1−λ+δ^{⊥}+2\sqrt{δ^{⊥}(1−λ)}}{1−λ−δ^{⊥}}})},

where λ = \frac{1}{2} − \sqrt{\frac{1}{2}(\frac{1}{2} − δ^{⊥})}.

For other bounds see [42, 50, 141, 142, 143, 144]

12 Other problems related to coverings

The notion of covering has been generalized in several ways [79].

12.1 Football pool problem

The goal is to find a way of forecasting the outcome (win, lose, tie) of n football matches with a fixed maximal number, ρ, of wrong outcomes in at least one guess, using a minimal number of guesses. Thus one can guarantee winning at least the (ρ + 1)-st prize, no matter what the actual outcomes are. This problem coincides with the problem of constructing minimal coverings in a ternary Hamming space of length n. However, some initial knowledge about possibilities of outcomes can reduce this problem to that of covering some subset of the ternary Hamming space, namely a mixed binary-ternary space. For results see the survey paper by Honkala, Hämäläinen, Litsyn and Östergård [62] and [51, 58, 63, 95, 102, 103, 127, 130, 145, 146, 158, 165].

12.2 Mixed Coverings

For i = 1, 2, …, n, let Q_{i} be an alphabet consisting of q_{i} ≥ 2 symbols, and let V be the Cartesian product V := Q_{1} × Q_{2} × ⋯ × Q_{n}. If t is a nonnegative integer, B_{t}(x) denotes the sphere with radius e and center x: B_{t}(x) = {y ∈ V, d(x, y) ≤ t}. A code C ⊂ V is a perfect mixed t-code if the spheres B_{t}(c), c ∈ C, form a partition of V.

Constructions of mixed codes were studied mostly for the binary/ternary case (see [48, 129, 131]). Lower bounds improving on the sphere covering bound were derived in [56, 57, 58, 59, 100, 101, 110, 125, 161, 162, 163].

12.3 Weighted Coverings

The notion of weighted coverings proved to be very fruitful. Many perfect configurations such as classical perfect codes, uniformly packed codes, L-codes, etc., are particular cases of weighted coverings. (For details and applications, see [29]).

A way of seeing a weighted covering is as a union of weighted spheres (i.e., spheres with different weights attached to their layers) around the codewords such that the accumulated density in every point of the space is at least 1. The case when the weights of the first ρ layers equal to 1 corresponds to the classical case.

Classification of perfect weighted coverings of small diameter was made in [28, 29, 34, 35].

12.3.1 Multiple Coverings

This is the case when the first ρ weights equal 1/m for some integer m. This means that every point of the space is covered by at least m spheres (in terms of football pools, you are sure to win m prizes, each of which is at least the (ρ(C)+1)-st prize). Perfect multiple coverings were studied in [164] in the binary and non-binary cases. It was shown that there exist perfect multiple coverings which are not a union of cosets of a conventional perfect covering. Complete classification of such perfect coverings is still an open problem. Honkala [73] generalized the notion of normality to multiple coverings. Upper and lower bounds were extensively studied in [60], with a table of bounds for n ≤ 16, t ≤ 4, and μ ≤ 4. Results on generalizations to schemes other than Hamming association schemes may be found in [24].

12.3.2 Multiple Coverings of the Farthest-Off Points

This topic corresponds to weighted coverings which cover all the points at least once, and the points that are at distance ρ(C) from the code C at least m times, m > 1 (in terms of football pools, you are sure to win at least the ρ(C)-th prize or at least m times the (ρ(C) + 1)-st prize). Constructions of such codes and tables for n ≤ 16, t ≤ 4, μ ≤ 4 may be found in [61].

13 Acknowledgement

We are grateful to G.Cohen, I.Honkala, A.Lobstein and H.F.Mattson, Jr.

References

[1] E. H. L. Aarts and P. J. M. van Laarhoven, “ Local search in coding theory,” Discrete Mathematics, vol. 106/107, pp. 11–18, 1992.

[2] M. J. Adams, “ Subcodes and covering radius,” IEEE Trans. Inform. Th., vol. IT-32, pp. 700–701, 1986.

[3] N. Alon and J. H. Spencer, The Probabilistic Method, New York, Wiley, 1992.

[4] E. F. Assmus, Jr., and H. F. Mattson, Jr., “ Some 3-error correcting BCH codes have covering radius 5,” IEEE Trans. Inform. Th., vol. IT-22, pp. 348–349, 1976.

[5] E. F. Assmus, Jr., and V. S. Pless, “ On the covering radius of extremal self-dual codes,” IEEE Trans. Inform. Th., vol. IT-29, pp. 359–363, 1983.

[6] I. Bárány, ”A short proof of Kneser’s conjecture,” J. Combin. Theory, Ser. A 25 (1978), 325-326.

[7] M. C. Bhandari and M. S. Garg, “ A note on the covering radius of optimum codes,” Discrete Applied Mathematics, vol. 33, pp. 3–9, 1991.

[8] V. M. Blinovskii, “ Lower asymptotic bound on the number of linear code words in a sphere of given radius in F_{q}^{n},” Problemy Peredachi Informatsii, vol. 23, No. 2, pp. 50–53, 1987. Translated in : Problems of Inform. Transm., vol. 23, No. 2, pp. 130–132.

[9] V. M. Blinovskii, “ Asymptotically exact uniform bounds for spectra of cosets of linear codes,” Problemy Peredachi Informatsii, vol. 26, No. 1, pp. 99–103, 1990. Translated in : Problems of Inform. Transm., vol. 26, No. 1, pp. 83–86.

[10] V. M. Blinovskii, “ Covering the Hamming space with sets translated by linear code vectors,” Problemy Peredachi Informatsii, vol. 26, No. 3, pp. 21–26, 1990. Translated in : Problems of Inform. Transm., vol. 26, No. 3, pp. 196–201.

[11] A. Blokhuis and C. W. H. Lam, “ More coverings by rook domains,” J. Combinatorial Th., Ser. A, vol. 36, pp. 240–244, 1984.

[12] R. A. Brualdi, N. Cai, and V. S. Pless, “ Orphan structure of the firstorder Reed-Muller codes,” Discrete Mathematics, vol. 102, pp. 239–247, 1992.

[13] R. A. Brualdi and V. S. Pless, “ Orphans of the first order Reed-Muller codes,” IEEE Trans. Inform. Th., vol. IT-36, pp. 399–401, 1990.

[14] R. A. Brualdi and V. S. Pless, “ On the covering radius of a code and its subcodes,” Discrete Mathematics, vol. 83, pp. 189–199, 1990.

[15] R. A. Brualdi and V. S. Pless, “ On the length of codes with a given covering radius, : Coding Theory and Design Theory. Part I, “ Coding Theory, Ray-Chaudhuri, Ed., pp. 9–15, New York, “ Springer-Verlag, 1990.

[16] R. A. Brualdi and V. S. Pless, “Subcodes of Hamming codes,” Cong. Num., vol. 70, pp.153-158, 1990.

[17] R. A. Brualdi, V. S. Pless, and R. M. Wilson, “ Short codes with a given covering radius,” IEEE Trans. Inform. Th., vol. IT-35, pp. 99–109, 1989.

[18] P. B. Busschbach, M. G. L. Gerretzen, and H. C. A. van Tilborg, “ On the covering radius of binary linear codes meeting the Griesmer bound,” IEEE Trans. Inform. Th., vol. IT-31, pp. 465–468, 1985.

[19] A. R. Calderbank, “ Covering radius and the chromatic number of Kneser graphs,” J. Combinatorial Th., Ser. A, vol. 54, pp. 129–131, 1990.

[20] A. R. Calderbank, “ Covering bounds for codes,” J. Combinatorial Th., Ser. A, vol. 60, pp. 117–122, 1992.

[21] A. R. Calderbank and N. J. A. Sloane, “ Inequalities for covering codes,” IEEE Trans. Inform. Th., vol. IT-34, pp. 1276–1280, 1988.

[22] W. A. Carnielli, “ On covering and coloring problems for rook domains,” Discrete Mathematics, vol. 57, pp. 9–16, 1985.

[23] W. Chen and I. S. Honkala, “ Lower bounds for q-ary covering codes,” IEEE Trans. Inform. Th., vol. IT-36, pp. 664–671, 1990.

[24] R. F. Clayton, “ Perfect multiple coverings in metric schemes,” : Coding Theory and Design Theory. Part I: Coding Theory, Ray-Chaudhuri, Ed., pp. 51–64, New York, Springer-Verlag, 1990.

[25] G. D. Cohen, “ A nonconstructive upper bound on covering radius,” IEEE Trans. Inform. Th., vol. IT-29, pp. 352–353, 1983.

[26] G. D. Cohen and P. Frankl, “ On cliques and partitions in Hamming spaces,” Annals of Discrete Mathematics, vol. 17, pp. 211–217, 1983.

[27] G. D. Cohen and P. Frankl, “ Good coverings of Hamming spaces with spheres,” Discrete Mathematics, vol. 56, pp. 125–131, 1985.

[28] G. D. Cohen, I. S. Honkala, and S. Litsyn, “ On weighted coverings and packings with diameter one,” CISM Courses and Lectures, No. 339, pp. 43–49, Springer-Verlag, 1993.

[29] G. D. Cohen, I. S. Honkala, S. Litsyn, and H. F. Mattson, Jr., “ Weighted coverings and packings,” IEEE Trans. Inform. Th., vol. IT-41, pp. 1856– 1867, 1995.

[30] G. D. Cohen, I. S. Honkala, S. Litsyn, and A.Lobstein, Covering Codes, Elsevier, 1997.

[31] G. D. Cohen, M. G. Karpovsky, H. F. Mattson, Jr., and J. R. Schatz, “ Covering radius—survey and recent results,” IEEE Trans. Inform. Th., vol. IT-31, pp. 328–343, 1985.

[32] G. D. Cohen and S. Litsyn, “ On the covering radius of Reed-Muller codes, Discrete Mathematics, vol. 106/107, pp. 147–155, 1992.

[33] G. D. Cohen, S. Litsyn, A. C. Lobstein, and H. F. Mattson, Jr., “ Covering radius 1985-1994,” Applicable Algebra in Engineering, Communication and Computing, special issue, to appear.

[34] G. D. Cohen, S. Litsyn, and H. F. Mattson, Jr., “ On perfect weighted coverings with small radius,” Lecture Notes in Computer Science, No. 573, pp. 32–41, Springer-Verlag, 1992.

[35] G. D. Cohen, S. Litsyn, and H. F. Mattson, Jr., “ Binary perfect weighted coverings, I, The linear case,” : Sequences II, Capocelli, DeSantis, and Vaccaro, Eds., pp. 36–51, Springer-Verlag, 1993.

[36] G. D. Cohen, A. C. Lobstein, and N. J. A. Sloane, “ Further results on the covering radius of codes,” IEEE Trans. Inform. Th., vol. IT-32, pp. 680–694, 1986.

[37] G. D. Cohen, A. C. Lobstein, and N. J. A. Sloane, “ On a conjecture concerning coverings of Hamming space,” Lecture Notes in Computer Science, No. 228, pp. 79–89, Springer-Verlag, 1986.

[38] S. D. Cohen, “ The length of primitive BCH codes with minimal covering radius,” Preprint.

[39] A. A. Davydov, “ Construction of linear covering codes,” Problemy Peredachi Informatsii, vol. 26, No. 4, pp. 38–55, 1990. Translated in : Problems of Inform. Transm., vol. 26, No. 4, pp. 317–331.

[40] A. A. Davydov, “ Constructions and families of covering codes and saturated sets of points in projective geometry,” IEEE Trans. Inform. Th., vol. IT-41, pp. 2071–2080, 1995.

[41] A. A. Davydov and A. Y. Drozhzhina-Labinskaya, “ Constructions, families, and tables of binary linear covering codes,” IEEE Trans. Inform. Th., vol. IT-40, pp. 1270–1279, 1994.

[42] C. Delorme and P. Solé, “ Diameter, covering index, covering radius and eigenvalues,” European J. Combinatorics, vol. 12, pp. 95–108, 1991.

[43] P. Delsarte and P. Piret, “ Do most binary linear codes achieve the Goblick bound on the covering radius?,” IEEE Trans. Inform. Th., vol. IT-32, pp. 826–828, 1986.

[44] S. M. Dodunekov, “ Griesmer codes with maximum covering radius,” Problemy Peredachi Informatsii, vol. 23, No. 4, pp. 110–113, 1987. Translated in : Problems of Inform. Transm., vol. 23, No. 4, pp. 344–346.

[45] R. Dougherty and H. Janwa, “ Covering radius computations for binary cyclic codes,” Mathematics of Computation, vol. 57, pp. 415–434, 1991.

[46] D. E. Downie and N. J. A. Sloane, “ The covering radius of cyclic codes of length up to 31,” IEEE Trans. Inform. Th., vol. IT-31, pp. 446–447, 1985.

[47] A. A. El Gamal, L. A. Hamachandra, I. Shperling, and V. K. Wei, “ Using simulated annealing to design good codes,” IEEE Trans. Inform. Th., vol. IT-33, pp. 116–123, 1987.

[48] T. Etzion and G. Greenberg, “ Constructions of perfect mixed codes and other covering codes,” IEEE Trans. Inform. Th., vol. IT-39, pp. 209–214, 1993.

[49] T. Etzion, G. Greenberg, and I. S. Honkala, “ Normal and abnormal codes,” IEEE Trans. Inform. Th., vol. IT-39, pp. 1453–1456, 1993.

[50] G. Fazekas and V. I. Levenshtein, “ On upper bounds for code distance and covering radius of designs in polynomial metric spaces,” J. Combinatorial Th., Ser. A, vol. 70, pp. 267–288, 1995.

[51] H. Fernandes and E. Rechtschaffen, “ The football pool problem for 7 and 8 matches,” J. Combinatorial Th., Ser. A, vol. 35, pp. 109–114, 1983.

[52] E. M. Gabidulin, A. A. Davydov, and L. M. Tombak, “ Linear codes with covering radius 2 and other new covering codes,” IEEE Trans. Inform. Th., vol. IT-37, pp. 219–224, 1991.

[53] T. J. Goblick, Jr., “ Coding for a discrete information source with a distortion measure, Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, United States, 1962.

[54] D. Gorenstein, W. W. Peterson, and N. Zierler, “ Two-error correcting Bose-Chaudhury codes are quasi-perfect,” Information and Control, vol. 3, pp. 291–294, 1960.

[55] R. L. Graham and N. J. A. Sloane, “ On the covering radius of codes,” IEEE Trans. Inform. Th., vol. IT-31, pp. 385–401, 1985.

[56] L. Habsieger, “ Lower bounds for q-ary coverings by spheres of radius 1,” J. Combinatorial Th., Ser. A, vol. 67, pp. 199–222, 1994.

[57] L. Habsieger, “ Binary codes with covering radius one, some new lower bounds,” Discrete Mathematics, to appear.

[58] L. Habsieger, “ A new lower bound for the football pool problem for 7 matches,” J. Th. des Nombres de Bordeaux, to appear.

[59] L. Habsieger, “ Some new lower bounds for ternary covering codes,” Electronic J. Combinatorics, http:// ejc.math.gatech.edu:8080/ Journal/ Volume 3/ festschrift.html, 1996.

[60] H. O. Hämäläinen, I. S. Honkala, M. K. Kaikkonen, and S. Litsyn, “ Bounds for binary multiple covering codes,” Designs, Codes and Cryptography, vol. 3, pp. 251–275, 1993.

[61] H. O. Hämäläinen, I. S. Honkala, S. Litsyn, and P. R. J. Östergård, “ Bounds for binary codes that are multiple coverings of the farthest-off points,” SIAM J. Discrete Mathematics, vol. 8, pp. 196–207, 1995.

[62] H. O. Hämäläinen, I. S. Honkala, S. Litsyn, and P. R. J. Östergård, “ Football pools - a game for mathematicians,” American Mathematical Monthly, vol. 102, pp. 579–588, 1995.

[63] H. O. Hämäläinen and S. Rankinen, “ Upper bounds for football pool problems and mixed covering codes,” J. Combinatorial Th., Ser. A, vol. 56, pp. 84–95, 1991.

[64] T. Helleseth, “ All binary 3-error-correcting BCH codes of length 2^{m} − 1 have covering radius 5,” IEEE Trans. Inform. Th., vol. IT-24, pp. 257– 258, 1978.

[65] T. Helleseth, “ On the covering radius of cyclic linear codes and arithmetic codes,” Discrete Applied Mathematics, vol. 11, pp. 157–173, 1985.

[66] T. Helleseth, T. Kløve, and J. Mykkeltveit, “ On the covering radius of binary codes,” IEEE Trans. Inform. Th., vol. IT-24, pp. 627–628, 1978.

[67] T. Helleseth and H. F. Mattson, Jr., “ On the cosets of the simplex code, Discrete Mathematics, vol. 56, pp. 169–189, 1985.

[68] I. S. Honkala, “ Lower bounds for binary covering codes,” IEEE Trans. Inform. Th., vol. IT-34, pp. 326–329, 1988.

[69] I. S. Honkala, “ Modified bounds for covering codes,” IEEE Trans. Inform. Th., vol. IT-37, pp. 351–365, 1991.

[70] I. S. Honkala, “ On (k, t)-subnormal covering codes,” IEEE Trans. Inform. Th., vol. IT-37, pp. 1203–1206, 1991.

[71] I. S. Honkala, “ All binary codes with covering radius one are subnormal,” Discrete Mathematics, vol. 94, pp. 229–232, 1991.

[72] I. S. Honkala, “ A lower bound on binary codes with covering radius one,” Lecture Notes in Computer Science, No. 781, pp. 34–37, Springer-Verlag, 1994.

[73] I. S. Honkala, “ On the normality of multiple covering codes,” Discrete Mathematics, vol. 125, pp. 229–239, 1994.

[74] I. S. Honkala, “ On (q, 1)-subnormal q-ary covering codes,” Discrete Applied Mathematics, vol. 52, pp. 213–221, 1994.

[75] I. S. Honkala, “ A new lower bound on codes with covering radius one,” Proc. Internat. Symp. on Information Theory and its Applications, vol. 1, pp. 39–41, Sydney, 1994.

[76] I. S. Honkala and H. O. Hämäläinen, “ A new construction for covering codes,” IEEE Trans. Inform. Th., vol. IT-34, pp. 1343–1344, 1988.

[77] I. S. Honkala and H. O. Hämäläinen, “ Bounds for abnormal binary codes with covering radius one,” IEEE Trans. Inform. Th., vol. IT-37, pp. 372– 375, 1991.

[78] I. S. Honkala, Y. Kaipainen, and A. Tietäväinen, “ Long binary narrowsense BCH codes are normal,” Applicable Algebra in Engineering, Communication and Computing, to appear.

[79] I. S. Honkala and S. Litsyn, “ Generalizations of the covering radius problem in coding theory,” Bull. Institute of Combinatorics and its Applications, vol.17, pp.39–46, 1996.

[80] I. S. Honkala, S. Litsyn, and A. Tietäväinen, “ On algebraic methods in covering radius problems,” Lecture Notes in Computer Science, No. 948, pp. 21–32, Springer-Verlag, 1995.

[81] J. A. van der Horst and T. Berger, “ Complete decoding of triple-error-correcting binary BCH codes,” IEEE Trans. Inform. Th., vol. IT-22, pp. 138–147, 1976.

[82] X. D. Hou, “ Covering radius and error correcting codes,” Ph. D. Thesis, University of Illinois, Chicago, United States, 77 p., 1990.

[83] X. D. Hou, “ Some results on the norm of codes,” IEEE Trans. Inform. Th., vol. IT-36, pp. 683–685, 1990.

[84] X. D. Hou, “ New lower bounds for covering codes,” IEEE Trans. Inform. Th., vol. IT-36, pp. 895–899, 1990.

[85] X. D. Hou, “ An improved sphere covering bound for the codes with n = 3R + 2,” IEEE Trans. Inform. Th., vol. IT-36, pp. 1476–1478, 1990.

[86] X. D. Hou, “ Binary linear quasi-perfect codes are normal,” IEEE Trans. Inform. Th., vol. IT-37, pp. 378–379, 1991.

[87] X. D. Hou, “ On the covering radius of subcodes of a code,” IEEE Trans. Inform. Th., vol. IT-37, pp. 1706–1707, 1991.

[88] X. D. Hou, “ Some results on the covering radii of Reed-Muller codes,” IEEE Trans. Inform. Th., vol. IT-39, pp. 366–378, 1993.

[89] X. D. Hou, “ Further results on the covering radii of the Reed-Muller codes, Designs, Codes and Cryptography, vol. 3, pp. 167–177, 1993.

[90] X. D. Hou, “ The Reed-Muller code R(1, 7) is normal,” Designs, Codes and Cryptography, to appear.

[91] H. Janwa, “ Some new upper bounds on the covering radius of binary linear codes,” IEEE Trans. Inform. Th., vol. IT-35, pp. 110–122, 1989.

[92] H. Janwa, “ Some optimal codes from algebraic geometry and their covering radii,” European J. Combinatorics, vol. 11, pp. 249–266, 1990.

[93] H. Janwa, “ On the parameters of algebraic geometric codes,” Lecture Notes in Computer Science, No. 539, pp. 19–28, Springer-Verlag, 1991.

[94] G. A. Kabatyanskii and V. I. Panchenko, “ Unit sphere packings and coverings of the Hamming space,” Problemy Peredachi Informatsii, vol. 24, No. 4, pp. 3–16, 1988. Translated in : Problems of Inform. Transm., vol. 24, No. 4, pp. 261–272.

[95] H. J. L. Kamps and J. H. van Lint, “ The football pool problem for 5 matches, J. Combinatorial Th., Ser. A, vol. 3, pp. 315–325, 1967.

[96] M. G. Karpovsky, “ Weight distribution of translates, covering radius and perfect codes correcting errors of the given multiplicities,” IEEE Trans. Inform. Th., vol. IT-27, pp. 462–472, 1981.

[97] G. L. Katsman, “ Bounds on covering radius of dual product codes,” Lecture Notes in Computer Science, No. 573, pp. 52–57, Springer-Verlag, 1992.

[98] K. E. Kilby and N. J. A. Sloane, “ On the covering radius problem for codes: I Bounds on normalized covering radius, II Codes of low dimension; normal and abnormal codes,” SIAM J. Algebraic and Discrete Methods, vol. 8, pp. 604–627, 1987.

[99] D. J. Kleitman, “ On a combinatorial conjecture of Erdös,” J. Combinatorial Th., vol. 1, pp. 209–214, 1966.

[100] E. Kolev, “ Codes over GF (3) of length 5, 27 codewords and covering radius 1,” J. Combinatorial Designs, vol. 1, pp. 265–275, 1993.

[101] E. Kolev and I. Landgev, “ On some mixed covering codes of small length,” Lecture Notes in Computer Science, No. 781, pp. 38–50, Springer-Verlag, 1994.

[102] K. U. Koschnick, “ A new upper bound for the football pool problem for nine matches,” J. Combinatorial Th., Ser. A, vol. 62, pp. 162–167, 1993.

[103] P. J. M. van Laarhoven, E. H. L. Aarts, J. H. van Lint, and L. T. Wille, “ New upper bounds for the football pool problem for 6, 7 and 8 matches,” J. Combinatorial Th., Ser. A, vol. 52, pp. 304–312, 1989.

[104] F. Levy-dit-Vehel and S. Litsyn, “ On the covering radius of long Goppa codes,” Lecture Notes in Computer Science, No. 948, pp. 341–346, Springer-Verlag, 1995.

[105] F. Levy-dit-Vehel and S. Litsyn, “ More on the covering radius of BCH codes, IEEE Trans. Inform. Th., vol. IT-42, pp. 1023–1028, 1996.

[106] F. Levy-dit-Vehel and S. Litsyn, “ Parameters of Goppa codes revisited, ” IEEE Trans. Inform. Th., to appear.

[107] D. Li and W. Chen, “ New lower bounds for binary covering codes,” IEEE Trans. Inform. Th., vol. IT-40, pp. 1122–1129, 1994.

[108] J. H. van Lint, “ Recent results on covering problems,” Lecture Notes in Computer Science, No. 357, pp. 7–21, Springer-Verlag, 1989.

[109] J. H. van Lint, Jr., “ Covering radius problems,” Master’s Thesis, Eindhoven University of Technology, the Netherlands, 41 p., 1988.

[110] J. H. van Lint, Jr., and G. J. M. van Wee, “ Generalized bounds on binary/ternary mixed packing and covering codes,” J. Combinatorial Th., Ser. A, vol. 57, pp. 130–143, 1991.

[111] S. Litsyn and A. Tietäväinen, “ Upper bounds on the covering radius of a code with a given dual distance,” European J. Combinatorics, vol. 17, pp. 265–270, 1996.

[112] D.-h. Liu, personal communication.

[113] A. C. Lobstein and V. S. Pless, “ The length function, a revised table,” Lecture Notes in Computer Science, No. 781, pp. 51–55, Springer-Verlag, 1994.

[114] A. C. Lobstein and G. J. M. van Wee, “ On normal and subnormal q-ary codes,” IEEE Trans. Inform. Th., vol. IT-35, pp. 1291–1295, 1989, and vol. IT-36, p. 1498, 1990.

[115] L. Lovász, ”Kneser’s conjecture, chromatic number and homotopy,” J. Combin. Theory, Ser. A 25 (1978), 319-324.

[116] F. J. MacWilliams and N. J. A. Sloane, “ The Theory of Error-Correcting Codes, Amsterdam, “ North-Holland, 1977.

[117] H. F. Mattson, Jr., “ An upper bound on covering radius,” Annals of Discrete Mathematics, vol. 17, pp. 453–458, 1983.

[118] H. F. Mattson, Jr., “ Another upper bound on covering radius,” IEEE Trans. Inform. Th., vol. IT-29, pp. 356–359, 1983.

[119] H. F. Mattson, Jr., “ An improved upper bound on covering radius,” Lecture Notes in Computer Science, No. 228, pp. 90–106, Springer-Verlag, 1986.

[120] H. F. Mattson, Jr., and J. R. Schatz, “ A brief survey of covering radius,” Annals of Discrete Mathematics, vol. 18, pp. 617–624, 1983.

[121] A. McLoughlin, “ The covering radius of the (m − 3)rd order Reed-Muller codes and a lower bound on the covering radius of the (m − 4)th order Reed-Muller codes,” SIAM J. Applied Mathematics, vol. 37, pp. 419–422, 1979.

[122] M. Mollard, “ Les invariants du n-cube, Thèse de 3ème cycle, Université de Grenoble, France, 113 p., 1981.

[123] C. J. Moreno and O. Moreno, “ Exponential sums and Goppa codes II,” IEEE Trans. Inform. Th., vol. IT-38, pp. 1222–1229, 1992.

[124] J. Mykkeltveit, “ The covering radius of the (128,8) Reed-Muller code is 56, IEEE Trans. Inform. Th., vol. IT-26, pp. 359–362, 1980.

[125] M. Numata, “ On the minimal covering of 3-dimensional Hamming scheme,” Ann. Rep. Fac. Educ., Iwate University, vol. 52, No. 1, pp. 73–84, 1992.

[126] P. R. J. Östergård, “ A new binary code of length 10 and covering radius 1,” IEEE Trans. Inform. Th., vol. IT-37, pp. 179–180, 1991.

[127] P. R. J. Östergård, “ Upper bounds for q-ary covering codes,” IEEE Trans. Inform. Th., vol. IT-37, pp. 660–664, 1991, and vol. IT-37, p. 1738, 1991.

[128] P. R. J. Östergård, “ Further results on (k, t)-subnormal covering codes,” IEEE Trans. Inform. Th., vol. IT-38, pp. 206–210, 1992.

[129] P. R. J. Östergård, “ Construction methods for mixed covering codes, : Analysis, Algebra, and Computers in Mathematical Research, Gyllenberg and Persson, Eds., pp. 387–408, New York, “ Dekker, 1994.

[130] P. R. J. Östergård, “ New upper bounds for the football pool problem for 11 and 12 matches,” J. Combinatorial Th., Ser. A, vol. 67, pp. 161–168, 1994.

[131] P. R. J. Östergård and H. O. Hämäläinen, “ A new table of binary-ternary mixed covering codes,” Designs, Codes and Cryptography, submitted.

[132] J. Pach and J. H. Spencer, “ Explicit codes with low covering radius,” IEEE Trans. Inform. Th., vol. IT-34, pp. 1281–1285, 1988.

[133] V. I. Panchenko, “ Packings and coverings over an arbitrary alphabet,” Problemy Peredachi Informatsii, vol. 24, No. 4, pp. 93–96, 1988. Translated in : Problems of Inform. Transm., vol. 24, No. 4, pp. 331–333.

[134] N. J. Patterson and D. H. Wiedemann, “ The covering radius of the (2^{15},16) Reed-Muller code is at least 16276,” IEEE Trans. Inform. Th., vol. IT-29, pp. 354–356, 1983.

[135] N. J. Patterson and D. H. Wiedemann, “ Correction to “The covering radius of the (2^{15},16) Reed-Muller code is at least 16276”,” IEEE Trans. Inform. Th., vol. IT-36, p. 443, 1990.

[136] J. R. Schatz, “ The second order Reed-Muller code of length 64 has covering radius 18,” IEEE Trans. Inform. Th., vol. IT-27, pp. 529–530, 1981.

[137] J. Simonis, “ Covering radius: improving on the sphere-covering bound,” Lecture Notes in Computer Science, No. 357, pp. 377–385, Springer-Verlag, 1989.

[138] J. Simonis, ”Subcodes and covering radius: a generalization of Adam’s result,” preprint.

[139] A. N. Skorobogatov, “ The parameters of subcodes of algebraic-geometric codes over prime subfields,” Discrete Applied Mathematics, vol. 33, pp. 205–214, 1991.

[140] N. J. A. Sloane, “ A new approach to the covering radius of codes,” J. Combinatorial Th., Ser. A, vol. 42, pp. 61–86, 1986.

[141] P. Solé, “ Asymptotic bounds on the covering radius of binary codes,” IEEE Trans. Inform. Th., vol. IT-36, pp. 1470–1472, 1990.

[142] P. Solé, “ Packing radius, covering radius, and dual distance,” IEEE Trans. Inform. Th., vol. IT-41, pp. 268–272, 1995.

[143] P. Solé and K. G. Mehrotra, “ Generalization of the Norse bounds to codes of higher strength,” IEEE Trans. Inform. Th., vol. IT-37, pp. 190–192, 1991.

[144] P. Solé and P. Stokes, “ Covering radius, codimension and dual-distance width,” IEEE Trans. Inform. Th., vol. IT-39, pp. 1195–1203, 1993.

[145] R. G. Stanton, “ Covering theorems in groups (or, how to win at football pools),” : Recent Progress in Combinatorics, Tutte, Ed., pp. 21–36, New York, Academic Press, 1969.

[146] R. G. Stanton, J. D. Horton, and J. G. Kalbfleisch, “ Covering theorems for vectors with special reference to the case of four and five components,” J. London Math. Soc. (2), vol. 1, pp. 493–499, 1969.

[147] R. G. Stanton and J. G. Kalbfleisch, “ Covering problems for dichotomized matchings,” Aequationes Math., vol. 1, pp. 94–103, 1968.

[148] R. G. Stanton and J. G. Kalbfleisch, “ Intersection inequalities for the covering problem,” SIAM J. Applied Mathematics, vol. 17, pp. 1311–1316, 1969.

[149] R. Struik, “ An improvement of the van Wee bound for binary linear covering codes,” IEEE Trans. Inform. Th., vol. IT-40, pp. 1280–1284, 1994.

[150] R. Struik, “ On the structure of linear codes with covering radius two and three,” IEEE Trans. Inform. Th., vol. IT-40, pp. 1406–1416, 1994.

[151] R. Struik, “ Covering codes,” Ph. D. Thesis, Eindhoven University of Technology, the Netherlands, 106 p., 1994.

[152] A. Tietäväinen, “ On the covering radius of long binary BCH codes, Discrete Applied Mathematics, vol. 16, pp. 75–77, 1987.

[153] A. Tietäväinen, “ An asymptotic bound on the covering radii of binary BCH codes,” IEEE Trans. Inform. Th., vol. IT-36, pp. 211–213, 1990.

[154] A. Tietäväinen, “ An upper bound on the covering radius as a function of the dual distance,” IEEE Trans. Inform. Th., vol. IT-36, pp. 1472–1474, 1990.

[155] A. Tietäväinen, “ Covering radius and dual distance,” Designs, Codes and Cryptography, vol. 1, pp. 31–46, 1991.

[156] E. D. Velikova, “ Covering radius of some cyclic codes,” Proc. Internat. Workshop on Algebraic and Combinatorial Coding Theory, pp. 165–169, Varna, 1988.

[157] S. G. Vläduts and A. N. Skorobogatov, “ Covering radius for long BCH codes,” Problemy Peredachi Informatsii, vol. 25, No. 1, pp. 38–45, 1989. Translated in : Problems of Inform. Transm., vol. 25, No. 1, pp. 28–34.

[158] E. W. Weber, “ On the football pool problem for 6 matches, “ a new upper bound, J. Combinatorial Th., Ser. A, vol. 35, pp. 106–108, 1983.

[159] G. J. M. van Wee, “ Improved sphere bounds on the covering radius of codes,” IEEE Trans. Inform. Th., vol. IT-34, pp. 237–245, 1988.

[160] G. J. M. van Wee, “ More binary covering codes are normal,” IEEE Trans. Inform. Th., vol. IT-36, pp. 1466–1470, 1990.

[161] G. J. M. van Wee, “ On the non-existence of certain perfect mixed codes,” Discrete Mathematics, vol. 87, pp. 323–326, 1991.

[162] G. J. M. van Wee, “ Bounds on packings and coverings by spheres in q-ary and mixed Hamming spaces,” J. Combinatorial Th., Ser. A, vol. 57, pp. 117–129, 1991.

[163] G. J. M. van Wee, “ Some new lower bounds for binary and ternary covering codes,” IEEE Trans. Inform. Th., vol. IT-39, pp. 1422–1424, 1993.

[164] G. J. M. van Wee, G. D. Cohen, and S. Litsyn, “ A note on perfect multiple coverings of the Hamming space,” IEEE Trans. Inform. Th., vol. IT-37, pp. 678–682, 1991.

[165] L. T. Wille, “ The football pool problem for 6 matches, “ a new upper bound obtained by simulated annealing,” J. Combinatorial Th., Ser. A, vol. 45, pp. 171–177, 1987.

[166] L. T. Wille, “ Improved binary code coverings by simulated annealing,” Congressus Numerantium, vol. 73, pp. 53–58, 1990.

[167] G. Zémor and G. D. Cohen, “ Error-correcting WOM-codes,” IEEE Trans. Inform. Th., vol. IT-37, pp. 730–734, 1991.

[168] Z. Zhang, “ Linear inequalities for covering codes: Part I—pair covering inequalities,” IEEE Trans. Inform. Th., vol. IT-37, pp. 573–582, 1991.

[169] Z. Zhang and C. Lo, “ Linear inequalities for covering codes: Part II— triple covering inequalities,” IEEE Trans. Inform. Th., vol. IT-38, pp. 1648–1662, 1992.

[170] Z. Zhang and C. Lo, “ Lower bounds on t[n, k] from linear inequalities,” IEEE Trans. Inform. Th., vol. IT-38, pp. 194–197, 1992.