Lower bound on the covering radius of a code

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?

1 Answer

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)$.

• I'm afraid your formula is incorrect. For example, $V_q(1) = 1 + n(q-1)$. The value depends on $n$. Mar 25, 2016 at 0:06
• You'll have to work that out. There are many approximations out there, then you can find in any textbook, or online. You can also work back and see what approximation gives the required bound, and then try to prove it or to look it up. Good luck! Mar 25, 2016 at 0:15
• You tell me. Good luck! Mar 27, 2016 at 14:25
• There are standard bounds, and one of them probably works. You can look at the list as well as I can. Mar 27, 2016 at 21:40
• The same book where this exercise is taken from. Mar 27, 2016 at 21:46