Erasures a code can see

The capacity of a channel that flips bits is $1 - H(p)$, and reaching it took sixty years of work because the decoder has to discover where the damage is before repairing it. There is a channel that removes the first half of the problem. Each bit either arrives intact or arrives as a blank — a mark saying “this one was lost” — with probability $\varepsilon$. The receiver knows exactly which positions to reconstruct.

That is the erasure channel, introduced by Peter Elias in 1955, and it is not a toy. A packet dropped by a network, a disk in an array that has failed, a block of a file missing from a download: in each case the loss is known and the location is known. Erasures are the normal form of failure for anything stored or sent in pieces.

The capacity of the erasure channel is $1 - \varepsilon$, and the reason is almost too simple to state. A fraction $\varepsilon$ of the bits never arrive, so at most a fraction $1 - \varepsilon$ can carry message; and the surviving bits are exactly right, so nothing further needs to be spent on noise. At a loss of one bit in ten, the flipping channel carries 0.531 and the erasing channel 0.9. The gap between them is $H(p) - p$, the cost of not knowing where to look.

Message bits as unknowns #

A linear code over the two-symbol alphabet sends each transmitted bit as a fixed sum, modulo 2, of some of the message bits. With $k$ message bits and $n$ transmitted, such a code is a $k$-by-$n$ table of zeros and ones — each column says which message bits are added to make that transmitted bit — and the received bits are the values of $n$ linear equations in $k$ unknowns.

On an erasure channel, some of the equations are lost and the rest are correct. The receiver has a system of linear equations with no errors in it and a known subset missing, and decoding is solving the system. The message is recovered exactly when the surviving equations determine all $k$ unknowns — when the surviving columns of the table have rank $k$. This is the same Gaussian elimination that solves any system of linear equations, carried out modulo 2, where adding a row to another is exclusive-or.

So the question of how good a code is on this channel becomes a question about the rank of the columns that survive. For a random code, where the table’s entries are fair coin tosses, it has an exact answer.

An erasure is half an error #

The same distance that governs error correction governs erasures, with a factor of two in the erasures’ favour. A code whose codewords differ in at least $d$ positions corrects $(d-1)/2$ flips, because a received word must be closer to the sent codeword than to any other, and each flip moves it one step away. It fills in $d - 1$ erasures, because with fewer than $d$ positions missing, the surviving positions still differ between any two codewords, so only one codeword agrees with what arrived.

The factor of two is the whole difference between the two problems, and it is visible in the capacities. A flip costs two units of distance — one step away from the true codeword and, in the worst case, one step towards a rival — while an erasure costs one, since the receiver simply ignores the missing position. The perfect Hamming code, distance three, corrects one flip or fills in two erasures. The syndrome decoder that finds a flip without reading the message is doing the harder job; on the erasure channel it is not needed at all, because the location it computes is already known.

A single flip is an erasure whose position is hidden, and the entire cost of error correction over erasure correction is the cost of finding that position.

The chance that enough is enough #

Suppose the receiver collects random combinations of $k$ message bits, one at a time. After exactly $k$ of them, how likely is it to have enough?

The combinations determine the message when they are linearly independent, and the chance of that can be counted one combination at a time. The first is useless only if it is all zeros, a chance of $2^{-k}$. The second is useless only if it equals the first or zero, a chance of $2^{-(k-1)}$. The $j$-th is useless when it lies in the span of the previous ones, which holds $2^{j-1}$ of the $2^k$ possibilities. Multiplying the chances of success,

$$\Pr(k \text{ combinations suffice}) = \prod_{i=1}^{k} \left(1 - 2^{-i}\right),$$

which for large $k$ is $0.2888\ldots$ Only about 29% of the time do exactly $k$ random combinations pin down $k$ bits. With $m$ extra combinations the product runs from $1 - 2^{-(m+1)}$ upwards instead, and the chance of failure falls below $2^{-m}$: ten extras make it less than one in a thousand. The dots in the figure are two thousand trials at each $m$ and sit on the bars.

What matters is what does not appear in the formula: the length of the message. The chance of success with $m$ extras is essentially the same for twenty message bits as for twenty million. The cost of randomness on this channel is a handful of symbols, not a fraction of the block.

An overhead that does not grow #

The average number of extras follows from the same product.

