A polynomial through the gaps

Two points determine a line. Three determine a parabola. That fact, taken seriously and done over a finite alphabet, is a code.

The construction #

Fix a finite field — here the integers modulo $11$, which is a field because $11$ is prime, so every non-zero remainder has a reciprocal.

Take the message to be $k$ symbols from that field, and read them as the coefficients of a polynomial $f$ of degree less than $k$. Choose $n$ distinct points of the field, with $n > k$, and send the values

$$f(x_1),\ f(x_2),\ \dots,\ f(x_n).$$

That is the whole encoder. The figure above does it with $k=3$, $n=7$ and $p=11$: the message $4, 1, 3$ becomes $3x^2 + x + 4$, and the seven values sent are $4, 8, 7, 1, 1, 7, 8$.

Why any $k$ of them are enough #

A polynomial of degree less than $k$ is determined by its values at any $k$ distinct points. There are two ways to see it and both matter.

By interpolation. Lagrange’s formula writes the polynomial down explicitly from $k$ points, as a sum of $k$ terms each of which is $1$ at one point and $0$ at the others. Every step is field arithmetic — subtractions and one division — so the formula works over the integers mod $11$ exactly as it does over the reals.

By counting roots. If two polynomials of degree less than $k$ agreed at $k$ points, their difference would be a polynomial of degree less than $k$ with $k$ roots, and a non-zero polynomial cannot have more roots than its degree. So the difference is zero.

The second argument is the one that generalises, and it is worth noticing that it needs the alphabet to be a field. Over the integers modulo $8$ — not a field, because $2$ times $4$ leaves no remainder — the polynomial $2x$ has two roots, $0$ and $4$, and the whole argument collapses. That is the reason a finite field is required rather than merely a finite set with arithmetic on it.

Erasures, which are the easy failure #

The channel model changes here, and the change is what makes the code so clean.

A flip turns a symbol into a different symbol without saying so. An erasure removes a symbol and says which one is missing — a disc sector that fails to read, a packet that never arrives, a scratch whose position is known.

Erasures are much easier, because the positions of the survivors are known and any $k$ of them suffice.

The two figures make the point that no single one could. It is not that this code tolerates these four erasures; it tolerates any four, and the figures show two disjoint choices working identically. The generator checks all $\binom{7}{3} = 35$ ways of choosing which three survive, on every placement, and requires the recovered coefficients to be the ones sent.

Where the boundary is #

One symbol fewer and everything stops, which is worth showing because a boundary that is not exhibited is a boundary the reader has to take on trust.

With only $k-1$ survivors, the number of messages consistent with them is exactly $p$ — one for each value the missing constraint could take. The figures compute that count directly by trying all $p^k$ possible messages and keeping the ones that agree with the survivors, and the answer is $11$.

So the code is not merely good at $n-k$ erasures; it is precisely at the edge. Recovery is certain up to $n-k$ losses and impossible at $n-k+1$, with no grey region between.

Interpolation, done exactly #

It is worth watching one recovery in full, because “interpolate” is a word that hides whether anything difficult is happening, and here nothing is.

Suppose the surviving points are $(0,4)$, $(2,7)$ and $(4,1)$, over the integers mod $11$. Lagrange’s basis polynomial for the first point is

$$\ell_0(x) = \frac{(x-2)(x-4)}{(0-2)(0-4)} = \frac{(x-2)(x-4)}{8},$$

and dividing by $8$ mod $11$ means multiplying by the reciprocal of $8$, which is $7$ because $8 \times 7 = 56 = 55 + 1$. So the division is a multiplication and there is no rounding anywhere.

Building all three basis polynomials, scaling each by its point’s value and adding gives $3x^2 + x + 4$, which is the message. Every operation was an addition, a multiplication or a lookup of a reciprocal in a table of ten entries.

That exactness is the difference between this and interpolation over the real numbers, where fitting a high-degree polynomial to data is famously unstable and small changes in the values move the curve wildly. There is no stability question here because there is no notion of small. Two field elements are equal or they are not, and the recovered polynomial is right or it is not.

Distance, measured over every codeword #

For flips rather than erasures the relevant quantity is the minimum distance, and it can be read off the same root-counting argument.

A non-zero message gives a non-zero polynomial of degree less than $k$, which has at most $k-1$ roots, so at most $k-1$ of the $n$ transmitted values are zero and at least $n-k+1$ are not. Since the code is linear, that minimum weight is the minimum distance.

The Singleton bound says no code can do better: a code of length $n$ with $M$ codewords and distance $d$ satisfies $M \le q^{\,n-d+1}$, because deleting $d-1$ symbols from every codeword must still leave them all distinct, and there are only $q^{\,n-d+1}$ shortened words to be distinct in.

Codes meeting it are called maximum distance separable, and they are rare. These are them. The distance is $n-k+1$ exactly, at every length and every dimension, over any field big enough to supply $n$ distinct points.

The bound’s proof is worth one more look because it is a clean piece of counting of the kind this collection keeps returning to. Delete the first $d-1$ symbols from every codeword. Two codewords that agreed on everything remaining would differ in at most $d-1$ places, contradicting the minimum distance — so the shortened words are still all distinct. There are $q^{\,n-d+1}$ possible shortened words, so there were at most that many codewords to begin with. No construction, no algebra, and it applies to every code there is.

What that costs #

Nothing is free, and the cost here is the alphabet.

The construction needs $n$ distinct evaluation points, so $n \le q$: the codeword cannot be longer than the field. Correcting a lot of errors in a long message therefore means a large field, and a large field means symbols carrying many bits each.

