Hamming code
Named by 6 essays across one field — each of them below, with the objects they name alongside it.
Sixteen spheres that fill a cube
A hundred and twenty-eight seven-bit words, sixteen of them chosen, and a ball of eight around each. Sixteen times eight is a hundred and twenty-eight exactly — so the balls tile the space with nothing left over, and the code wastes nothing at all.
Finding the error without reading the message
Three parity checks on a seven-bit word produce three bits. If they are all zero nothing is wrong; otherwise they are the number of the position that broke. The message is never consulted, because the answer does not depend on it.
The rate a noisy channel allows
A channel that flips one bit in ten can still carry messages with as few errors as anyone likes — at up to 0.531 message bits per transmitted bit, and at no rate above that. The number is Shannon's capacity, 1 − H(p). Repetition reaches reliability only by sending nothing; a code chosen at random gets there at any rate below the limit; and the reason there is a limit at all is a count of how many flip patterns a block of noise can hold.
Erasures a code can see
If a channel loses bits instead of flipping them, and says which ones it lost, its limit rises from 1 − H(p) to 1 − p — and reaching it needs nothing cleverer than a random matrix and the solution of simultaneous equations. A random code needs, on average, 1.607 symbols more than the message it carries, whatever the message's length, and that number is a constant Erdős proved irrational.
A code that survives a lost bit
A flipped bit leaves the word the right length and wrong in one place; a lost bit leaves it one short, with no sign of where the gap was. Keep only the words whose 1s sit at positions adding up to a multiple of n + 1, and any single lost bit can be put back. The price is about log₂(n + 1) bits, the same as the Hamming code pays for a flip.
Wrong guesses that arrive together
Seven players in red or blue hats each see every hat but their own, and must guess their own colour or pass. Every guess is a coin toss, yet with the Hamming code the team wins seven times in eight — not by making guesses better, but by making the wrong ones arrive together. The best chance for any number of players is fixed by the fewest losses that cover the cube.
Named alongside it
The objects these essays reach for when they reach for this one.
Error-correcting codeHamming distanceChannel capacityCosetCounting argumentExhaustive searchPerfect codeRandom codeBinomial distributionCovering codeDecision procedureEntropy