Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 2, 469-478.

On Codes with Given Minimum Distance and Covering Radius

Jörn Quistorff

Speckenreye 48, D-22119 Hamburg, Germany

Abstract. Codes with minimum distance at least d and covering radius at most d − 1 are considered. The minimal cardinality of such codes is investigated. Herewith, their connection to covering problems is applied and a new construction theorem is given. Additionally, a new lower bound for the covering problem is proved. A necessary condition on an existence problem is presented by using a multiple covering of the farthest-off points.

1. Introduction

Coding theory, seen from the combinatorial point of view, considers often (block-)codes of finite order and length provided with the Hamming metric, neither restricted to the binary nor to the linear case.

Prior reseach dealt usually with at most one of the following two problems.

On the one hand, packing problems were investigated in order to find (local) maximal, which means not extendable, codes with given minimum distance. Herewith, it is the aim to determine the maximal, more seldom the minimal, cardinality of such a code. Cf. MacWilliams/Sloane [14], Heise/Quattrocchi [9] and Quistorff [15].

On the other hand, covering problems were examined in order to find codes with given covering radius. Herewith, it is the aim to determine the minimal cardinality of such a covering code. Cf. Cohen et al. [2], [3], [4], [5] and van Lint [13].

Both problems were usually studied isolated. Cohen et al. [2] however remarked that in packing problems, also the covering radius plays an important role: A code with a minimum distance at least d is not extendable iff its covering radius is at most d − 1.

The present work is mainly devoted to codes with given minimum distance and covering radius. It concentrates on the minimal cardinality of a code with minimum distance at least

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

d and covering radius at most d − 1, especially in case of d = 2. Additionally, a new lower bound for the covering problem is proved.

In Section 2, the foundations of packing and covering problems are given.

Known results on the minimal cardinality v(q, n, d) of a code of order q and length n with minimum distance at least d and covering radius at most d − 1 are surveyed in Section 3. Some stem from Quistorff [15], where a code with the mentioned properties is called a local cardinal maximum code. Other findings, for example an implicit lower bound, were given in Quistorff [16], partially using the algebraic structure of an n-quasigroup.

The minimal cardinality of a code of order q and length n with covering radius at most t is called K_{q}(n, t). Trivially, K_{q}(n, d − 1) is a lower bound on v(q, n, d). Hence, some lower bounds and exact values on K_{q}(n, t), for example the well-known sphere-covering bound, are mentioned in Section 4.

In Section 5, a new lower bound on K_{q}(n, 1) with 2 ≤ n − 1 < q ≤ 2(n − 1) is proved using ideas of Kalbfleisch/Weiland [12].

Section 6 presents a new construction of codes with minimum distance at least 2 and covering radius 1.

An open problem with relative small parameters is the determination of v(4, 4, 2). Results of Sections 4 and 6 yield 24 and 32 as lower and upper bound, respectively.

In the final Section 7, a necessary condition on the existence of a code of a given cardinality u with minimum distance at least 2 and covering radius 1 is presented using the so-called multiple covering of the farthest-off points, cf. Hämäläinen et al. [8]. An example shows that this condition is fulfilled in case of q = n = 4 and u = 24.

2. Foundations

Let q, n ∈ N = {1, 2, …}. A set C ⊆ K^{n} with |K| = q is called a code of order q and length n (or q-ary code of length n). An element w = (w_{1}, …, w_{n}) of C is called codeword. The mapping

d : K^{n} × K^{n} → N_{0}, (w, w′) ↦ |{x ∈ Z_{n}|w_{x} ≠ w′_{x}}|

with N_{0} = N ∪ {0} and Z_{n} := {x ∈ N|x ≤ n} is called Hamming distance. It induces a metric on the space K^{n}, called the Hamming metric. If |C| ≥ 2 and hence q ≥ 2, the minimum distance of C is defined as

d(C) := min{d(w, w′) ∈ N|w, w′ ∈ C with w ≠ w′}.

If |C| ≥ 1, the covering radius of C is introduced as

t(C) := max{min{d(v, w) ∈ N_{0}|w ∈ C}|v ∈ K^{n}}.

For e ∈ N_{0} and v ∈ K^{n}, the set

B(v, e) := {v′ ∈ K^{n}|d(v, v′) ≤ e}

