# Covering code

## Description

A code \(C\) in a metric space is covering if the union of balls of some radius centered at the codewords covers the entire space. For example, 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\).

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)~. \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{perfect-ref} \end{align} Linear \([n,k]_q\) codes also satisfy the redundancy bound \begin{align} \rho(C)\leq n-k \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{spherepacking-perfect-label} \end{align} A code is perfect iff it satisfies Eqs. \eqref{perfect-ref} and \eqref{spherepacking-perfect-label} with equality.

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

## Realizations

## Parent

## Child

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

## Zoo code information

## References

- [1]
- G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997).
- [2]
- H. Hamalainen et al., “Football Pools--A Game for Mathematicians”, The American Mathematical Monthly 102, 579 (1995). DOI
- [3]
- A. Barg, “At the Dawn of the Theory of Codes”, The Mathematical Intelligencer 15, 20 (1993). DOI

## Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/covering.yml.