In practice the field is $GF(256)$ and a symbol is a byte. The standard code on a compact disc is $[32, 28]$ over that field; the one on a QR code is $[255, k]$ with $k$ chosen by the error-correction level; the one on the Voyager missions after Jupiter was $[255, 223]$, correcting sixteen bad bytes in every two hundred and fifty-five.

That byte-sized alphabet is also the answer to the burst problem of the previous rung. Eight consecutive bad bits inside one byte are one wrong symbol, not eight wrong bits, so a code that corrects sixteen symbol errors survives a scratch a hundred and twenty-eight bits long. Choosing the alphabet to match the shape of the damage is most of the engineering.

For flips the accounting differs from erasures by exactly a factor of two, and the reason is worth stating.

An erasure is a known position and an unknown value: one unknown. A flip is an unknown position and an unknown value: two unknowns. So $n-k$ redundant symbols buy $n-k$ erasures or $\lfloor (n-k)/2 \rfloor$ flips, and a decoder can trade between them — correcting $e$ erasures and $t$ flips whenever $2t + e \le n-k$.

That relationship is why systems that can detect where the damage is do so. A disc controller knows which sector failed; a packet network knows which packet is missing. Turning a flip into an erasure by other means doubles the value of the same redundancy, and it is often much cheaper than adding redundancy.

Finding the errors, which is the hard half #

Everything above about flips has assumed that a decoder exists, and constructing one is a real piece of work that this essay is not going to do. It is worth saying what shape it has, because otherwise the code looks easier than it is.

With erasures the positions are given and interpolation finishes the job. With flips the decoder must find the positions, and the obvious method — try every set of $t$ positions, assume those are wrong, interpolate from the rest, and see whether the result is consistent — costs $\binom{n}{t}$ interpolations, which at $n=255$ and $t=16$ is a number with thirty digits.

The practical algorithms do something cleverer. They compute a small number of syndromes — exactly the idea of the previous rung, generalised to this field — and then solve for an error-locator polynomial whose roots are the bad positions. Berlekamp and Massey found how to do that solve efficiently in the 1960s, and Sugiyama and others later showed it is Euclid’s algorithm on polynomials in disguise.

The relevant point for this page is that the syndrome trick survives the change of alphabet unchanged. A linear code’s check depends on the error and not on the message, whatever the field, so the decoder can work on the damage alone. What becomes harder is only the step of turning that damage into positions.

The same picture, used to keep a secret #

The construction has a second life that is worth knowing, because it is the identical mathematics read with the roles swapped.

Take a secret $s$ and make it the constant term of a random polynomial of degree $k-1$ over a large field. Hand out $n$ values of that polynomial to $n$ people. Then any $k$ of them can reconstruct the polynomial and read off $s$; and any $k-1$ of them learn nothing at all, because for every candidate secret there is exactly one polynomial through their points with that constant term — the same count of $p$ possibilities that appeared above as a failure of decoding.

That is Shamir’s secret sharing, published in 1979, and it is the same object as the code wearing a different hat — the kind of double life this collection collects. The fact that the failure mode of the code is the security property of the scheme is not a coincidence. Both are the statement that $k-1$ points determine nothing about a degree-$(k-1)$ polynomial’s remaining freedom.

What the picture cannot show #

The figures here draw the polynomial’s values as dots on a grid, and the grid is a genuine picture of the field — but it is a picture of a set, not of a line.

Over the real numbers a polynomial is a curve and interpolation is visibly a matter of a curve passing through points. Over $GF(11)$ there is no curve. The points do not lie on anything, there is no notion of between, and the dots in the first figure form no pattern the eye can complete. Everything that makes interpolation feel inevitable in the real case — smoothness, continuity, a Taylor series’s promise that local information determines the whole — is absent.

What survives is the algebra, and only the algebra: a system of $k$ linear equations in $k$ unknowns whose matrix is invertible because the evaluation points are distinct. The figures therefore verify by computation rather than by appearance, interpolating all thirty-five subsets rather than showing a curve and inviting the reader to believe it.

That gap is worth naming because it is the general condition of this field. A finite structure can be drawn, and the drawing is honest about what is there; what it cannot do is make the argument feel forced, because the intuitions that would do the forcing come from a continuous world this one has left.

Why this construction and not a cleverer one #

There is something worth pausing on in how little the code does.

The Hamming code of the previous rungs is a design: three parity checks arranged so that their columns are the seven non-zero patterns, chosen to make the syndrome name a position. Change the arrangement and the code gets worse. It is an optimisation of a specific size.

This one is not designed at all. It is one sentence of algebra — a polynomial of low degree is determined by enough of its values — and every property follows without any choices being made. The distance is optimal at every length. The erasure tolerance is optimal at every length. The evaluation points can be any distinct elements, in any order.

That is unusual and it is why Reed–Solomon codes are everywhere. A construction with no parameters to tune has no way to be tuned badly, and a construction whose correctness is one root-counting argument has very little that can be got wrong. The engineering effort in a real deployment goes into the decoder and into the choice of field, never into the code.

The contrast with the classical constructions of the first anchor of this field is instructive. There, an operation set was fixed and the question was what could be reached. Here the reachable object was specified first — a set of $n$-tuples pairwise far apart — and the arithmetic was chosen to make it exist. Both are questions about what a fixed set of rules produces; the difference is which end was pinned down.

Where this ladder ends #

Four rungs: distance as a geometry, a perfect packing, a decoder that ignores the message, and a construction that meets the best possible bound at every size.

What every one of them needed was an arithmetic that closes — addition, multiplication and division on a finite set, with no exceptions and no zero divisors. That object was used freely here and never examined. The next anchor examines it: which finite sets support such an arithmetic, why the answer is the prime powers and nothing else, and why the field with four elements is not the integers modulo four.