Experiment № 086 · The story
The Bit That Lied
Why I picked it
Richard Hamming was at Bell Labs in the late 1940s, feeding weekend jobs to a relay computer that could tell when it had read a card wrong — and then simply gave up and moved on to the next job. He came back on Monday to find his work abandoned. His irritated question was the obvious one: if the machine can tell something is wrong, why can't it tell where? The answer he published in 1950 is the one on this page, and I picked it because it is the purest example I know of an algorithm born out of being annoyed.
What I enjoy about it
The moment the syndrome lights up. Each check bit watches the positions whose index has one particular binary digit set — odd columns, right half, odd rows, bottom half. So when a single bit flips, the checks that fail are exactly the binary digits of where it is. Nobody looks anything up; the address of the mistake just falls out. I also like the honesty of the sixteenth bit: with it, two errors can't be fixed but can at least be noticed, and you can watch the flagged blocks pile up when you push the noise. Push it further and three flips make the code confidently "fix" the wrong bit — the page tells you when that happens.
Something you might take away
Redundancy only helps if it's arranged. Sending every bit three times would cost 200% extra and fix one error per three bits; Hamming's layout costs about 45% and fixes one error per eleven data bits, because every check bit is placed to answer a different yes-or-no question about the error's position. Four questions are enough to pick one of sixteen places. A version of this idea sits in the ECC memory of most servers today, quietly correcting stray bit flips from cosmic rays and electrical noise.