is called sphere around v with radius e (and with respect to the Hamming metric). Its cardinality is |B(v, e)| = ∑_{i=0}^{e} \binom{n}{i}(q − 1)^{i}.

The statement B(w, e) ∩ B(w′, e) = ∅ holds true for all w, w′ ∈ C with w ≠ w′ iff 2e + 1 ≤ d(C) is valid. Furthermore, ⋃_{w∈C} B(w, t) = K^{n} (or, equivalently, C ∩ B(v, t) ≠ ∅ for all v ∈ K^{n}) holds true iff t(C) ≤ t.

Because of these relations, questions referring to the minimum distance of codes are sphere-packing problems and questions referring to the covering radius are sphere-covering problems.

The minimum distance and the covering radius of any code with |C| ≥ 2 are related by

d(C) ≤ 2t(C) + 1,  (1)

cf. Graham/Sloane [6]. If the minimum distance of a code C is at least 2, bound (1) shows that in this case, t(C) ≤ 1 is equivalent to t(C) = 1.

For e ∈ N_{0}, a code C ⊆ K^{n} with e ≤ n is called e-perfect iff the spheres around the codewords with radius e are disjoint and exhaust K^{n}, i.e.

⨄_{w∈C} B(w, e) = K^{n}.

In this case t(C) = e and, if |C| ≥ 2, clearly d(C) = 2e + 1.

Let q, n, d ∈ N with 2 ≤ q and d ≤ n as well as C ⊆ K^{n} with |K| = q. Then C is called a (q, n, d)-cardinal maximum code iff d(C) ≥ d holds true and for every code C′ ⊆ K^{n} with d(C′) ≥ d, the statement |C′| ≤ |C| follows. The maximal cardinality of such a code is denoted by u(q, n, d) (or by A_{q}(n, d)).

Weakening this notion, C is called a local (q, n, d)-cardinal maximum code iff d(C) ≥ d holds true and for every proper including set C′ ⊃ C the statement d(C′) < d follows. The minimal cardinality of such a code is denoted by v(q, n, d).

Let q, n, t ∈ N with t ≤ n as well as C ⊆ K^{n} with |K| = q. Then C is called a t-covering code iff t(C) ≤ t. The minimal cardinality of such a code is denoted by K_{q}(n, t).

Every local (q, n, d)-cardinal maximum code is a (d − 1)-covering code, cf. Cohen et al. [2]. Hence,

v(q, n, d) ≥ K_{q}(n, d − 1).  (2)

If there exists an e-perfect code of order q and length n consisting of more than one codeword,

u(q, n, 2e + 1) = v(q, n, e + 1) = K_{q}(n, e) = \frac{q^{n}}{∑_{i=0}^{e} \binom{n}{i}(q − 1)^{i}}

is valid. The existence of perfect codes is discussed e.g. by Heise/Quattrocchi [9].

3. Known results on v(q, n, d)

Trivially, q ≤ v(q, n, d) ≤ u(q, n, d) holds true as well as v(q, n, 1) = q^{n}.

As an example for an upper bound on u(q, n, d) and hence also on v(q, n, d), the (Joshi-) Singleton bound u(q, n, d) ≤ q^{n−d+1} is mentioned. For further bounds on u(q, n, d), cf. MacWilliams/Sloane [14], Heise/Quattrocchi [9], Quistorff [15] and their references.

In Quistorff [15], the inequalities v(q, n, d) ≠ q^{n−d+1} − 1 ≠ u(q, n, d) were proved. Also, the statement v(q, n, d) = q if qd > n(q − 1) was given. It yields especially v(q, n, n) = q.

Inspired by Stojaković/Ušan’s [19] lower bound v(q, 3, 2) ≥ 2q − 1 if q ≥ 3, Quistorff [16] proved the following implicit lower bound on v(q, n, 2) in the language of (n−1)-quasigroups.

If there exists a code C ⊆ K^{n} of order q and cardinality u with minimum distance at least 2 as well as covering radius 1 and if u = aq^{n−2} + b with a, b ∈ N_{0} as well as b < q^{n−2}, then

(n − 1)(qu − b(a + 1)^{2} − (q^{n−2} − b)a^{2}) ≥ (q^{n−1} − u)q  (3)

