Hamming code
Named by 4 essays across one field — each of them below, with the objects they name alongside it.
![The sixteen words of the [7,4] Hamming code. A table of sixteen seven-bit codewords with their data bits, parity bits and weights.](/f/the-sixteen-words-of-the-7-4-hamming-code-03f0d582.svg)
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Error-correcting codeChannel capacityCosetHamming distanceRandom codeBinomial distributionCounting argumentDecision procedureEntropyErasureLinear codeLinearity