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 $q\geq 2$, $n\geq 1$, $R\geq 0$ be integers.
A code $C\subseteq Q^n$ over an alphabet ''Q'' of size , ''Q'', = ''q'' is called
''q''-ary ''R''-covering code of length ''n''
if for every word $y\in Q^n$ there is a codeword $x\in C$
such that the Hamming distance $d_H(x,y)\leq 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 $Q^n$.
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'' = is a 5-ary 2-covering code of length 4.

Covering problem

The determination of the minimal size $K_q(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 ''K''_''q''(''n'', ''R'').
Lower bounds include the sphere covering bound and
Rodemich's bounds $K_q(n,1)\geq q^/(n-1)$ and $K_q(n,n-2)\geq q^2/(n-1)$.
The covering problem is closely related to the packing problem in $Q^n$, 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 $n=\tfrac12 (3^k-1)$ then 3^''n''-''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

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 poolsH. 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
*Write-once memories
*Berlekamp-Gale game
*Speech coding
*Cellular telecommunications
* Subset sums and Cayley graphs

References

External links

Literature on covering codes



Coding theory