Hamming Code

A Hamming code is a clever placement of parity bits that doesn't just detect a single-bit error — it pinpoints *which* bit flipped and corrects it, using surprisingly little overhead. The trick is to make the failing parity checks literally spell out the error's position in binary.

Why power-of-two positions

Number the codeword positions starting at 1. Put the parity bits at the power-of-two positions — 1, 2, 4, 8, … — and fill the rest with data bits. Each parity bit guards exactly the positions whose number, written in binary, has *its* bit set:

1. 1Parity bit at position 1 covers every position with the 1s bit set: 1, 3, 5, 7, …
2. 2Parity bit at position 2 covers every position with the 2s bit set: 2, 3, 6, 7, …
3. 3Parity bit at position 4 covers every position with the 4s bit set: 4, 5, 6, 7, …
4. 4Each parity bit is chosen to make its covered group hold an even number of 1s.

Worked example — Hamming(7,4)

Four data bits need three parity bits, giving a 7-bit codeword (positions 1–7). Say the sender transmits the codeword 0 1 1 0 0 1 1. The bit at position 5 flips in transit, so the receiver gets 0 1 1 0 1 1 1. Recompute the three checks:

received: pos 1234567 = 0 1 1 0 1 1 1

check p1 (pos 1,3,5,7): 0,1,1,1 -> three 1s -> odd  -> FAIL (1)
check p2 (pos 2,3,6,7): 1,1,1,1 -> four 1s  -> even -> ok   (0)
check p4 (pos 4,5,6,7): 0,1,1,1 -> three 1s -> odd  -> FAIL (1)

syndrome = p4 p2 p1 = 1 0 1 (binary) = 5
-> bit 5 is wrong; flip it back to correct.

The two failing checks, 1 and 4, sum to 5 — exactly the corrupted position. Flip position 5 and the original data is restored. In general a Hamming code is an (n, n − log₂n) code: the parity overhead grows only *logarithmically* with the data size, which is why it's far cheaper than sending everything twice.