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 K_q(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, K₃(n,1), is sought.

If [math]\displaystyle{ n=\tfrac12 (3^k-1) }[/math] then 3^n-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

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

External links

• Literature on covering codes
• Bounds on [math]\displaystyle{ K_q(n,R) }[/math]

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Covering code. Read more