Collecting random combinations until they span, the number needed is a sum of waiting times: once $j$ independent combinations are in hand, each new one is useful with probability $1 - 2^{j-k}$, so the wait for the next useful one averages $1/(1 - 2^{j-k})$. Adding these up and subtracting $k$ gives the average excess,

$$\sum_{j=1}^{k} \frac{1}{2^j - 1} \;\longrightarrow\; 1.6066951\ldots$$

The limit is the Erdős–Borwein constant, the sum of the reciprocals of one less than the powers of two. Paul Erdős proved in 1948 that it is irrational — the same year as Shannon’s paper — in a note on a different question entirely, about the number of divisors of whole numbers, since the same sum also equals $\sum_n d(n)/2^n$ with $d(n)$ the number of divisors of $n$. A coding overhead and a divisor count share a constant, and the constant’s irrationality was known before anyone asked what it cost to decode a random erasure code.

The right-hand panel shows a small curiosity the product contains: needing no extras and needing exactly one are equally likely, each about 28.9%. With one extra the product loses its smallest factor, $1 - 2^{-1}$, so in the limit the chance of success exactly doubles — and a doubling adds precisely the original amount, which is the chance of needing exactly one.

Below the limit and above it #

The capacity statement is about rates, and a random linear code shows both sides of it directly.

At rate 0.6 a block of length $n$ carries $0.6n$ message bits, and about $0.7n$ symbols survive the channel. The surplus, $0.1n$ symbols, grows with the block, and since a handful of extras suffices for random combinations, failure becomes rare as $n$ grows: from 49% at length 10 to 1% at length 160. At rate 0.8 the surviving symbols number about $0.7n$, fewer than the $0.8n$ unknowns, and no amount of cleverness can solve fewer equations than unknowns. Failure rises to certainty.

The transition sharpens with length because the number of survivors concentrates. At length 10 the count of surviving symbols varies by one or two either way, which is comparable to the surplus; at length 160 it varies by about six against a surplus of sixteen. The limit $1 - \varepsilon$ is where the surplus changes sign, and long blocks make that sign all that matters.

This is the whole of the coding theorem for the erasure channel, with an explicit decoder. Random codes reach capacity, as they do on the flipping channel — but here the decoder is Gaussian elimination, which runs in time proportional to the cube of the block length rather than searching every codeword. The obstacle that took sixty years on the flipping channel is absent, because the decoder never has to find the errors.

What structure buys: the Hamming code under erasures #

A random code has no structure, and structure can do better than randomness on a short block.

The Hamming code’s minimum distance is 3, so any two erasures can be filled in: two codewords agreeing everywhere except in two positions would be at distance two, which its minimum distance forbids. Three erasures usually can be, and fail exactly when the erased positions carry a codeword of weight three — then that codeword and the zero word agree on every surviving position and the receiver cannot tell them apart. The Hamming code has seven codewords of weight three, and they are the seven triples it cannot recover, leaving 28 of 35.

A code that recovered every three erasures from seven symbols carrying four would be as good as possible — every pattern leaving four symbols would suffice, which is the most that can be asked, since four unknowns need four equations. Codes with this property are called maximum distance separable, and over the two-symbol alphabet none exists at this size. Over larger alphabets they are plentiful. A Reed–Solomon code sends the values of a polynomial of degree below $k$ at $n$ points, and any $k$ values determine the polynomial by interpolation — so any $k$ of its $n$ symbols suffice, with no overhead at all.

That is why erasure coding in practice uses large alphabets. A symbol of eight bits is an element of a field with 256 elements, built as polynomials modulo an irreducible one exactly as the field with four elements is, and every non-zero element of it is a power of one of them, which is what makes its multiplication fast enough to run on every byte of a disk. The disks of a storage array and the packets of a network are symbols of hundreds of bits each, and a Reed–Solomon code over a field with 256 elements or more recovers the data from any $k$ surviving pieces. The usual way a storage array survives the loss of two disks, without keeping two full copies of everything, is a code of this kind.

Codes that decode as they arrive #

Gaussian elimination on a block of a million symbols is too slow for streaming, and the modern answer keeps the randomness while abandoning the density. A fountain code sends an endless stream of symbols, each the sum of a small random set of message bits, and the receiver collects symbols until it has enough — whichever ones arrive, in whatever order.

