Past half the distance

Every account of error correction contains the same sentence: a code of minimum distance $d$ corrects $\lfloor (d-1)/2 \rfloor$ errors. The argument is one line — balls of that radius around the codewords do not overlap — and it is correct.

It is also an answer to a question nobody asked. That radius is the largest one at which the answer is unique, and uniqueness is a convenience. A decoder handed a corrupted message and returning two candidates has narrowed a thousand possibilities to two, and whether that is useful depends on what happens next, not on a theorem.

So the honest question is how many codewords lie within a given radius of a received word, and it can be answered by counting. That is a different question from the one the bounds on a code’s size answer, and it has a different shape of answer: not a single threshold but three regimes, with the famous one occupying only the first.

Three regimes, and only one of them is famous #

The bars in that figure fall into three groups, and the boundaries between them are the whole subject.

Up to half the minimum distance the list is at most one. That is the classical statement, and the search confirms it — no received word among the sample had two codewords within distance 2, and none could, because two such codewords would be at distance at most 4 from each other and the minimum distance is 5.

Past that radius the list is short. At radius 3 the largest list found is 5, out of 1331 codewords. A decoder returning those 5 has done something useful: it has corrected three errors where the classical bound permits two, at the cost of an ambiguity a checksum or a language model would resolve immediately.

And past a second radius the list stops being a list. At radius 5 the count is 187 and at radius 6 it is 650 — half the code. There is nothing to return.

The second boundary has a name and a formula. The Johnson radius is $n - \sqrt{n(n-d)}$, which for this code is 3.26: inside it the list is guaranteed to be short, and outside it there is no such guarantee. The figure’s three colours are those three regimes, and the middle one is the whole content of list decoding.

The word that cannot be decoded uniquely #

The claim that uniqueness stops at radius 2 is proved by exhibiting a received word with two codewords equally close, and the construction is short enough to follow.

Two things about that word are worth separating. It is not a case where the code has failed: the two codewords are 6 apart, comfortably more than the minimum distance, and the code is doing exactly what it was built to do. And the received word is not exotic — it is what arrives when three of seven symbols are corrupted, which is a perfectly ordinary amount of damage on a channel that damages anything.

It is worth comparing this with the case where the code genuinely runs out. The Hamming code’s balls tile the whole space, so every received word is within one step of exactly one codeword and there is nothing further to reach for; a perfect code has no list-decoding regime at all, because there is no room between the balls. The codes with room to spare are the ones list decoding is for, and Reed–Solomon has a great deal of it: 1331 codewords in a space of nineteen and a half million.

The failure is in the decoder’s contract, not in the code. A decoder promising one answer cannot keep the promise here. A decoder promising a short list keeps it easily: the list is two.

Why the code allows this at all #

The code in the figures is Reed–Solomon — the message is the coefficients of a polynomial and the transmitted word is its values — and its distance comes from a fact about polynomials rather than about strings.

The same fact says what a decoder is really doing. A received word is a set of $n$ points in the plane over the field, some of them on the true polynomial’s graph and some not. Decoding is fitting a curve of degree below $k$ through as many of the points as possible — and asking for a list rather than one answer is asking for every low-degree curve passing through enough of them.

Put that way the classical bound is visibly conservative. Two curves of degree below $k$ agree in at most $k - 1$ places, so two candidate curves each hitting more than $(n + k - 1)/2$ points are impossible — which is the unique-decoding radius. But a curve hitting rather fewer points than that is still a strong statement about the data, and there are not many such curves.

That contrast is the cleanest way to see where the factor of two comes from. An erasure tells the decoder where the damage is; an error does not, and the decoder spends half its distance budget finding out. List decoding is what happens when the decoder declines to spend all of it.

Where the second boundary comes from #

The Johnson radius looks like an arbitrary formula and is not. It is the radius at which a ball starts holding a definite share of the whole space, and the arithmetic that says so is short enough to do.

