World's most popular travel blog for travel bloggers.

Lower bound on the covering radius of a code

, , No Comments
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?

Asked By : Evinda
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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54854

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback