Error-correcting codes — the series

A code on the 3-cube, and the balls around its words. The corners of a hypercube with the chosen codewords marked and the words within one error of each shaded.

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.

part 1 · computation

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.

part 2 · computation

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.

part 3 · computation

A degree-2 polynomial over GF(11), and the 7 values sent. A grid of the finite field with the polynomial's value at each point marked, and the transmitted symbols picked out.

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.

part 4 · computation

The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds.

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.

part 5 · computation

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.

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.

part 6 · computation

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.

part 7 · computation

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.

part 8 · computation

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.

part 9 · computation

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.

part 10 · computation

Every swap-proof scrambling, graded on twins and jump swaps. 34040 permutations; twin errors caught range 50–86 of 90, jump transpositions 600–848 of 900; Verhoeff's at (848, 86).

The best of thirty-four thousand scramblings

Verhoeff's check digit multiplies digits in the symmetry group of a pentagon after scrambling each one a different number of times, and 34,040 scramblings make it catch every swap of neighbours. Graded on the rarer errors, none of them catches everything, the best catch 86 of 90 doubled-digit slips and 848 of 900 swaps across a digit — and the scrambling Verhoeff published in 1969 is one of the forty that are best at both.

part 11 · computation