Error-correcting code
Named by 19 essays across 2 fields — each of them below, with the objects they name alongside it.
Distance is a picture
A message is a corner of a cube and an error is a step along an edge. Everything a code can do is decided by how far apart the corners it uses are — and that is a fact about a drawing.
![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.
A polynomial through the gaps
Write the message as the coefficients of a polynomial and send its values instead. Any k of them determine the polynomial, so it does not matter which ones are lost — and it does not matter how many, as long as k survive.
A page that knows where it is
A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.
The best a code can be
A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.
![How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked.](/f/how-many-codewords-lie-within-each-radius-for-a-7-3-code-e1fb4777.svg)
Past half the distance
A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.
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.
Orthogonal squares are a code
Write down each cell of a set of orthogonal Latin squares as a word — its row, its column, and its entry in each square — and no two words agree in more than one place. That is not a pleasant accident of the squares. It is exactly what being Latin and being orthogonal say, it makes the list an error-correcting code as good as any code of its size can be, and the squares a field builds turn out to be a Reed–Solomon code, the one on every compact disc.
The biggest box built from signs
Fill a square table with plus and minus ones and ask how large its determinant can be. The columns all have the same length, so the answer is a box with fixed edges — largest when every corner is square, which is possible only when the size is a multiple of four.
The longest code that survives every erasure
A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.
Ten digits need a symmetry that does not commute
A check digit should catch one wrong digit and two neighbours swapped. Over eleven symbols a weighted sum does both; over the ten decimal digits no weighted sum can, no scheme of any shape built on adding modulo ten can, and the reason is the same as the reason Euler's thirty-six officers cannot be paraded. What works is the ten symmetries of a pentagon, which do not commute.
A code built from an icosahedron
Write down which corners of an icosahedron are not joined by an edge, put the table beside a diagonal of ones, and add the twelve rows together in every combination. The 4,096 strings of 24 bits that come out differ from each other in at least eight places, occur in only five weights, and — with one bit deleted — fill the space of 23-bit strings so exactly that every one of the 8,388,608 lies within three flips of exactly one of them. This is the Golay code, which carried Voyager's pictures home, and its words of weight eight cover every five of the twenty-four positions exactly once.
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.
Two lost bits
One congruence repairs any single lost bit, and the set of words it defines is believed to be the best possible. Two lost bits defeat it. An exhaustive search finds the largest codes that survive two — 2, 2, 4, 5, 7 and 11 words for lengths 4 to 9 — and Helberg's congruence, with weights that grow like Fibonacci numbers, gives a code that provably works at every length but spends a fixed share of every bit on protection. The best codes need only about four times the logarithm of the length.
How few distances fix a word
An unknown word of a thousand bits can be read one bit at a time with a thousand questions. Ask instead for its distance from a chosen word, and each answer is worth about half of log₂ n bits, so roughly two hundred distances fix it. A balance reading many coins at once is the same question. So is Mastermind, in which Knuth's rule finds any of the 1,296 codes in at most five guesses and a mean of 4.476, and no first guess is best on both counts.
Two shares know nothing
Hide a number as the constant term of a quadratic modulo a prime and give eight people one value each. Any three can recover it. Any two know exactly nothing: of the 2,197 quadratics modulo 13, those matching two shares split into exactly one for each possible secret. Over the whole numbers the same two shares already give away the secret's parity.
Parallel planes take a vote
Draw a four-dimensional space with two values to a coordinate as a 4 × 4 grid, and mark its hyperplanes: thirty-two patterns any two of which differ on eight of sixteen squares. A polynomial's top coefficient can be read off any plane, and parallel planes do not overlap, so an error spoils only one vote. One of them flew to Mars, and in 2016 it turned out to reach Shannon's limit.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchHamming distanceFinite fieldHamming codeBoundChannel capacityErasureMinimum distanceModular arithmeticPerfect codePolynomialRedundancy