# 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 ${\displaystyle q\geq 2}$, ${\displaystyle n\geq 1}$, ${\displaystyle R\geq 0}$ be integers. A code ${\displaystyle 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 ${\displaystyle y\in Q^{n}}$ there is a codeword ${\displaystyle x\in C}$ such that the Hamming distance ${\displaystyle d_{H}(x,y)\leq R}$. In other words, the spheres (or balls or rook[disambiguation needed]-domains) of radius R with respect to the Hamming metric around the codewords of C have to exhaust the finite metric space ${\displaystyle 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 ${\displaystyle 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 Kq(nR). Lower bounds include the sphere covering bound and Rodemich’s bounds ${\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}$ and ${\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}$.[2] The covering problem is closely related to the packing problem in ${\displaystyle 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, K3(n,1), is sought.

If ${\displaystyle n={\tfrac {1}{2}}(3^{k}-1)}$ then 3n-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.

## 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