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 [math]\displaystyle{ q\geq 2 }[/math], [math]\displaystyle{ n\geq 1 }[/math], [math]\displaystyle{ R\geq 0 }[/math] be integers. A code [math]\displaystyle{ C\subseteq Q^n }[/math] over an alphabet Q of size |Q| = q is called q-ary R-covering code of length n if for every word [math]\displaystyle{ y\in Q^n }[/math] there is a codeword [math]\displaystyle{ x\in C }[/math] such that the Hamming distance [math]\displaystyle{ d_H(x,y)\leq R }[/math]. 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 [math]\displaystyle{ Q^n }[/math]. 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 [math]\displaystyle{ K_q(n,R) }[/math] 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 [math]\displaystyle{ K_q(n,1)\geq q^{n-1}/(n-1) }[/math] and [math]\displaystyle{ K_q(n,n-2)\geq q^2/(n-1) }[/math].[2] The covering problem is closely related to the packing problem in [math]\displaystyle{ Q^n }[/math], 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 [math]\displaystyle{ n=\tfrac12 (3^k-1) }[/math] 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
- ↑ Kamps, H.J.L.; van Lint, J.H. (December 1967). "The football pool problem for 5 matches" (in en). Journal of Combinatorial Theory 3 (4): 315–325. doi:10.1016/S0021-9800(67)80102-9. http://alexandria.tue.nl/repository/freearticles/593454.pdf. Retrieved 9 November 2022.
- ↑ "Bounds on K3(n, R) (lower and upper bounds on the size of ternary optimal covering codes)" (in en). http://old.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
External links
 |  |
