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.