World's most popular travel blog for travel bloggers.

# Lower bound on the covering radius of a code

, ,
Problem Detail:

Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \geq \frac{n-k}{1+ \log_q{(n)}}$.

Could you give me a hint how we could show this?

###### Answered By : Yuval Filmus

The idea is to use a sphere packing argument, only for covering. Let $V_q(\rho)$ be the volume of a Hamming ball of radius $\rho$. The Hamming balls around all codewords cover the entire space, so $V_q(\rho) q^k \geq q^n$, or $V_q(\rho) \geq q^{n-k}$. To deduce the bound, use an approximation for $V_q(\rho)$.