Cobra Effect · Computing and information
The codes that fix their own mistakes
How a frustrated mathematician invented codes that find and fix their own errors.
7 cards, read aloud in 2:27, with a test and sources.
In the late 1940s, Richard Hamming used a huge relay computer at Bell Labs.
Hamming was a mathematician who had worked on the Manhattan Project before joining Bell Labs in 1946. The machine could detect some errors in its own work. During the week, operators fixed them. At weekends, an error made the machine abandon the job.
Hamming left long calculations running over weekends, and came back to find nothing done.
An error early on had stopped his job, and the machine had moved on to the next. It happened more than once. If a machine can tell there is an error, he reasoned, why can’t it find it and fix it?
Simple checks could only say that something had gone wrong.
A parity check adds one extra bit, so that the number of ones is always even. If a single bit flips, the count turns odd, and the error shows up. But the check cannot say which bit was wrong.
Hamming found a way to use several overlapping checks.
In his seven bit code, four bits carry the message and three bits are checks. Each check covers a different group of bits, and the groups overlap. If one bit flips, the pattern of failed checks points to exactly which one it was.
Then the machine can simply flip that bit back.
The message is corrected, without anyone having to send it again. Claude Shannon’s 1948 paper had already described the code, crediting Hamming. Hamming published his own paper on it in 1950.
Error correcting codes are now everywhere.
They protect data in computer memory, on discs, and in signals sent across the world. Later codes can correct many errors at once, building on the same idea. In 1968, Hamming received the Turing Award, partly for this work.
So when a system keeps failing in the same way, ask why it cannot fix itself.
Hamming’s frustration was the starting point. He turned a machine that could only notice errors into one that could correct them. A good question born of irritation can outlast the problem that prompted it.
Sources
- Richard Hamming, IEEE Computer Society, Computer Pioneers. His life, including the relay computer that lost his weekend work.
- Error Detecting and Error Correcting Codes, Richard Hamming, Bell System Technical Journal, 1950. The original paper.
- Richard W. Hamming, Engineering and Technology History Wiki. A biography, and his Turing Award.
Nearby ideas
- The man who measured information. How Claude Shannon turned information into something that could be measured in bits.
- The question no machine can answer. How Alan Turing imagined the computer, and proved some questions have no answer.
- The tiny switch that replaced the valve. How a slab of germanium at Bell Labs gave rise to every modern chip.
- The notes that imagined a computer. How Ada Lovelace's notes on an unbuilt machine imagined what computers could do.
- The codebreakers who read Enigma. How Polish mathematicians and Bletchley Park broke Germany's Enigma machine.