Covering code

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}$. 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.

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 lower and upper 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)}/(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.

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

Weblinks

• Literature on covering codes
• Bounds on $K_{q}(n,R)$