# Covering code

## Description

A \(q\)-ary code \(C\) is \(\rho\)-covering if \(\forall v \in GF(q)^{n}\), there is a codeword \(c \in C\) such that the Hamming distance \(D(c,v)\leq \rho\). More generally, a covering code in a metric space is covering if the union of balls of some radius centered at the codewords covers the entire space.

The covering radius \(\rho(C)\) is the smallest non-negative integer \(\rho\) such that \(C\) is \(\rho\)-covering, i.e. \begin{align} \rho(C)=\max_{{v\in GF(q)^{n}}}\min_{{c\in C}}d(v,c)~. \tag*{(1)}\end{align} For a linear code \([n,k]_q\), the covering radius is the minimum number of columns of the code's parity check matrix which cover \(GF(q)^{n-k}\).

The covering radius satisfies various inequalities. A code \(C\) with distance \(d\) satisfies the relation \begin{align} \rho(C)\geq \frac{|d-1|}{2}~. \label{eq:perfect-ref} \tag*{(2)}\end{align} Linear \([n,k]_q\) codes also satisfy the redundancy bound \begin{align} \rho(C)\leq n-k \tag*{(3)}\end{align} and the sphere covering bound \begin{align} \rho(C)\leq \min{\left(p~\bigg\rvert \sum_{i=0}^{p} {n \choose i}(q-1)^{i}|C| \geq q^{n}\right)}~. \label{eq:spherepacking-perfect-label} \tag*{(4)}\end{align} A code is perfect iff it satisfies Eqs. (2) and (4) with equality.

In general, finding the covering radius of code is NP-Hard [1]. Complexity analysis as well as an extensive study on bounds can be found in Ref. [2].

## Realizations

## Notes

## Parent

- Weighed-covering code — An \(m\)-weighed covering code for \(m_j=1\) is a covering code of covering radius at most \(r\) ([5], Ch. 13).

## Child

- Perfect code — Perfect codes are covering codes with minimum number of codewords

## References

- [1]
- A. McLoughlin, “The complexity of computing the covering radius of a code”, IEEE Transactions on Information Theory 30, 800 (1984) DOI
- [2]
- G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997).
- [3]
- H. Hamalainen et al., “Football Pools--A Game for Mathematicians”, The American Mathematical Monthly 102, 579 (1995) DOI
- [4]
- A. Barg, “At the Dawn of the Theory of Codes”, The Mathematical Intelligencer 15, 20 (1993) DOI
- [5]
- G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering codes. Elsevier, 1997.

## Page edit log

- Victor V. Albert (2022-07-19) — most recent
- Mustafa Doger (2022-03-31)

## Cite as:

“Covering code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/covering