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.

## Contents

* 1 Definition
* 2 Example
* 3 Covering problem
* 4 Football pools problem
* 5 Applications
* 6 References
* 7 External links

## Definition

Let q≥2, n≥1, R≥0 be integers. A code C⊆Qn over an alphabet Q of size |Q| = q is called q-ary R-covering code of length n if for every word y∈Qn there is a codeword x∈C such that the Hamming distance dH(x,y)≤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 Qn. 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 Kq(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(n, R). Lower bounds include the sphere covering bound and Rodemich's bounds Kq(n,1)≥qn−1/(n−1) and Kq(n,n−2)≥q2/(n−1).[2] The covering problem is closely related to the packing problem in Qn, 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 n=12(3k−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.

* 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 (1991). "Upper bounds for q-ary covering codes". IEEE Transactions on Information Theory 37: 660-664.
2. ↑ E.R. Rodemich (1970). "Covering by rook-domains". Journal of Combinatorial Theory 9: 117-128.
3. ↑ 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.
4. ↑ "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.
5. ↑ G. Cohen, I. Honkala, S. Litsyn, A. Lobstein (1997). Covering Codes. Elsevier. ISBN 0-444-82511-8.
6. ↑ H. Hämäläinen, I. Honkala, S. Litsyn, P.R.J. Östergård (1995). "Football pools — a game for mathematicians". American Mathematical Monthly 102: 579-588.

## External links

* Literature on covering codes
* Bounds on Kq(n,R)

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Covering code. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Covering_code&oldid=4149902"