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 , , 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.[1]
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 .[2] 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 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 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.
- 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
- ↑ P.R.J. Östergård, Upper bounds for q-ary covering codes, IEEE Transactions on Information Theory, 37 (1991), 660-664
- ↑ E.R. Rodemich, Covering by rook-domains, Journal of Combinatorial Theory, 9 (1970), 117-128
- ↑ http://alexandria.tue.nl/repository/freearticles/593454.pdf
- ↑ http://www.sztaki.hu/~keri/codes/3_tables.pdf
- ↑ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8
- ↑ 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