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

Data compression both with or without compression [1].Football-pool problem: finding the smallest number of bets on a set of matches needed to guarantee at least one bet has at most \(\rho\) errors [2][3].

Parent

Child

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

Zoo code information

Internal code ID: covering

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: covering

Cite as:
“Covering code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/covering
BibTeX:
@incollection{eczoo_covering, title={Covering code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/covering} }
Permanent link:
https://errorcorrectionzoo.org/c/covering

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.