Repetition Code

Repeat each bit n times, decode by majority — the rate vs. distance tradeoff at its starkest.

The idea

The repetition code is the simplest error-correcting code: to protect a message bit against a channel that occasionally flips bits, send $n$ copies of it and let the receiver take a majority vote.

The $(n, 1)$ repetition code — block length $n$, one message bit per block — has exactly two codewords, the all-zero string and the all-one string. The decoder reads each block of $n$ received bits and outputs the majority value, so the received words split into two decoding regions, one around each codeword. If fewer than half of the copies were flipped in transit, the majority is still the bit that was sent, and the vote repairs the damage; if half or more were flipped, the decoder outputs the wrong bit without detecting anything wrong.

Two numbers measure the code. The rate $R = k/n$ is the fraction of transmitted bits that carry message rather than repetition; here $k = 1$, so $R = 1/n$. The minimum distance $d$ is the smallest number of positions in which two distinct codewords differ; here $d = n$, and a code of minimum distance $d$ corrects up to $\lfloor (d-1)/2 \rfloor$ errors, where $\lfloor x \rfloor$ means $x$ rounded down. Repetition buys distance by spending rate: distance $n$ costs rate $1/n$.

Ways to work on it

• Walkthrough. Encode, corrupt, decode by majority. Compute rate and correction radius.
• Practice. Vary n and the number of channel errors — decide whether decoding succeeds.
• Hardest. Decide whether decoding succeeds for longer codes with borderline error counts.

Not sure where to start? Take the ten-question placement test.