Worst-case correction guarantee from the Gilbert–Varshamov bound ($R\le 1-h_2(2p),0\le p<1/4$)

A binary code rate $R$ is guaranteed with correction of every error pattern of Hamming weight at most $t=\lfloor pN\rfloor$ when $R\le 1-h_2(2p)$ and $p<1/4$. Choose minimum Hamming distance $2t+1$. The Gilbert–Varshamov bound and entropy bound for a Hamming ball give at least $2^{N(1-h_2(2p))}$ codewords. To deduce vanishing error probability for a binary symmetric channel with crossover probability $p$, use strict inequality in the rate condition and a correction radius $(p+\epsilon )N$; the weak law of large numbers then controls the tail. Correcting exactly the mean number of errors does not by itself ensure reliable transmission.

// Target: algebra.bigb