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 , , be integers. A code over an alphabet Q of size |Q| = q is called q-ary R-covering code of length n if for every word there is a codeword such that the Hamming distance . 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 . 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.
Covering problem
The determination of the minimal size 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(n, R). Lower bounds include the sphere covering bound and Rodemich's bounds and . The covering problem is closely related to the packing problem in , 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 come up with a betting system over n football matches that, regardless of the outcome, has at most R 'misses'. Thus, for n matches with at most one 'miss', a ternary covering, K3(n,1), is sought.
If then 3n-k are needed, so for n = 4, k = 2, 9 are needed; for n = 13, k = 3, 59049 are needed. The best bounds known as of 2011 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 815-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 on covering codes lists the following applications.
Compression with distortion Data compression Decoding errors and erasures Broadcasting in interconnection networks Football pools Write-once memories Berlekamp-Gale game Speech coding Cellular telecommunications Subset sums and Cayley graphs
References
External links Literature on covering codes Bounds on