Distance is a picture

A string of three bits has eight possible values, and they are the corners of a cube.

That drawing is not an analogy or an aid. It is the object, and every question about correcting errors is a question about the positions of some dots on it.

Bits, as geometry #

Write the eight three-bit strings at the corners of a cube so that neighbours differ in one bit. This is possible, and in exactly one way up to relabelling: the corner $b_1b_2b_3$ goes at coordinates $(b_1, b_2, b_3)$, and two corners share an edge precisely when they differ in a single coordinate.

The same works in any number of dimensions. The $2^n$ strings of $n$ bits are the corners of an $n$-dimensional cube; there is no fourth perpendicular direction to draw, so a four-dimensional cube is drawn as two three-dimensional ones joined corner to corner, which is the honest picture rather than a perspective trick.

Define the Hamming distance between two strings as the number of places where they differ. Then:

• distance $1$ means adjacent — one edge apart;
• distance $k$ means $k$ edges apart, by any shortest path along the cube;
• the distance is a genuine metric, satisfying the triangle inequality, because a path from $a$ to $c$ through $b$ cannot be shorter than the direct route.

That last point is what makes everything else work. Distance on the cube behaves like distance, so the words “ball”, “sphere” and “nearest” all mean what they usually mean.

The cube has been here before #

This is the third time in the collection that the same cube has turned up carrying a different subject, and the repetition is worth noticing rather than passing over.

In logic it is the set of assignments to a formula: each corner is a way of setting the variables true or false, and a formula is the set of corners where it holds. Adjacent corners differ in one variable, which is why the geometry answers the question “what if this one changed?”.

In the simplification of Boolean expressions it is the map that puts neighbours side by side, where the whole trick is an ordering of the rows in which consecutive entries differ in exactly one place — a walk along the edges of the cube visiting every corner once.

Here it is the set of possible messages, and adjacency is a single transmission error. The three subjects share no vocabulary and no motivation, and they share an object exactly: the $n$-cube with its edge relation. Anything true of the cube is available to all three, which is why “the balls do not overlap” can be a statement about a communication channel.

Errors are edges #

A transmission flips some bits. Flipping one bit moves the string one step along an edge; flipping $k$ bits moves it $k$ steps.

So a channel that corrupts at most one bit per word takes each corner to itself or to one of its $n$ neighbours — that is, into the ball of radius one around it, which has $1 + n$ corners in it.

This is the whole model, and its bluntness is deliberate. Nothing here says how likely an error is or which bit is more fragile; the question is only what can be recovered in the worst case, and the answer turns out to depend on nothing but the geometry.

What a code is #

A code is a chosen subset of the corners. Words in the subset are legal; everything else is not.

If the balls of radius one around the chosen corners do not overlap, then a received word lies in at most one ball, and the codeword at its centre is the only legal word within one error. Correction is then unambiguous, and it is performed by looking for the nearest codeword.

If the chosen corners are merely not adjacent — no two of them one edge apart — then a single error always lands on an illegal word, so the error is noticed even if it cannot be fixed.

Both conditions are statements about the minimum distance $d$ between two codewords:

• detect up to $d-1$ errors;
• correct up to $\lfloor (d-1)/2 \rfloor$ errors.

The figure at the top of this page shows the smallest interesting case. Two codewords, $000$ and $111$, at opposite corners of the cube, at distance $3$. The balls of radius one around them hold four corners each; four plus four is eight; there are eight corners. They tile the cube exactly.

Correction, performed rather than asserted #

The claim “this code corrects one error” is checkable and the figure checks it, because a claim about a code is the kind of claim that can quietly be wrong.

For every codeword and every position, the generator flips that bit, searches all codewords for the nearest one, and requires both that the nearest is unique and that it is the codeword the corruption started from. For the three-bit repetition code that is eight tests; for larger codes it is more, and it is always done.

That is worth insisting on because the alternative — computing $d$ and quoting the formula — would be a claim about the formula rather than about the code. The formula is right; a figure that asserted it would be asserting arithmetic it had not performed.

