Matpic
mathematics, in pictures
Concept

Hamming distance

The number of places in which two strings of the same length disagree. It is city-block distance restricted to the corners of a cube, and it is what decides how many errors a code can survive.

Named by 11 essays across 5 fields — each of them below, with the objects they name alongside it.

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.

computation · Error-correcting codes 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 A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

discrete · Hamiltonian cycles The unit ball at p = 2.00. The set of points one unit from the origin, when distance is measured by the p-th power sum. At p = 1 it is a diamond, at p = 2 a circle, and as p grows it fills out a square.

Circles that are diamonds and squares

The theorem hands over a formula for distance. Take the formula as a definition, change the exponent in it, and the set of points one unit from the origin stops being round — while remaining, in every sense that matters, a circle.

geometry · Pythagoras 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.

computation · Error-correcting codes 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.

computation · Error-correcting codes The nearest consistent verdict: a 3-way tie at distance 4. A table of the 4 consistent judgement sets on the agenda p, q, and p and q, each with its number of disagreements with each of 3 judges and the total; the smallest total is marked.

The nearest consistent verdict

When a court's majorities contradict each other, one repair is to announce the consistent verdict that disagrees with the judges least. It treats the premises and the conclusion alike, which neither of the two standard procedures does. On the classic case it returns a three-way tie; on five judges, with every question weighted equally, it never returns a single answer on a troubled profile at all — and what breaks the tie is a decision about which question matters more.

applied · Judgement aggregation 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 The 1,344 tours of the 4-cube, by how often each place changes. A bar for each pattern of change counts among all closed walks through the 4-cube, with the number of tours having it; the reflected code's pattern and the perfectly even one are marked.

Every place changes back

A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.

discrete · Hamiltonian cycles 3 orthogonal squares of order 4, read as a code. A table of 16 words of length 5 over 4 symbols, one per cell of 3 orthogonal Latin squares of order 4: row, column and the entry in each square. Any two words agree in at most one position.

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.

computation · Latin squares A random walk across the regions to the one that satisfies every clause. Four overlapping ellipses with a dot in each of their sixteen regions, one marked as the only assignment satisfying the clauses, and a path of arrows from a random starting region to it, each arrow crossing one ellipse.

A walk that beats trying everything

To decide whether clauses of three letters can all be satisfied, the obvious method tries all 2ⁿ assignments. Uwe Schöning's method, from 1999, starts at a random assignment and wanders: pick a clause that is false, flip one of its letters at random, and repeat three times as many times as there are letters. A single try usually fails, but it succeeds with chance at least about (3/4)ⁿ, so about (4/3)ⁿ tries are enough — and the reason is a walk on a line that goes the wrong way two times in three.

logic · Class diagrams

Named alongside it

The objects these essays reach for when they reach for this one.

Error-correcting codeCounting argumentHypercubeExhaustive searchParityBinaryBoundGray codeHamming codeMinimum distancePerfect codeSphere-packing bound

All concepts