holds true. Using this implicit lower bound, the value of v(q, 3, 2) was determined as follows.

v(q, 3, 2) = ⌈\frac{1}{2}q^{2}⌉ .  (4)

(⌈x⌉ denotes the least integer greater than or equal to x.) In the same paper, it was proved that v(kq, n, d) ≤ k^{n−d+1}v(q, n, d) if there exists an (n, n − d + 1)-MDS-code of order k (i.e. a code which fulfils the Singleton bound with equality). Hence, the well-known existence of an (n, n − 1)-MDS-code of every order yields

v(kq, n, 2) ≤ k^{n−1}v(q, n, 2).  (5)

Furthermore, it was shown that

v(kp, p + 1, 2) = k^{p}p^{p−1}  (6)

if p is a prime power and k ∈ N.

4. Lower bounds and exact values on K_{q}(n, t)

Trivially, K_{q}(n, 0) = q^{n} and K_{q}(n, n) = 1 holds true. Cohen et al. [5] mentioned also K_{q}(n, n − 1) = q.

The best known lower bound on K_{q}(n, t) is the sphere-covering bound:

K_{q}(n, t) ≥ \frac{q^{n}}{∑_{i=0}^{t} \binom{n}{i}(q − 1)^{i}} .  (7)

Hence, from (2) and (7) follows

v(q, n, d) ≥ \frac{q^{n}}{∑_{i=0}^{d−1} \binom{n}{i}(q − 1)^{i}} .  (8)

Equality holds in (7) iff there exists a t-perfect code of order q and length n, cf. Section 2. Several improvements of the sphere-covering bound (7) are known, cf. Chen/Honkala [1] and van Wee [21]. The latter proved e.g.

K_{q}(n, 1) ≥ \frac{q^{n}}{n(q − 1)} for even q, n ∈ N.

Trivially, (7) implies

K_{q}(n, t) ≥ ⌈\frac{q^{n}}{∑_{i=0}^{t} \binom{n}{i}(q − 1)^{i}} ⌉ .

Habsieger [7] characterised all cases where this bound for t = 1 and a prime power q is attained: K_{q}(n, 1) = ⌈\frac{q^{n}}{1+n(q−1)}⌉ iff there exists a k ∈ N with n = \frac{q^{k−1}}{q−1} or (q, n) = (2, 2) or (q, n) = (2, 4).

Kalbfleisch/Stanton [11] mentioned

K_{q}(n + 1, 1) ≤ qK_{q}(n, 1),  (9)

they determined

K_{q}(3, 1) = ⌈\frac{q^{2}}{2} ⌉  (10)

and proved K_{4}(4, 1) ≥ 24. Stanton et al. [18] improved the latter to

K_{4}(4, 1) = 24  (11)

by presenting a 1-covering code of order 4, length 4 and cardinality 24. They also proved

K_{kq}(n, 1) ≤ k^{n−1}K_{q}(n, 1)  (12)

if k, q ∈ N with q ≥ 2. Cohen et al. [5] mentioned

K_{kp}(p + 1, 1) = k^{p}p^{p−1}  (13)

if p is a prime power and k ∈ N.

In the binary case, van Wee [20] showed K_{2}(2^{s}, 1) = 2^{2^{s}−s}. Cohen et al. [3] proved e.g. K_{2}(2t + 2, t) ≥ 4 and K_{2}(2t + 3, t) = 7.

Extensive tables of the known results on K_{q}(n, t) were given by Cohen et al. [4], [5]. They include lower bounds on K_{q}(n, 1) with 2 ≤ q ≤ 5 and n ≤ 33, n ≤ 14, n ≤ 10 and n ≤ 9, respectively. Using (2), these bounds force lower bounds on v(q, n, 2) which are, with one exception, as good as or better than the implicit lower bound (3). Only in case of q = n = 5, they mentioned K_{5}(5, 1) ≥ 157 referring to Kalbfleisch/Weiland [12] while (3) forces v(5, 5, 2) ≥ 164. In the following section, K_{5}(5, 1) ≥ 160 will be shown.

It is not known whether there exist parameters with v(q, n, d) > K_{q}(n, d−1). Considering the conformity of (4) and (10), of (5) and (12) and of (6) and (13), one might conjecture equality in (2), at least in case of d = 2. Additionally, a bound which is conform to (9) is given in Section 6.

