Sixteen spheres that fill a cube

Counting corners gives a ceiling on how many codewords there is room for. Almost nothing reaches it. One thing does, at length seven, and it does so exactly.

The arithmetic that has to work first #

A code correcting one error needs the balls of radius one around its codewords to be disjoint. In the $n$-cube such a ball holds $1 + n$ words. So $M$ codewords need $M(1+n)$ words of room, and there are $2^n$ words altogether:

$$M \le \frac{2^n}{n+1}.$$

For that to be attained the division must come out as a whole number, and — since $M$ has to be a power of two for a linear code — as a power of two. That happens when $n+1$ is a power of two, so at $n = 3, 7, 15, 31, \ldots$.

At $n=3$ the answer is $M = 2$, which is the repetition code from the previous essay — perfect, and useless, since two codewords carry one bit.

That the ball has $n+1$ words in it, and not some more complicated number, is the reason the condition is as clean as it is. A ball of radius one is the centre plus the $n$ words one flip away, and the binomial coefficients that appear at larger radii have not started yet.

At $n=7$ the answer is $M = 16$, which carries four bits in seven. That is a rate of $4/7$, a genuine code rather than a curiosity, and the question is whether sixteen corners of the seven-cube can actually be found sitting at distance three from one another.

The construction #

They can, and the construction is four data bits with three parity bits computed from them.

Let the data be $d_1 d_2 d_3 d_4$ and set

$$p_1 = d_1 + d_2 + d_3,\qquad p_2 = d_2 + d_3 + d_4,\qquad p_3 = d_1 + d_2 + d_4,$$

all sums taken modulo two. The codeword is $d_1 d_2 d_3 d_4 p_1 p_2 p_3$.

Sixteen data patterns give sixteen codewords, listed in the figure at the top of this page with their weights. The choice of which data bits each parity bit watches is a choice, and it is the only choice in the whole construction; what makes it the right one is checked below rather than argued for.

Why the choice of parity checks is the whole design #

Three parity bits watching four data bits could be arranged in many ways, and most arrangements give a worse code. It is worth seeing what separates the good arrangement from the bad ones, because the answer is a single sentence and it is the reason the next essay works.

Write the three equations as a matrix over the two-element field, with one column per position, and read off the columns. Position $1$ enters checks $1$ and $3$, so its column is $101$. Position $2$ enters all three, giving $111$. Position $5$ is the first parity bit and enters only its own check, giving $100$. Running through all seven positions produces the seven columns

$$101,\quad 111,\quad 110,\quad 011,\quad 100,\quad 010,\quad 001,$$

which are the seven non-zero three-bit patterns, each appearing exactly once.

That is the design condition, and everything follows from it. A code has distance at least three exactly when no two columns are equal and no column is zero — because a codeword of weight one or two would be a column, or a sum of two columns, coming out zero. With three check bits there are $2^3 - 1 = 7$ non-zero patterns available, so seven is the longest such code, and it uses every pattern.

Length seven is therefore not a lucky number. It is $2^3-1$, and the same argument gives $2^r-1$ for $r$ check bits: fifteen with four, thirty-one with five. The perfection and the length come from the same count, which is why the bound is met rather than approached.

Distance three, measured twice #

The minimum distance is computed in the figure over all $\binom{16}{2} = 120$ pairs, and it comes out as $3$.

It is also computed a second way. The code is linear — the sum of two codewords is a codeword, since the parity equations are linear — and for a linear code the minimum distance equals the minimum weight of a non-zero codeword. That is because the distance between $u$ and $v$ is the weight of $u+v$, which is itself a codeword.

So one hundred and twenty pairwise comparisons and fifteen weight counts are two routes to the same number, and the figure asserts that they agree. Either alone would be a claim about itself.

The weight distribution is worth reading: one word of weight $0$, seven of weight $3$, seven of weight $4$, one of weight $7$. It is symmetric, which is not an accident — adding the all-ones word to a codeword gives a codeword, and that pairing swaps weight $w$ with weight $7-w$.

The packing, performed #

Now the claim this essay is named for.

Around each of the sixteen codewords, the ball of radius one holds $1 + 7 = 8$ words: the codeword and the seven words one flip away. Sixteen balls of eight is one hundred and twenty-eight, which is the number of seven-bit words there are.

That the arithmetic works does not mean the balls do not overlap. So the figure does not compute $16 \times 8$; it assigns every one of the one hundred and twenty-eight words to a ball and counts.

The partition is drawn there in its other and slightly better form. The whole space splits into eight classes, one per possible outcome of the three parity checks, each containing sixteen words. Within each class there is exactly one word of least weight, and its weight is at most one.

Those eight lightest words are the zero word and the seven single-bit errors. That is precisely the statement that every word in the space is either a codeword or one flip from exactly one codeword — which is what perfection means, arrived at by partitioning rather than by multiplying.

Perfect, and what it costs #

The code is optimal in the strongest available sense: no code of length seven correcting one error can have seventeen codewords, because there is no room, and this one has sixteen.

That optimality has a price, and the price is that there is no slack anywhere. Every word in the space is claimed by some codeword. A word with two errors in it does not look like a word with two errors; it looks like a perfectly ordinary word one flip from a different codeword, and the decoder confidently repairs it into the wrong message.

So a perfect code cannot detect what it cannot correct. The parity code of the previous essay detects one error and corrects none, and is honest about failing. This code corrects one error and is silent about two.

The usual repair is to append one more parity bit over the whole word, giving the extended $[8,4]$ code with distance $4$. It corrects one error and detects two, at the cost of one bit and of perfection — the balls no longer tile, and the words left over are exactly the ones the decoder now refuses rather than mangles.