Count the words within distance $e$ of a fixed word, over an alphabet of $q$ letters and length $n$: choose which $i$ positions differ and what each becomes, giving $\binom{n}{i}(q-1)^i$ for each $i$ up to $e$. For this code at radius 3 that is $1 + 70 + 2100 + 35000 = 37171$ words, out of the nineteen and a half million in the whole space.

The code has 1331 words scattered through that space. If they were scattered at random, the expected number inside a ball of radius 3 would be 1331 times the ball’s share of the space, which comes to about 2.54.

The measured average is 2.52. So a Reed–Solomon code’s words are, for this purpose, indistinguishable from a random scattering — and the average list size at any radius is simply the ball’s share of the space multiplied by the number of codewords, which grows by a factor of about ten with each extra unit of radius here.

That accounts for the average and not for the maximum, and the difference between them is exactly what the Johnson radius measures. At radius 3 the average is 2.52 and the largest list found is 5 — the same order. At radius 5 the average is 170 and the largest is 187, again the same order, but both are now a seventh of the entire code. The radius at which the maximum is guaranteed to stay small, rather than merely being small on average, is where the guarantee stops, and $n - \sqrt{n(n-d)}$ is where the counting argument that provides the guarantee runs out.

A statement about averages is not a decoder. A decoder needs the worst case bounded, and the Johnson bound is the theorem that bounds it — which is why the radius is named after a bound rather than after the counting above.

Two curves through the same points #

The pair of codewords in the figure above deserves reading as polynomials rather than as strings, because the string version makes the coincidence look like luck.

A codeword is the list of values of a polynomial of degree at most 2 at the points $0$ through $6$. Two such polynomials differ by a third polynomial of degree at most 2, which has at most 2 roots — so two codewords agree in at most 2 places and differ in at least 5, which is the minimum distance arriving from the algebra rather than from a count.

The pair drawn differs in 6 places, so the two polynomials agree in exactly one. The received word takes its symbols from the first polynomial at 3 of the disputed places and from the second at the other 3, plus the one place they agree.

So the received seven points contain 4 lying on one parabola and 4 lying on another — the three taken from each, plus the shared one. Two curves of degree 2 each pass through 4 of the 7 points, and no rule of algebra prefers either. Fitting a curve through 3 points determines it; through 4 it is a genuine claim; and the claim is true twice.

That is the whole phenomenon, and it explains why the list is short rather than empty or enormous. A curve through 4 of 7 points is a real constraint, so there are not many; and 4 out of 7 is not a large enough majority to exclude a rival, so there can be more than one.

What a short list is worth #

A decoder returning two answers is only useful if something resolves them, and in practice something always does.

The commonest arrangement is a concatenated code: a Reed–Solomon code over bytes wrapping an inner code over bits, or wrapping a checksum. The outer layer receives a short list and rejects all but one of its members almost certainly, because a wrong candidate has to pass a check it was not built to pass. The cost is one checksum; the gain is the extra third of the error-correcting radius.

The second arrangement is context. A decoder for a stored message often knows something about what the message should look like — a file header, a language, a prior — and a list of two candidates is resolved by inspection. This is the situation for a barcode read at an angle, for a scratched disc, and for essentially every deep-space transmission, where the receiver knows the format exactly.

The third is that the list is often of length one anyway. The figures report the largest list over a sample; the average at radius 3 is 2.52, so a decoder working past the classical radius usually returns a single answer and occasionally returns a few. Uniqueness was never the guarantee; it was the typical case being mistaken for one, and the classical radius is the radius at which the typical case can be proved to be the only case.

The same shape at other parameters #

The three regimes are not an artefact of one code.

What has changed between the two figures is the rate. The second code carries 2 symbols in 6 rather than 3 in 7, and a lower rate buys a larger Johnson radius. That trade is the general statement: the fraction of errors a list decoder can handle is $1 - \sqrt{R}$ where $R$ is the rate, against $(1 - R)/2$ for unique decoding, and the first is larger than the second at every rate below one.

