Error-Correcting Code
Codes that add structured redundancy so corrupted bits can be detected — and even located and repaired.
Contents
Error-Correcting Code
An error-correcting code adds carefully structured redundancy to a message so that, when noise flips some of the bits in transit, the receiver can not only notice the damage but repair it — without ever asking for a retransmission. This is what lets a scratched DVD still play, a deep-space probe whisper across billions of kilometers, and a memory chip shrug off a cosmic ray.
The trick is to use only a sparse set of valid codewords, chosen so that every two of them differ in many bit positions (a large Hamming Distance). A few flipped bits then leave you nearer to the original codeword than to any other, so the decoder snaps the corrupted word back to the closest legal one.
Parity, the smallest example
Add one parity bit equal to the XOR of all the data bits, so every valid codeword has an even number of 1s. Flip any single bit and the parity becomes odd — instant detection. But a single parity bit only detects; it cannot say which bit flipped, so it cannot correct. To locate the error you need several overlapping parity checks.
Hamming(7,4): locate and fix one flip
Richard Hamming's 1950 code packs 4 data bits into a 7-bit codeword using 3 parity bits, placed at positions 1, 2, and 4. Each parity bit checks a different overlapping group of positions:
- p_1 (pos 1) checks positions 1, 3, 5, 7
- p_2 (pos 2) checks positions 2, 3, 6, 7
- p_4 (pos 4) checks positions 4, 5, 6, 7
The genius is the overlap. When a single bit flips, the pattern of which checks fail spells out, in binary, the exact position of the error. Compute the three failing/passing checks as a 3-bit number — the syndrome — and it literally equals the index of the broken bit. Read it, flip that bit back, done.
Click any of the seven bits below to corrupt it. Watch the parity checks light up red and the syndrome pinpoint the flip — then read the corrected codeword the decoder recovers.
The cost and the payoff
Redundancy is not free — Hamming(7,4) spends 7 bits to carry 4, a rate of 4/7. But the Channel Capacity theorem promises that as long as you stay below capacity, codes exist that push the error rate as low as you like while keeping the rate high. Modern codes (Reed–Solomon, LDPC, turbo, polar) are the descendants of Hamming's insight, and they operate startlingly close to Shannon's limit.