= Worst-case correction guarantee from the Gilbert–Varshamov bound
{title2=$R\leq1-h_2(2p),\quad0\leq 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\leq1-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+\varepsilon)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
Back to article page
