4
$\begingroup$

I am trying to prove the following bounds for a $[n, k]$ code that can correct $t$ errors

\begin{align} 1-H\left(\frac{t}{n}\right)\geq \frac{k}{n}\geq 1-H\left(\frac{2t}{n}\right) \end{align} where \begin{align} H(x) = -x \log_2x-(1-x)\log_2(1-x) \end{align} is the binary Shannon entropy. I have two questions.

  1. Are these bounds true for all $[n, k]$ code that can correct $t$ errors? For the lower bound, or the Gilbert-Varshamov bound, from the text around Eq. 10.63 in Nielsen-Chuang, it seems to be the case (see here). However, from Gottesman, it seems like both bounds are true in certain asymptotic limits (see Eq. 1.15-1.20 in here).

  2. How to prove these two bounds? From the inequalities \begin{align} \frac{2^{nH(k/n)}}{n+1}\leq {n \choose k}\leq 2^{nH(k/n)} \end{align} which can be found here, together with the following known bounds (see again Gottesman) \begin{align} \sum_{j=0}^{2t}{n \choose j}\geq2^{n-k}\geq\sum_{j=0}^t{n \choose j} \end{align} I was almost able to obtain something similar to the bounds, but not exactly the same. Any helps are appreciated!

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.