Covering code

In coding theory, a covering code is an object satisfying a certain mathematical property: A code of length n over Q is an R-covering code if for every word of Qn there is a codeword such that their Hamming distance is \le R.

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 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 lower and upper 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 K_q(n,1)\geq q^{n-1}/(n-1) and K_q(n,n-2)\geq q^2/(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.