Cheap detection, expensive correction #

Two families make the trade-off visible.

The parity code takes every string of even weight. No two such strings are adjacent, because flipping one bit changes the parity, so every single error lands outside the code and is detected. But the balls overlap heavily: the corner $001$ is one step from $000$, $011$ and $101$, three legal words at once, and there is no way to say which was sent.

That is the cheapest possible error control. It costs one bit out of $n$ — the rate is $(n-1)/n$, which tends to $1$ — and it buys detection and nothing else. It is the parity bit in a serial line, and its decimal cousin is the check digit on an account number, which is the same idea over ten symbols instead of two.

The decimal version is worth a moment, because it shows what changes when the alphabet is not binary. A check digit is a weighted sum of the digits, appended so that the total vanishes modulo something, and its whole job is to fail on the errors a person actually makes: one digit typed wrong, or two adjacent digits swapped.

Two properties decide everything, and neither is about codes. The modulus must be at least as large as the alphabet and share no factor with any weight, or some substitution changes the total by a multiple of it and is missed. And neighbouring positions must carry different weights, or a swap changes nothing at all.

The middle row is the interesting one. Alternating weights of $3$ and $1$ change the total by $2(d_{i+1}-d_i)$ under a swap, which vanishes modulo $10$ exactly when the two digits differ by five — so the scheme used on every barcode in the world misses precisely the swaps $0↔5$, $1↔6$, $2↔7$, $3↔8$ and $4↔9$. A prime modulus has no such gap, because a prime divides a product only by dividing a factor, and neither factor here is large enough. That is the no-zero-divisors property doing its usual work, in the humblest application it has.

The parity of a string is worth a moment’s attention on its own account. It is the sum of the bits modulo two, and adding a bit that makes the total even is exactly forcing the sum to zero in the two-element field. That one sentence is the seed of everything in the next three essays: a code will turn out to be the set of solutions of a system of linear equations over that field, and its whole behaviour will follow from the algebra of the system.

The repetition code sends each bit several times. Its distance is the length, so it corrects plenty, and its rate is $1/n$, which is dreadful. Sending a bit five times to correct two errors means spending five bits to carry one.

Between those two extremes is the entire subject. The question is how much distance can be bought for how little rate, and the geometry answers it.

That last figure is the correction rule failing, drawn. At radius $2$ the balls swallow the entire cube and share six corners, and a word in the overlap is exactly as far from both codewords. Nothing decides between them, which is why the correcting power stops at one.

How much room there is #

Since correction means non-overlapping balls, and the balls all have the same size, there is an immediate limit: the number of codewords times the size of a ball cannot exceed the number of corners.

The size of a ball is worth writing down, because it is where the rest of the arithmetic comes from. A word at distance exactly $j$ from a given one is a choice of which $j$ positions to flip, so there are $\binom{n}{j}$ of them, and the ball of radius $t$ holds

$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{t}$$

words. Those are rows of Pascal’s triangle, partially summed, and the whole theory of how much room a code has is a statement about partial sums of binomial coefficients.

That is the sphere-packing bound, and it is nothing more than counting corners. What is striking is how rarely the division comes out exactly. At distance $3$ the ball holds $n+1$ words, and $2^n/(n+1)$ is a power of two only when $n+1$ is — at $n = 3, 7, 15, 31$ and so on.

Those are the lengths where a code could conceivably use every corner with nothing left over. Such a code is called perfect, and whether one exists at each of those lengths is the subject of the next essay.

The distance-$5$ table is a useful corrective. Exactness in the bound is necessary for perfection and nowhere near sufficient for usefulness: the one exact row in range is $n=5$, whose perfect code is the five-fold repetition code with two codewords and a rate of one fifth.

The bound is a ceiling and not a promise #

Two directions have to be kept apart here, and conflating them is the standard mistake.

The sphere-packing bound says a code cannot have more codewords than the corners allow. That is a genuine impossibility, proved by counting, and it holds for every code whether or not anybody has thought of it.

