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.

over an alphabet Q of size |Q| = q is called q-ary R-covering code of length n if for every word

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

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.

[1] The determination of the minimal size

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

[2] The covering problem is closely related to the packing problem in

, i.e. the determination of the maximal size of a q-ary e-error correcting code of length n. 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.

[3] The best bounds known as of 2011[4] are The standard work[5] on covering codes lists the following applications.