Repetition code

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 givesAt $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.

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.