It does not say that a code achieving the bound exists. Most of the time none does, and the interesting question in coding theory is the gap between what the counting permits and what can actually be built. The bound is a ceiling with nobody standing on it.

There is a matching statement in the other direction — the Gilbert–Varshamov bound, which says a code of a certain size must exist because a greedy construction cannot get stuck before reaching it: keep choosing corners at distance $d$ or more from everything chosen so far, and each choice forbids only the ball of radius $d-1$ around it, so the process runs until the forbidden balls cover everything. That is an existence proof by exhaustion of room rather than by construction, and it is exactly the counting argument that runs the probabilistic method in Ramsey theory.

Between the two bounds sits a gap that has been open, at most lengths, since the 1950s. What lies in it is the actual subject, and everything on this page is the frame around it.

Where the picture stops helping #

The cube is drawable at three dimensions, awkward at four and impossible after that. Real codes live at $n = 7$, $n = 255$, $n = 4096$.

What survives the loss of the picture is every word in it. Distance, balls, overlap, packing and covering all remain exactly what they were, defined combinatorially and behaving as the drawing suggests, because Hamming distance is a metric and metric arguments do not care about being visualised.

So the figures on this page do two jobs. They establish the vocabulary on a case small enough to check by eye, and they carry the one claim that is genuinely verified — that corrupting each codeword in each position and decoding to the nearest returns the original — on codes small enough for the verification to be exhaustive.

What they cannot show is a code at a useful size. The [7,4] code of the next essay has one hundred and twenty-eight corners, and by then the drawing has to become a table. That is a change of medium and not a change of subject: the table’s rows are corners, and the argument is still about how far apart they are.

Rate, and what it is a rate of #

One quantity has been used loosely above and deserves a definition, because it is half of every trade-off in the subject.

A code with $M$ codewords of length $n$ carries $\log_2 M$ bits of message in $n$ bits of transmission, so its rate is $\frac{\log_2 M}{n}$. The parity code has $M = 2^{n-1}$ and rate $\frac{n-1}{n}$. The repetition code has $M = 2$ and rate $\frac1n$. A code with rate $1$ has no redundancy and no protection.

The two quantities pull against each other and the pull is not symmetrical. Doubling the length of a repetition code doubles its distance and halves its rate — a straight trade. The good codes do much better than that, and the reason is the one the packing picture makes obvious: distance is about pairs of codewords, and adding a dimension roughly doubles the room available while adding only one to the length.

Whether the trade can be made arbitrarily favourable is the founding question of information theory, and the answer is yes, up to a limit that depends on how noisy the channel is. That limit is a statement about the channel and not about any particular code, and it is why a subject that begins with a cube ends somewhere else entirely. Nothing on this page reaches it; everything on this page is what the reaching is done with.

Why this is a geometry and not a coincidence #

It is worth stepping back to notice what has happened, because it is the same move this collection keeps finding.

The problem was about communication — bits arriving wrong, and how to notice. Nothing in the statement mentions space, distance or shape. And yet by writing the strings as coordinates, the problem became a packing problem: put as many non-overlapping balls into a cube as will fit.

Packing spheres into a space is a subject with its own long history and it is genuinely the same subject here, down to the vocabulary. The bound above is called sphere-packing because it is; and the reason the pigeonhole principle keeps appearing in this field is that a bound on how many balls fit is a bound on how many pigeons there is room for.

Hamming’s own account of arriving at this was that he was tired of a machine dropping his weekend jobs on a parity error, and that the geometry occurred to him afterwards as a way to see what the codes he was inventing had in common. The picture came second and made everything else easy, which is the ordinary order of events and not the one textbooks suggest.

Where this ladder goes #

The next rung takes the one length where the arithmetic is exact and asks whether a code actually achieves it. It does: sixteen codewords of length seven, each surrounded by a ball of eight, filling all one hundred and twenty-eight words with nothing left over.

After that, the mechanism — three parity checks whose result names the broken bit without recovering the message — and then a different construction entirely, in which the codeword is a polynomial’s values and the errors are allowed to be erasures rather than flips.