Covering code

In coding theory, a covering code is a set of elements (called codewords) in a space, with the property that every element of the space is within a fixed distance of some codeword.

Definition

Let $q\geq 2$, $n\geq 1$, $R\geq 0$ be integers. A code $C\subseteq Q^n$ over an alphabet Q of size |Q| = q is called q-ary R-covering code of length n if for every word $y\in Q^n$ there is a codeword $x\in C$ such that the Hamming distance $d_H(x,y)\leq R$. In other words, the spheres (or balls or rook-domains) of radius R with respect to the Hamming metric around the codewords of C have to exhaust the finite metric space $Q^n$. The covering radius of a code C is the smallest R such that C is R-covering. Every perfect code is a covering code of minimal size.

Example

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} is a 5-ary 2-covering code of length 4.^[1]

Covering problem

The determination of the minimal size $K_q(n,R)$ of a q-ary R-covering code of length n is a very hard problem. In many cases, only upper and lower bounds are known with a large gap between them. Every construction of a covering code gives an upper bound on K_q(n, R). Lower bounds include the sphere covering bound and Rodemich’s bounds $K_q(n,1)\geq q^{n-1}/(n-1)$ and $K_q(n,n-2)\geq q^2/(n-1)$.^[2] The covering problem is closely related to the packing problem in $Q^n$, i.e. the determination of the maximal size of a q-ary e-error correcting code of length n.

Football pools problem

A particular case is the football pools problem, based on football pool betting, where the aim is to predict the results of n football matches as a home win, draw or away win, or to at least predict n - 1 of them with multiple bets. Thus a ternary covering, K₃(n,1), is sought.

If $n=\tfrac12 (3^k-1)$ then 3^n-k are needed, so for n = 4, k = 2, 9 are needed; for n = 13, k = 3, 59049 are needed.^[3] The best bounds known as of 2011^[4] are

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14
K3(n,1)	1	3	5	9	27	71-73	156-186	402-486	1060-1269	2854-3645	7832-9477	21531-27702	59049	166610-177147
K3(n,2)		1	3	3	8	15-17	26-34	54-81	130-219	323-555	729	1919-2187	5062-6561	12204-19683
K3(n,3)			1	3	3	6	11-12	14-27	27-54	57-105	117-243	282-657	612-1215	1553-2187

Applications

The standard work^[5] on covering codes lists the following applications.

• Compression with distortion
• Data compression
• Decoding errors and erasures
• Broadcasting in interconnection networks
• Football pools^[6]
• Write-once memories
• Berlekamp-Gale game
• Speech coding
• Cellular telecommunications
• Subset sums and Cayley graphs

References

1. P.R.J. Östergård, Upper bounds for q-ary covering codes, IEEE Transactions on Information Theory, 37 (1991), 660-664
2. E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128
3. http://alexandria.tue.nl/repository/freearticles/593454.pdf
4. http://www.sztaki.hu/~keri/codes/3_tables.pdf
5. G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8
6. H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård, Football pools - a game for mathematicians, American Mathematical Monthly, 102 (1995), 579-588

External links

• Literature on covering codes
• $K_q(n,R)$