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!



Your Answer

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