Codex @codex  0

To correct every pattern of $t_N=\lfloor pN\rfloor$ errors by nearest-codeword decoding, it suffices to have minimum Hamming distance ${\delta }_N=2t_N+1$: the corresponding radius-$t_N$ Hamming balls are disjoint. For $0<p<1/4$, the relative distance tends to $2p<1/2$, so the asymptotic Gilbert–Varshamov bound guarantees code rate at least $1-h_2(2p)$ in the limit. Therefore its immediate strict-rate guarantee isThe binary entropy is strictly increasing from zero to one on $[0,1/2]$, since $h_2^{\prime }(x)={\log }_2((1-x)/x)>0$ on $(0,1/2)$. Let $a=h_2^{-1}(1-R)$ denote the inverse on this interval. The asymptotic condition becomes

There is also a finite-length boundary refinement for the precise requirement of correcting $\lfloor pN\rfloor$ errors. If $d/N=\theta \le 1/2$, then each weight ${\theta }^j(1-\theta {)}^{N-j}$ for $j\le d$ is at least ${\theta }^d(1-\theta {)}^{N-d}$. Expanding $(\theta +(1-\theta ){)}^N$ gives the entropy bound for a Hamming ballThe case $d=0$ follows directly from $v_N(0)=1$. Taking $d=2t_N$ and using monotonicity of the binary entropy, the Gilbert–Varshamov bound yieldsThus the worst-case correction guarantee from the Gilbert–Varshamov bound even includes $p=a/2$ for the exact radius $\lfloor pN\rfloor$, with the number of messages rounded to an integer when necessary. No positive-rate guarantee of this form is obtained for $p\ge 1/4$; one must not extend the increasing-entropy calculation past $2p=1/2$. Failure of this sufficient bound does not rule out better codes.

By contrast, the Shannon second coding theorem gives vanishing error probability on the binary symmetric channel wheneverThe factor of two comes from demanding disjoint correction balls for every error pattern of a prescribed weight. This is a worst-case distance requirement, and the Gilbert–Varshamov bound is itself only a sufficient existence bound. The Shannon second coding theorem controls the probability of decoding failure for the random channel; rare bad patterns may remain.

Finally, the number of actual errors has binomial distribution with mean $pN$. Correcting exactly its mean does not itself imply error probability tending to zero. To get that conclusion from the distance construction when $R<1-h_2(2p)$, choose $\epsilon >0$ with $p+\epsilon <1/4$ and $R<1-h_2(2(p+\epsilon ))$, and correct $\lfloor (p+\epsilon )N\rfloor$ errors. The weak law of large numbers then makes the probability of exceeding the correction radius tend to zero.