That trade is a real design decision and not a technicality. A channel where two errors are rare wants the perfect code; a channel where a wrong answer is worse than no answer wants the extended one.

What the design costs to build #

It is worth noticing how little machinery the construction needs, because it explains why this code is in hardware everywhere.

Encoding is three exclusive-ors. Checking is three more. Neither operation needs a table, a search, or memory of anything beyond the seven bits in hand. The whole of the arithmetic is in the two-element field, where addition is the exclusive-or gate and multiplication is the and gate — which is why a code is the natural thing for a circuit to compute and a decimal check digit is not.

Memory modules have used the extended $[8,4]$ version and its larger relatives since the 1970s, under the name SECDED — single error correct, double error detect. A stick of server memory runs a Hamming-style code across every word it stores, corrects the single-bit upsets that cosmic rays and marginal cells produce, and reports the double ones. The design is Hamming’s from 1950, unmodified in any essential way, and the reason it has not been improved on at that size is that at length seven there is provably nothing better.

How many perfect codes there are #

The natural next question is which other lengths work, and the answer is one of the more satisfying classification theorems in the subject.

The arithmetic permits perfection at $n = 3, 7, 15, 31, 63, \ldots$ for one error, and at scattered lengths for more. The Hamming construction generalises: for every $r$, there is a code of length $2^r - 1$ with $2^r - 1 - r$ data bits correcting one error, perfectly. So the one-error case is settled and the answer is “all of them”.

For more than one error, almost everything fails.

The one exception is remarkable enough to have its own name. At $n = 23$, a ball of radius three holds

$$1 + 23 + 253 + 1771 = 2048 = 2^{11}$$

words, and $2^{23}/2^{11} = 2^{12}$. The arithmetic permits a code with $4096$ codewords of length $23$ correcting three errors, and such a code exists: the binary Golay code, published by Marcel Golay in 1949 in a paper of half a page.

And that is all. A theorem of Tietäväinen and van Lint, completed in 1973, says the perfect binary codes are exactly: the trivial ones, the repetition codes of odd length, the Hamming codes, and the Golay code. Nothing else, at any length, for any number of errors.

Where the arithmetic lies #

The classification has a moral, and it is one this collection keeps meeting: a count that comes out right is not an object.

The clean case is length $90$. A ball of radius two in the $90$-cube holds

$$1 + 90 + 4005 = 4096 = 2^{12}$$

words, and $2^{90}/2^{12} = 2^{78}$ — as exact as any division in this essay. Every necessary condition is met. There is no such code, and the proof that there is not is a genuinely hard argument rather than an oversight.

So the tables in these figures answer a smaller question than they appear to. “Is a perfect code arithmetically possible at this length?” is decided by counting corners, which is what the figures do. “Does one exist?” is a different question with a different and much harder answer, and the two coincide far less often than the length-seven case suggests.

This is exactly the discipline the counting arguments elsewhere in this collection demand. Counting the same thing two ways proves an identity; counting the room something would need proves only that it might fit.

The same gap appears in every subject where a necessary condition is cheap and existence is expensive. Which numbers of points admit a schedule where every pair meets once has a divisibility test that is necessary and — unusually — turns out to be sufficient too, which is the happy case. Which orders admit a pair of orthogonal Latin squares has a necessary condition that Euler believed sufficient and that is not, and the exception took a hundred and seventy years to find. Perfect codes sit at the same crossroads, and length ninety is where the arithmetic’s promise is broken.

There is no general lesson beyond the obvious one, which is that a table of exact divisions is a table of candidates. Nothing in this essay’s figures would look any different if the length-seven code did not exist. What makes it exist is the construction, and what makes the construction correct is the partition the second figure performs.

Two ways of saying the same thing #

The packing statement and the class statement are worth holding side by side, because they are the same fact and the second one generalises.

As a packing: the sixteen balls of radius one are disjoint and cover everything.

As a partition: the code is a subgroup of the group of all seven-bit words under bitwise addition, its cosets are the sixteen-word classes in the figure above, and each coset contains exactly one word of weight at most one.

The second version is better for two reasons. It makes the sixteen-ness obvious — every coset of a subgroup has the same size as the subgroup, which is Lagrange’s theorem doing the counting — and it says what decoding is: given a received word, identify its coset, subtract the coset’s lightest member, and the result is a codeword.

That reformulation is what turns a search over sixteen candidates into an arithmetic operation, and it is why the next rung can locate an error without ever listing a codeword. The subgroup structure is available because the code is linear, and the code is linear because parity is addition modulo two and nothing else.

The code that went to Jupiter #

One footnote, because the Golay code is not a curiosity.

The Voyager spacecraft used it for their images of Jupiter and Saturn: the $[24,12,8]$ extended Golay code, three errors corrected in every twenty-four bits, at a rate of one half. Later missions moved to the Reed–Solomon codes of the fourth rung of this ladder, which handle bursts better.

There is a pleasing sequence in that. A packing argument on a cube, a half-page paper in 1949, a classification theorem in 1973, and pictures of a planet — all of it turning on the fact that $1 + 23 + 253 + 1771$ happens to be $2048$.

Where this ladder goes #

The packing is established, and nothing so far explains how the correction is actually carried out. Finding the nearest of sixteen codewords by comparing against all sixteen is a possible procedure and a poor one.

The next rung shows what the three parity bits are really for. Running them on a received word produces three bits that are zero when nothing is wrong, and otherwise are the binary numeral of the position that broke — the error located directly, without any search and without recovering the message at all.