5. A new lower bound on K_{q}(n, 1)

Kalbfleisch/Weiland [12] proved

K_{q}(n, 1) ≥ ⌈\frac{q^{n−1}}{n − 1}⌉  (14)

if n − 1 < q ≤ 2(n − 1). Rodemich [17] showed independently the validity of this bound if only n ≥ 2.

Some notations are necessary in order to improve Kalbfleisch/Weiland’s [12] argumentation in the scope of 2 ≤ n − 1 < q < 2(n − 1).

Let q, n ∈ N with q ≥ 2 and n ≥ 3 as well as K a set with |K| = q. Let v ∈ K^{n−1} and j ∈ Z_{n}. Put

v#_{(j)}y := (v_{1}, …, v_{j−1}, y, v_{j}, …, v_{n−1}) ∈ K^{n}

for y ∈ K as well as B_{v}^{(j)} := {(v#_{(j)}y) ∈ K^{n}|y ∈ K}. Let w ∈ K^{n−2} and j, k ∈ Z_{n} with j ≠ k. Put

w#_{(j,k)}(y, z) := \{ \begin{matrix}(w_{1}, ..., w_{j−1}, y, w_{j}, ..., w_{k−2}, z, w_{k−1}, ..., w_{n−2}) ∈ K^{n} & if j < k, \\ (w_{1}, ..., w_{k−1}, y, w_{k}, ..., w_{j−2}, z, w_{j−1}, ..., w_{n−2}) ∈ K^{n} & if k < j, \end{matrix}

for y, z ∈ K as well as R_{w}^{(j,k)} := {(w#_{(j,k)}(y, z) ∈ K^{n}|y, z ∈ K}. Clearly, R_{w}^{(j,k)} = R_{w}^{(k,j)}. For C ⊆ K^{n} put f_{C}(R_{w}^{(j,k)}) := (x, t) ∈ (N_{0})^{2} iff |R_{w}^{(j,k)} ∩ C| = x and |{v ∈ K^{n−1}|B_{v}^{(j)} ⊆ R_{w}^{(j,k)} and B_{v}^{(j)} ∩ C ≠ ∅}| = t.

Lemma 1. Let (x, t) := f_{C}(R_{w}^{(j,k)}) and (x, t′) := f_{C}(R_{w}^{(k,j)}).

(i) t ≤ x ≤ qt. (ii) If t = 0 then x = t′ = 0. (iii) If t ≥ 1 then x, t′ ≥ 1. (iv) If t = 1 then x = t′.

(v) If t < x then t′ ≥ 2.

Furthermore, let h_{C}(j, k, x, t) := |{w ∈ K^{n−2}|f_{C}(R_{w}^{(j,k)}) = (x, t)}| for j ≠ k and g_{C}(j, x, t) := ∑_{k∈Z_{n}\\{j\}} h_{C}(j, k, x, t) as well as s(x, t) := (x − \frac{q}{n−1})(t − 1). Using these notations, one gets

∑_{x,t} h_{C}(j, k, x, t) = |K^{n−2}| = q^{n−2}

and hence

∑_{x,t} g_{C}(j, x, t) = (n − 1)q^{n−2}  (15)

as well as

∑_{x,t} h_{C}(j, k, x, t)x = ∑_{x} x ∑_{t} h_{C}(j, k, x, t) = |C|

and hence

∑_{x,t} g_{C}(j, x, t)x = (n − 1)|C|.  (16)

Kalbfleisch/Weiland [12] proved

∑_{x,t} g_{C}(j, x, t)s(x, t) ≤ (q − 1)((n − 1)|C| − q^{n−1}).  (17)

if C is a 1-covering code. In case of q ≤ 2(n−1), each product g_{C}(j, x, t)s(x, t) is nonnegative by Lemma 1 and thus ∑_{x,t} g_{C}(j, x, t)s(x, t) ≥ 0. This proves (14).

In the following, the announced new lower bound is presented.

Theorem 1. Let q, n ∈ N with 2 ≤ n − 1 < q ≤ 2(n − 1) and b := 2(n − 1) − q. Then

K_{q}(n, 1) ≥ ⌈\frac{2(q − 1)q − b}{2(q − 1)(n − 1) − b}q^{n−2}⌉ .

Proof. Because of Lemma 1 (iv), the inequalities h_{C}(j, k, x, 1) ≤ h_{C}(k, j, x, x) and hence ∑_{j∈Z_{n}} g_{C}(j, x, 1) ≤ ∑_{j∈Z_{n}} g_{C}(j, x, x) are valid. Therefore, ∑_{j∈Z_{n}} ∑_{x≥2} g_{C}(j, x, 1)s(x, x) ≤ ∑_{x≥2} s(x, x) ∑_{j∈Z_{n}} g_{C}(j, x, x) ≤ ∑_{j∈Z_{n}} ∑_{x,t} g_{C}(j, x, t)s(x, t) and thus there exists a k ∈ Z_{n} with

∑_{x≥2} g_{C}(k, x, 1)s(x, x) ≤ (q − 1)((n − 1)|C| − q^{n−1})  (18)

by inequality (17). Furthermore, x ≥ 2 implies

x − \frac{q}{n − 1} ≥ \frac{b}{n − 1}(x − 1)  (19)

since n − 1 < q. After this preparation, one obtains

(q − 1)((n − 1)|C| − q^{n−1}) ≥ ∑_{x,t≥2} g_{C}(k, x, t)s(x, x)
≥ ∑_{x≥2;t≥1} g_{C}(k, x, t) (x − \frac{q}{n − 1}) − ∑_{x≥2} g_{C}(k, x, 1) (x − \frac{q}{n − 1})
≥ \frac{b}{n − 1} ∑_{x,t} g_{C}(k, x, t)(x − 1) − ∑_{x≥2} g_{C}(k, x, 1)s(x, x)
≥ b|C| − bq^{n−2} − (q − 1)((n − 1)|C| − q^{n−1})

by (15), (16), (17), (18), (19) and Lemma 1. Finally,

(2(q − 1)(n − 1) − b)|C| ≥ 2(q − 1)q^{n−1} − bq^{n−2}

follows which proves the theorem. □

In case of q = 2(n − 1), Theorem 1 coincides with bound (14). In case of 2 ≤ n − 1 < q < 2(n − 1), the rational number \frac{2(q−1)q−b}{2(q−1)(n−1)−b}q^{n−2} is perceptible greater than \frac{q^{n−1}}{n−1} . Therefore, Theorem 1 is in many cases stronger than (14).

Examples. Theorem 1 shows K_{5}(5, 1) ≥ 160 and K_{6}(5, 1) ≥ 330 as well as K_{7}(5, 1) ≥ 606 instead of the lower bounds 157, 324 and 601, respectively, given by (14).

6. A new construction

The following construction uses the notion of a quasigroup.

Theorem 2. Every code C ⊆ K^{n} with minimum distance d(C) ≥ 2 and covering radius t(C) = 1 gives rise to a code \overline{C} ⊆ K^{n+1} of cardinality |\overline{C}| = |K| · |C| with minimum distance d(\overline{C}) ≥ 2 and covering radius t(\overline{C}) = 1. Hence, v(q, n + 1, 2) ≤ qv(q, n, 2) for all q, n ∈ N \ {1}.

Proof. Clearly, n ≥ d(C) ≥ 2. Define an addition on K such that (K, +) is a quasigroup. Put

\overline{C} := \{(w_{1}, …, w_{n+1}) ∈ K^{n+1}|(w_{1}, …, w_{n−1}, w_{n} + w_{n+1}) ∈ C\}.

(I) Let \overline{v}, \overline{w} ∈ \overline{C} with (v_{1}, …, v_{n+1}) := \overline{v} ≠ \overline{w} =: (w_{1}, …, w_{n+1}). Put

d := d((v_{1}, …, v_{n−1}), (w_{1}, …, w_{n−1})).

In case of d = 0, the equality v_{n} + v_{n+1} = w_{n} + w_{n+1} and, hence, d(\overline{v}, \overline{w}) = 2 follows. In case of d = 1, the statement v_{n} + v_{n+1} ≠ w_{n} + w_{n+1} and, hence, d(\overline{v}, \overline{w}) ≥ 2 follows. In case of d ≥ 2, trivially d(\overline{v}, \overline{w}) ≥ 2 follows. Herewith, d(\overline{C}) ≥ 2. (II) Let \overline{v} = (v_{1}, …, v_{n+1}) ∈ K^{n+1}. Put v := (v_{1}, …, v_{n−1}, v_{n} + v_{n+1}). There exists a codeword w = (w_{1}, …, w_{n}) ∈ C with d(v, w) ≤ 1. In case of d(v, w) = 0, clearly \overline{v} ∈ \overline{C}. So, let d(v, w) = 1. If there exists an index x ∈ Z_{n−1} with v_{x} ≠ w_{x}, the equality v_{n} + v_{n+1} = w_{n} is valid and therefore \overline{w} := (w_{1}, …, w_{n−1}, v_{n}, v_{n+1}) ∈ \overline{C} as well as d(\overline{v}, \overline{w}) = 1. If such an index does not exist, v_{n} + v_{n+1} ≠ w_{n}. Let z ∈ K be the unique solution of v_{n} + z = w_{n}. Then, \overline{w} := (w_{1}, …, w_{n−1}, v_{n}, z) = (v_{1}, …, v_{n−1}, v_{n}, z) ∈ \overline{C} and d(\overline{v}, \overline{w}) = 1. On the whole, t(\overline{C}) ≤ 1. By d(\overline{C}) ≥ 2, this means t(\overline{C}) = 1. (III) The cardinality of \overline{C} is equal to |K| · |C| because the construction is based on a quasigroup. □

Connecting Theorem 2 with equation (4), one gets the following upper bound.

Corollary 1. Let q, n ∈ N with 2 ≤ q and 3 ≤ n. Then

v(q, n, 2) ≤ q^{n−3} ⌈\frac{1}{2}q^{2}⌉ .

This corollary together with the lower bound (8) proves e.g. v(2, 4, 2) = 4.

7. A necessary condition

Considering all mentioned results on v(q, n, 2), one can remark that the case n = 2, the case n = 3 and the case n = 4, q ≤ 3 are solved. If q = n = 4, bound (2), equation (11) and Corollary 1 show

24 ≤ v(4, 4, 2) ≤ 32.

No sharper bound is known. (The code which was used to establish equation (11) has minimum distance 1. Therefore, it cannot be applied here.)

This open problem motivates the development of a necessary condition on the existence of codes of given cardinality with minimum distance at least 2 and covering radius 1.

Hämäläinen et al. [8] and Honkala/Litsyn [10] dealt in the binary case with so-called multiple coverings of the farthest-off points (MCF). Extending this notion to the q-ary case, a code C ⊆ K^{n} of order q and covering radius t(C) ≤ t, fulfilling

|B(v, t) ∩ C| ≥ μ for all v ∈ K^{n} with min{d(v, w)|w ∈ C} = t

is called an (n, |C|, t, μ) MCF of order q.

It is not difficult to prove the following application.

Theorem 3. Let C ⊆ K^{n} be a code of order q, length n, minimum distance at least 2 and covering radius t(C) ≤ t. Then, C is an (n, |C|, t, 1) MCF of order q and the puncturing

C′ := {(w_{1}, …, w_{n−1}) ∈ K^{n−1}|∃w_{n} ∈ K with (w_{1}, …, w_{n}) ∈ C}

of C is an (n − 1, |C|, t, q) MCF of order q.

This theorem is a slightly modified version of a theorem given by Hämäläinen et al. [8]. It yields that the existence of an (n − 1, u, 1, q) MCF of order q is necessary for the existence of a code of order q, length n, cardinality u, minimum distance at least 2 and covering radius 1.

In case of q = n = 4 and u = 24, the existence of the latter code is an open problem. But the necessary condition from above can be fulfilled: The code

\begin{matrix}\{(1, 1, 1), & (1, 1, 2), & (1, 2, 1), & (1, 2, 2), & (1, 3, 3), & (1, 4, 4), \\ (2, 1, 1), & (2, 1, 2), & (2, 2, 1), & (2, 2, 2), & (2, 3, 4), & (2, 4, 3), \\ (3, 1, 4), & (3, 2, 3), & (3, 3, 2), & (3, 3, 4), & (3, 4, 1), & (3, 4, 3), \\ (4, 1, 3), & (4, 2, 4), & (4, 3, 1), & (4, 3, 3), & (4, 4, 2), & (4, 4, 4)\} \end{matrix}

is a (3,24,1,4) MCF of order 4. (No puncturing of the code which was used to establish equation (11) is a (3, 24, 1, 4) MCF.)

References

[1] Chen, W.; Honkala, I. S.: Lower Bounds for q-ary Covering Codes. IEEE Trans. Inform. Theory 36 (1990), 664–671.

[2] Cohen, G. D.; Karpovsky, M. G.; Mattson, H. F., Jr.; Schatz, J. R.: Covering Radius – Survey and Recent Results. IEEE Trans. Inform. Theory 31 (1985), 328–343.

[3] Cohen, G. D.; Lobstein, A. C.; Sloane, N. J. A.: Further Results of the Covering Radius of Codes. IEEE Trans. Inform. Theory 32 (1986), 680–694.

[4] Cohen, G. D.; Litsyn, S. N.; Lobstein, A. C.; Mattson, H. F., Jr.: Covering Radius 1985– 1994. Appl. Algebra Eng. Comm. Comp. 8 (1997), 173–239.

[5] Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A.: Covering Codes. North-Holland, Amsterdam 1997.

[6] Graham, R. L.; Sloane, N. J. A.: On the Covering Radius of Codes. IEEE Trans. Inform. Theory 31 (1985), 385–401.

[7] Habsieger, L.: Lower Bounds for q-ary Coverings by Spheres of Radius One. J. Comb. Theory, Ser. A, 67 (1994), 199–222.

[8] Hämäläinen, H. O.; Honkala, I. S.; Litsyn, S. N.; Östergård, P. R. J.: Bounds for Binary Codes that are Multiple Coverings of the Farthest-off Points. SIAM J. Discr. Math. 8 (1995), 196–207.

[9] Heise, W.; Quattrocchi, P.: Informations- und Codierungstheorie. 3. Auflage, Springer, Berlin, Heidelberg 1995.

[10] Honkala, I.; Litsyn, S.: Generalizations of the Covering Radius Problem in Coding Theory. Bull. Inst. Combin. 17 (1996), 39–46.

[11] Kalbfleisch, J. G.; Stanton, R. G.: A Combinatorial Problem in Matching. J. London Math. Soc. 44 (1969), 60–64; Corrigendum. J. London Math. Soc., Second Ser., 1 (1969), 398.

[12] Kalbfleisch, J. G.; Weiland, P. H.: Some New Results for the Covering Problem. Recent Prog. Comb., Proc. Third Waterloo Conf. 1968, Academic Press, New York 1969.

[13] van Lint, J. H.: Recent Results on Covering Problems. In Mora, T. (ed.): Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proc. 6th Intern. Conf. (Rome 1988), Springer, Berlin, New York 1989.

[14] MacWilliams, F. J.; Sloane, N. J. A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam, New York, Oxford 1977.

[15] Quistorff, J.: Simultane Untersuchung mehrfach scharf transitiver Permutationsmengen und MDS-Codes unter Einbeziehung ihrer Substitute. Habilitationsschrift, submitted to Univ. Hamburg 1998.

[16] Quistorff, J.: On Full Partial Quasigroups of Finite Order and Local Cardinal Maximum Codes. Beiträge Algebra Geom. 40 (2) (1999), 495–502.

[17] Rodemich, E. R.: Coverings by Rook Domains. J. Combin. Th. 9 (1970), 117–128.

[18] Stanton, R. G.; Horten, J. D.; Kalbfleisch, J. G.: Covering Theorems for Vectors with Special Reference to the Case of Four and Five Components. J. London Math. Soc., Second Ser., 1 (1969), 493–499.

[19] Stojaković, Z.; Ušan, J.: A Classification of Finite Partial Quasigroups. Univ. u Novom Sadu Zb. rad. Prirod.-mat. fak., Serija za mat. 9 (1979), 185–190.

[20] van Wee, G. J. M.: Improved Sphere Bounds on the Covering Radius of Codes. IEEE Trans. Inform. Theory 34 (1988), 237–245.

[21] van Wee, G. J. M.: Bounds on Packings and Coverings by Spheres in q-ary and Mixed Hamming Spaces. J. Combin. Th., Ser. A, 57 (1991), 117–129.

Received July 1, 1999