Michael Luby’s LT codes of 2002 chose the sizes of those small sets from a carefully designed distribution, so that decoding can proceed by peeling: find a received symbol that involves only one unknown message bit, read that bit off, subtract it from every other symbol involving it, and repeat. With the right distribution the peeling never gets stuck, and the overhead is a small fraction of $k$ rather than 1.6 symbols. Amin Shokrollahi’s Raptor codes of 2006 added a precode that brought the decoding time to linear in $k$. The price of sparseness, compared with the dense random codes above, is that the overhead is a small percentage instead of a constant — a good trade when the alternative is solving a million equations.

Where the erasures come from in practice #

The erasure channel is an idealisation, and the systems that use it manufacture it. A compact disc stores its data with two Reed–Solomon codes interleaved: the inner one is used only to detect that a short run of bytes is damaged — a scratch, a speck of dust — and it marks those bytes as erased rather than trying to correct them; the outer code, which now knows where the damage is, fills them in. Detecting an error is far cheaper than correcting it, and a code of distance five that would correct two errors can fill four erasures once they are flagged.

Networks do the same thing with checksums. A packet whose checksum fails is dropped, which converts a corrupted packet into a missing one, and the receiver knows its sequence number. The flipping channel underneath has been turned into an erasure channel on top, at the cost of the checksum bits, and the bounds on what a code can be are then applied to the easier problem. This layering is the practical answer to the difficulty of the flipping channel: rather than solve it at full generality, spend a little rate to convert it into the channel where the linear algebra works.

What the figures cannot show #

The rank and overhead figures are exact for the sizes drawn and the simulations agree with them; the limit $0.2888\ldots$ and the constant $1.6067\ldots$ are infinite products and sums whose values are known to many digits and whose limits no figure reaches. The claim that the success probability is independent of $k$ is about the limit; at $k = 20$ it is correct to six decimal places, which is as close as a picture can come.

The simulation of random linear codes uses three hundred blocks at five lengths. Its numbers are estimates, and the sharpening of the threshold is visible over a factor of sixteen in length and not over the factor of millions at which real systems operate. The theorem behind it is the concentration of the number of surviving symbols, which the figure illustrates and does not prove.

And the Hamming comparison is one small code. That maximum distance separable codes do not exist over two symbols at these parameters is checked by the Hamming code’s seven bad triples; that they exist over large alphabets is the interpolation argument, which the figure’s second set of bars represents rather than computes.

Still open: how long a perfect erasure code can be #

Reed–Solomon codes over a field with $q$ elements have length at most $q$, or $q + 1$ with one extra point at infinity. Is that the longest any maximum distance separable code over that alphabet can be? The MDS conjecture says yes — apart from a few known exceptions in even characteristic, no code recovering from every pattern of $n - k$ erasures has length beyond $q + 1$.

Simeon Ball proved it in 2012 for alphabets of prime size, by an argument about polynomials that did not extend. For alphabets whose size is a power of a prime, which include the fields of 256 and 65,536 elements that storage systems use, it remains open in general. The question has a geometric form: an MDS code is equivalent to a set of points in a projective space with not too many on any hyperplane — an arc — and the conjecture is a bound on how large an arc can be, a relative of the hyperovals whose classification is also unfinished. For the fields of practical size the conjecture has been checked by computer for small dimensions, and nobody has found a counterexample; what is missing is an argument that works for every power of a prime at once, as Ball’s works for every prime.

Known to be unknown #

The erasure channel is the flipping channel with one piece of information added — the positions of the damage — and that piece changes everything about the problem. The capacity rises from $1 - H(p)$ to $1 - p$. Random codes reach it with a decoder that is ordinary linear algebra. The overhead of randomness is 1.607 symbols on average, however long the message. And codes over large alphabets reach the limit on every block, not just on average, by interpolating a polynomial through whatever survives.

What is left difficult is what always is: making the decoder fast enough for millions of symbols, and knowing how far the perfect codes go. The first was answered by sparse codes that can be peeled; the second is a conjecture about arcs in projective space that has resisted proof for sixty years, and on which every storage system’s choice of alphabet silently depends.

Seen from the flipping channel, the whole essay is a single piece of information priced. Knowing where the damage is moves the limit from $1 - H(p)$ to $1 - p$, turns decoding from a search into a system of equations, and makes the random code’s overhead a constant instead of a fraction. Every practical system that can afford a checksum buys that information, and then spends the rest of its effort on the problem that the capacity of a noisy channel says is the easy one.