Concept

Hamming code

A code of sixteen seven-bit words whose balls of radius one fill the whole space exactly, correcting any single error. It is perfect in the technical sense that its correction balls fill the space exactly, leaving no word unaccounted for.

Named by 6 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.

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.

computation · Error-correcting codes
The syndrome of 1011010, and the bit it names. A parity-check matrix over a received word, with the resulting syndrome matched against the table of single-error syndromes.

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.

computation · Error-correcting codes
Channel capacity 1 − H(p), and three codes at p = 0.1. The capacity of the binary symmetric channel plotted against its flip probability, with the rates of repetition, the Hamming code and no coding marked at one flip probability.

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.

computation · Error-correcting codes
Decoding from 20 + m random combinations: the chance it works. Bars for the exact probability that 20 plus m random binary combinations of 20 message bits have full rank, with simulated frequencies as dots, for m from zero upwards.

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.

computation · Error-correcting codes
A word that survives losing any one of its bits. codeword 100110010110, a=0 mod 13; deletions at 1..12 all decoded.

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.

computation · Error-correcting codes
Seven hats, sixteen losses. All 128 ways seven red-or-blue hats can fall, each drawn as seven dots, with the 16 configurations the Hamming strategy loses framed: the team wins 112 of 128, a probability of 7/8.

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.

computation · Error-correcting codes

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

All concepts