Repetition code
= Repetition code
{wiki}
A binary repetition code represents one <bit> by repeating it $n$ times, using <codewords> $0^n$ and $1^n$. Their <Hamming distance> is $n$, and the <code rate> is $1/n$. For odd $n$, the <majority function> recovers the input whenever fewer than half the positions have flipped. Even $n$ allows a tied vote, so a decoder must specify how it handles that case.
For $n=3$, the received words $000,001,010,100$ decode to zero; $111,110,101,011$ decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.
If each position passes independently through a <binary symmetric channel> with crossover <probability> $q$, a decoded error requires at least two flips. The <binomial distribution> gives
$$
P_{\mathrm{error}}=3q^2(1-q)+q^3=3q^2-2q^3.
$$
At $q=0.1$, the uncoded error <probability> is $0.1$, while the three-bit code's decoded error <probability> is $0.028$. This improvement costs three transmitted <bits> per message <bit>. For $0<q<1/2$, $3q^2-2q^3<q$; for $q>1/2$, one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.
\Image[/repetition-code-reliability.png]
{title=Three-bit majority decoding corrects one flip and lowers the error probability at the cost of rate}
Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with <probability> $q$, repetition provides no improvement. More efficient <error-correcting codes> distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.