Covering code 

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].