Hamming Code

Positions 1, 2, 4 and 8 are reserved; everything else carries data.

1. Number seven positions 1 to 7.
2. Mark positions 1, 2 and 4 as parity; 3, 5, 6 and 7 hold four data bits.
3. Write your four data bits into their positions.

Each parity bit covers every position whose number contains its bit.

1. P1 covers positions 1, 3, 5, 7 — those with a 1 in the ones place.
2. P2 covers 2, 3, 6, 7 — a 1 in the twos place.
3. P4 covers 4, 5, 6, 7 — a 1 in the fours place.
4. Set each parity bit to make its own group even.

The correction, performed by arithmetic rather than by searching.

1. Hand your seven-bit block to someone; have them flip one bit secretly.
2. Check each parity group and write 1 for a failed group, 0 for a passed one.
3. Read those results as a binary number: P4 P2 P1.
4. That number is the position of the broken bit. Flip it back.

Every code pays for its capability, and every code has a limit.

1. Count the overhead here: 3 parity bits for 4 data bits.
2. Work out the overhead for 11 data bits — it needs only 4 parity bits.
3. Now flip TWO bits and run the location procedure.

Richard Hamming published the code in 1950, having worked it out at Bell Labs where he had access to a relay computer only at weekends. His account of the motivation is refreshingly plain: the machine could tell something had gone wrong and then simply stopped, wasting the whole run, and he thought it should be able to do better.

What it added to the parity approach: a single parity bit detects one error and locates nothing. The two-dimensional grid in the parity blueprint locates an error but costs one bit per row and per column. Hamming's overlapping groups locate it with logarithmically few bits — for 11 data bits you need 4 parity bits where a grid would need far more. Same goal, three different costs, and the right choice depends on how much overhead the channel can afford.

Where it is used: ECC memory in servers uses a Hamming-derived code to correct single-bit errors caused by cosmic rays and electrical noise, silently, millions of times a day. Hamming distance — the number of positions in which two codewords differ — became a fundamental concept in coding theory and in fields far outside it, including genetics and machine learning.

Its neighbours in the space: Reed-Solomon handles bursts of adjacent errors and is what makes a scratched CD or an obscured QR code readable; convolutional and turbo codes suit continuous noisy streams like deep-space links; a simple retransmission request is often cheaper than any of them when the channel is bidirectional and cheap. Hamming's region is where errors are isolated, retransmission is impossible or expensive, and overhead must stay small.