The gap is not small. At rate a quarter, unique decoding reaches 37% of the symbols and list decoding reaches 50%. A third of the code’s error-correcting power is thrown away by insisting on a single answer, and that was the situation for the first forty years of the subject.

What it took to make this a decoder #

Counting codewords in a ball establishes that a short list exists. It does not produce one, and the distance between those two statements is where the actual work is.

The count in these figures is over all 1331 codewords, which is possible because the code is tiny. A real Reed–Solomon code over a byte alphabet has $256^{200}$ codewords, and no decoder can look at them.

Sudan’s algorithm in 1997 and Guruswami and Sudan’s improvement in 1998 supplied the missing half, and the idea is worth stating because it is not a search at all. Fit a two-variable polynomial vanishing at all $n$ received points, with enough multiplicity; then factor it. Every low-degree curve through enough of the points appears as a factor, and factoring a polynomial is something that can be done in time polynomial in its degree. The list is not found by looking for it; it is found as the factors of one object built from the data, which is why the running time does not depend on the size of the list’s search space.

What the pictures cannot show #

The counts here are over sampled received words. The bar at each radius is the largest list found in 240 draws, which is a lower bound on the worst case rather than the worst case itself. That the worst case is also bounded — that no received word anywhere has a long list inside the Johnson radius — is a theorem, and it is the theorem that makes list decoding a guarantee rather than a hope.

Nothing here runs a list decoder. The algorithm is described and not drawn, because it is an interpolation in two variables followed by a factorisation, and neither step has a picture that would say more than the words do.

And the asymptotic claim — that $1 - \sqrt{R}$ is reachable and $(1 - R)/2$ is what uniqueness allows — is stated with two small codes as illustration. Two points do not establish a curve, and the curve here comes from the theory rather than from the figures.

Where the ladder goes next #

This rung closes the ladder: distance as a picture, a perfect code, its decoder, the polynomial construction, the bounds on what any code can do, and now the bound on what any decoder can do.

Named here as debts. The Guruswami–Sudan algorithm in detail, whose interpolation step is a linear system and whose factorisation step is the interesting one. And capacity, which is the statement that the whole trade-off has a limit set by the channel rather than by the code, and which belongs to information theory rather than to coding.

Sideways, the code being decoded is the polynomial through the gaps, the largest code at each length is the rung below, the decoder that names a single position is the syndrome, and the geometry that makes distance the only thing that matters is the cube.

The bound on the decoder, not the code #

One more comparison makes the shape of this rung clear against the one below it.

The rung below bounds how many words a code can hold, and the bounds there are about packing: how much of the space the code occupies. This rung bounds how far a decoder can see, and the bound is about covering: how much of the space a ball occupies. The two are the same arithmetic used in opposite directions, and they behave in opposite ways as the code’s rate changes.

A high-rate code packs the space tightly, which is what a designer wants and what makes decoding hard: the balls are small and everything is near several codewords. A low-rate code wastes space, which is what makes list decoding reach so far. So the quantity being traded is the same one in both rungs — how full the space is — and the difference between the classical radius and the Johnson radius is a measure of how much of the emptiness is being left unused.

Two bounds, one resource. That is the useful way to hold the pair, and it explains why the gain from list decoding is largest exactly where the classical radius is largest: at low rates, where there is most room.

What is worth carrying away #

A theorem’s constant is often the price of a requirement nobody examined, and the requirement here was that the answer be unique.

Half the minimum distance is exactly right for a decoder that must name one codeword. It is off by a factor approaching two for a decoder allowed to name a few, and the difference was available for forty years before anybody claimed it — not because the mathematics was hard, but because the question was posed with uniqueness built in.

The habit worth taking is to ask what a bound is a bound on. The classical radius bounds the region where a certain kind of answer exists, not the region where the information survives; and once the two are separated, the second turns out to reach much further.

The corollary is about how to spot the situation elsewhere. Whenever a procedure’s guarantee is stated in terms of a unique correct output, there is a version returning a small set, and the set version usually has a better constant. The cost is that something downstream has to break the tie — which is often free, because downstream usually knows something the decoder does not.