Error-correcting codes · after R. W. Hamming, Bell System Technical Journal, April 1950

Hamming — the letterform that heals itself

Seven bits carry four. Three parity checks stand guard over every letter. When noise flips a bit — and it always does — the failing checks, read as a binary number, spell out the exact address of the wound. The letterform heals itself.

Exhibit begins below

¶ 1

The living message

Transmission under continuous noise Channel live

Parity inspectorawaiting traffic

Sent······· Received·······

Syndrome C4·C2·C1 — — —

STANDING BY

Service ledger — measured, not scripted

Errors struck

Located

Corrected

Residual errors after service: 0 Double faults — syndrome misled, block retransmitted: 0 Self-cancelled flips (same bit struck twice): 0 Channel noise: one strike every 4.3–5.7 s; one strike in twelve arrives as a double.

Each glyph travels as a Hamming(7,4) codeword — four data bits naming the letter, three parity bits standing guard at positions 1, 2 and 4. Noise strikes on its own schedule; click any bit cell to strike one yourself. Strike a second bit in the same codeword before it is serviced and watch the syndrome lie.

¶ 2

How the code finds the wound

Number the seven bits 1 through 7. Put parity at the powers of two — positions 1, 2, 4 — and data everywhere else. Each parity bit watches exactly the positions whose binary address contains its own: C1 sums bits 1·3·5·7, C2 sums 2·3·6·7, C4 sums 4·5·6·7. A clean codeword passes all three checks.

Flip any single bit and a unique combination of checks fails. Flip bit 5: C1 and C4 fail, C2 passes — syndrome 101, which is binary for five. The arithmetic does not search for the error. It computes its address.

Strike twice in one codeword and the syndrome lies. It points at a third, innocent bit, and the machine confidently corrects its way to the wrong letter — a clean, valid, incorrect codeword. Minimum distance three buys you one correction or two detections, never both at once. Hamming knew: his extended (8,4) code spends one more parity bit on the whole word to catch the double and call for retransmission. When a double fault lands here, the exhibit owns the miscorrection, stamps it, and retransmits.

C1 = b1 ⊕ b3 ⊕ b5 ⊕ b7 C2 = b2 ⊕ b3 ⊕ b6 ⊕ b7 C4 = b4 ⊕ b5 ⊕ b6 ⊕ b7 syndrome = C4·C2·C1 → address of the flipped bit

The three parity circles of Hamming(7,4). Every data bit sits in the overlap of the checks that guard it; every single-bit error leaves a unique signature of failed circles. All three fail → bit 7. Only C1 → bit 1 itself.

¶ 2a

The message codebook

Four data bits address sixteen symbols; this message needs thirteen, so three slots print as garble if a double fault ever decodes into them. Rest the cursor on a row to see every codeword in the stream that carries it.

¶ 3

The arithmetic of redundancy

4 / 7 ≈ 0.571

The code rate. Four message bits ride in every seven sent — three sevenths of the channel is armour, and the armour is total against any single strike.

2³ − 1 = 7

Three checks address exactly seven positions, with syndrome 000 left over to say all clear. Nothing wasted, nothing missing.

d = 3

Every codeword differs from every other in at least three places. One flip leaves you nearest the truth; two flips leave you nearest a lie.

16 × 8 = 2⁷

Sixteen codewords, each owning itself plus its seven single-flip neighbours, tile all 128 seven-bit words exactly. Hamming(7,4) is a perfect code.

¶ 4

Two lost weekends, 1947

Richard W. Hamming ran his problems on Bell Labs’ relay computers over the weekend, unattended. The machines already checked parity — they could see an error — but a single failed bit made them dump the whole job and move to the next one. Two consecutive Mondays of discarded work provoked the right question: if the machine can detect an error, why can’t it find the position and put the bit back?

The answer ran as “Error Detecting and Error Correcting Codes,” Bell System Technical Journal 29, April 1950 — fourteen pages that put redundancy to work as armour instead of alarm. The scheme above is its first construction, and it has never stopped shipping: ECC memory scrubs single flips with Hamming-class codes today, and every deep-space packet since has carried its descendants.