The rate a noisy channel allows

Every code considered so far has been judged by what it can guarantee. The Hamming code corrects any single flip in a block of seven; the best code of a given length is the largest set of words pairwise far enough apart; and a decoder that returns a list reaches past the radius at which answers are unique. All of those are statements about the worst case: how many flips, placed anywhere, a code survives.

A real channel does not place flips adversarially. It flips each bit independently with some probability — one in ten, say — and the question changes. It is no longer how many errors a code can survive, but how reliably messages get through, and at what cost in extra bits. Claude Shannon answered it in 1948, and the answer is a single number for each channel.

The curve is the capacity of the channel. At every rate below it — every number of message bits per transmitted bit — there are codes whose error probability is as small as anyone asks. At every rate above it there are none. For a channel flipping one bit in ten the dividing line is 0.531: just over half the transmitted bits can carry message, and the rest must pay for the noise.

A number that measures noise #

The capacity is $1 - H(p)$, and $H(p) = -p \log_2 p - (1-p)\log_2(1-p)$ is the binary entropy: the average number of bits needed to describe the outcome of a coin that lands heads with probability $p$. At $p = 0.1$ it is 0.469. A fair coin has entropy 1, since each toss is a full bit of news; a coin that always lands tails has entropy 0.

The formula says that each transmitted bit carries one bit of capacity, of which $H(p)$ is spent describing the noise. The receiver sees a word, and to know what was sent it has to know which bits were flipped; that information is not in the word, so the sender must supply it, and it costs $H(p)$ per bit. At $p = 0.5$ the channel flips a fair coin on every bit and $H$ is 1: nothing gets through at all, which the curve reaches at its right-hand end.

The three points on the figure are three codes at $p = 0.1$. Sending bare bits has rate 1 and error 0.1 per bit — far above the curve, and no amount of care makes it reliable. Repeating each bit three times and taking the majority has rate a third and error 0.028: reliable-ish and wasteful, well below the curve. The Hamming code, four message bits in seven, has rate 0.571 and fails on a block whenever two or more of its seven bits flip, which at this $p$ is 15% of blocks. Its rate is just above capacity, so no refinement of the idea at that rate can drive the error down.

Why the best input is a fair coin #

The formula can be derived rather than taken on trust, by asking how much a received bit says about the bit that was sent. The mutual information between input and output is the uncertainty in the output minus the part of it the noise alone produces: $H(\text{output}) - H(\text{output} \mid \text{input})$. Given the input, the output is the input flipped with probability $p$, so the second term is $H(p)$ whatever the input was. The first term is the entropy of the output bit, which is at most 1, and equals 1 exactly when the output is equally likely to be 0 or 1.

So the information per bit is at most $1 - H(p)$, and it reaches that when the output is a fair coin — which, on a symmetric channel, happens exactly when the input is. The capacity is this maximum, taken over every way of choosing the inputs, and Shannon’s theorem is the statement that the maximum can be realised by coding: blocks of fair-looking input bits, chosen from a code, carry $1 - H(p)$ bits of message each.

The derivation explains why capacity is a property of the channel and not of any code. It is the most a single use of the channel can convey on average, and a code is only a way of making that average count for every message rather than for the typical one. For a channel that treated 0 and 1 differently — flipping ones more often than zeros, say — the best input would not be a fair coin, and the capacity would come from a genuine optimisation; for this channel, the symmetry does it.

How many ways a block can be damaged #

The reason there is a limit is a count.

In a block of a hundred bits, the number that flip is almost never far from ten. It is between 4 and 16 in 97% of blocks, and the spread shrinks relative to the block as the block grows: in a block of ten thousand, the count is within a few percent of a thousand nearly always. This is the concentration of a sum of many small independent effects, the same fact that makes the bell curve appear wherever such sums do.

So the noise is not any of the $2^{100}$ possible patterns. It is almost certainly one of the patterns with about ten flips, and there are about $2^{nH(p)}$ of those — the count of ways to choose ten positions from a hundred is $2^{44.0}$, and the exponent per bit tends to $H(0.1) = 0.469$ as the block grows. These are the typical noise patterns.

Now the limit is arithmetic. A decoder receives a word and must work out which codeword was sent. Around each codeword lies a cloud of about $2^{nH(p)}$ words it is likely to become. If the clouds of different codewords overlap substantially, the decoder cannot tell them apart; if they do not, there are at most $2^n / 2^{nH(p)} = 2^{n(1 - H(p))}$ codewords, and the rate — message bits per transmitted bit — is at most $1 - H(p)$. That is the ceiling, and it is the counting argument behind the sphere-packing bound with the spheres replaced by the clouds a random channel actually produces.

Repetition, and the price of certainty #

The first code anybody thinks of for a noisy channel is to say everything several times.

Repetition works in the sense that its error goes to zero. With fifteen copies of each bit the majority is wrong about once in thirty thousand bits. But the rate goes to zero at the same time: fifteen copies carry one bit, a rate of 0.067. Every point in the figure is far to the left of capacity, and they march further left as they improve.

Before Shannon, this trade was widely assumed to be unavoidable — that reliability over a noisy channel had to be bought with rate, and complete reliability with all of it. The coding theorem says the opposite: at any fixed rate below 0.531, the error can be made as small as desired, by coding over long enough blocks. The Hamming code shows the first step of the alternative. Four message bits sent as seven, with three check bits each depending on several message bits, cost a rate of $4/7$ instead of repetition’s $1/3$ and still correct every single flip in the block. Repetition at the same rate would correct nothing, since a bit sent twice cannot be put to a majority vote. Sharing the checks among several message bits buys correction far more cheaply than duplicating each one, and the syndrome reads off where the flip was without ever looking at the message.

Repetition is the worst way to spend redundancy, because it protects each bit separately; a good code spreads the protection of every message bit across the whole block, so that the block’s typical ten flips can be located and undone together.

A code chosen at random #

Shannon’s proof that good codes exist does not construct one. It chooses codewords at random and shows that, on average, the result is good.

For a block of length $n$ at rate $R$, pick $2^{nR}$ words of $n$ bits entirely at random, as the codebook. Send one; the channel flips about $np$ of its bits; the decoder picks the codeword nearest to what arrived. The sent codeword is at distance about $np$. Any other codeword is a random word, and the chance that a random word falls within distance $np$ of the received word is about $2^{nH(p)}/2^n$. With $2^{nR}$ rivals, the expected number that fall that close is about $2^{n(R - (1 - H(p)))}$ — which shrinks exponentially with $n$ when $R$ is below capacity and grows exponentially when it is above.

The figure does this with small blocks and real noise. At rate 0.25, below capacity, the block error falls from 0.72 at length 6 to 0.07 at length 18, as the rivals thin out. At rate 0.75, above capacity, it rises from 0.63 to 0.72 and is heading for 1. The lengths are tiny — a code of rate 0.75 at length 18 already has 11,000 codewords to search — but the directions are the theorem’s, and they separate on either side of 0.531 as the argument says they must.

The randomness is a proof technique, not a recipe. A random code of useful length has more codewords than atoms in a building, has no structure to decode with except comparing against all of them, and would have to be written down in full for sender and receiver to share. What the argument proves is that good codes are not rare; almost every code is good, which makes it more surprising, not less, that finding an explicit one took decades.

Two papers from one corridor #

The worst-case theory and the capacity theory were born within two years of each other at Bell Telephone Laboratories. Richard Hamming, frustrated by a computer that stopped at every detected error over a weekend, devised a scheme that corrects single errors, and his results were circulated inside the laboratory before they were published in 1950. Shannon’s paper of 1948 cites the seven-bit code as an example of what coding can do — with credit to Hamming — before proving that far more is possible. The example was the right one to choose: it is perfect, in the sense that its spheres fill the space of words exactly, and yet at a flip rate of one in ten it sits above the limit the rest of the paper derives.

The two papers asked different questions and got answers of different kinds. Hamming’s was constructive and exact: here is a code, here is what it guarantees. Shannon’s was existential and asymptotic: good codes exist, their rates approach a number, and nothing is said about how to find one of any particular length. The subject spent the following decades trying to make Shannon’s answer constructive, with codes built from polynomials over finite fields, from sparse matrices and from recursive combinations, and it is only recently that the two kinds of answer have fully met.

Codes that exist, and codes that can be used #

The distance between existence and construction is the history of coding theory after 1948.

The best short codes improve with length, but only when the number of errors they correct is held fixed. Capacity asks for something different. A block of length $n$ on this channel suffers about $n/10$ flips, so a code that is to survive them must correct a number of errors growing in proportion to the length — distance 3 at length 8 is a fixed guarantee that the channel will soon exceed. The worst-case theory of distance and the average-case theory of capacity meet here, and they meet uneasily: a code that corrects a fixed fraction of worst-case errors cannot reach the capacity of the random channel with the same fraction of flips, since worst-case correction needs roughly twice the spacing that random noise requires.

Explicit codes approached capacity slowly. David Forney’s concatenated codes of 1966 had error falling exponentially with block length at any rate below capacity and could be decoded in polynomial time. Turbo codes in 1993, and the rediscovery in the 1990s of the low-density parity-check codes Robert Gallager had described in 1960, came within a fraction of a decibel of capacity in practice, without proofs that they reach it. Erdal Arıkan’s polar codes of 2009 were the first explicit construction proved to reach capacity on channels like this one, with efficient encoding and decoding. And in 2023 Emmanuel Abbe and Colin Sandon proved that the Reed–Muller codes, known since 1954, had been capacity-achieving on the flipping channel all along.

What the proof actually establishes #

The theorem has two halves, and their strength differs.

The achievability half says that for every rate below capacity and every tolerance, there is a length and a codebook with error below the tolerance. The random-code argument proves it, and a sharper version of the same argument shows that the error can fall exponentially with length, at a rate — the error exponent — that shrinks to zero as the rate approaches capacity. Codes near capacity need very long blocks.

The converse half says that above capacity the error cannot go to zero, and in its strong form that it goes to one. The counting argument above is the heuristic; the proof uses Fano’s inequality, which bounds how much information a guess can recover when the guess is sometimes wrong. Neither half says anything about blocks of any particular length. The capacity is a limit as the block grows, and the figures, at lengths up to 18, show the tendency rather than the limit.

It is also a statement about one channel. The flipping channel is the simplest noisy channel with memoryless, independent errors. Real channels have bursts, fading and interference, and each has its own capacity, computed from its own statistics by maximising the information the output carries about the input — a formula that reduces to $1 - H(p)$ here because this channel is symmetric and the best input is fair coin tosses.

What the figures cannot show #

The random-code figure is a simulation with fixed seeds: three hundred messages at each length, with codebooks drawn once. Its numbers have sampling noise of several percent, and at rate 0.25 the error even ticks up slightly between the last two lengths. The theorem is not about any finite set of simulated blocks, and the figure is evidence for its direction at small lengths, not a measurement of the limit.

The typical-set count shows one block length. That the fraction of patterns near $np$ flips tends to one, and that their number has exponent tending to $nH(p)$, are statements about the limit, proved by the law of large numbers and Stirling’s estimate of factorials; a block of a hundred shows the shape but still has a quarter of its probability spread over counts other than ten.

And the capacity curve itself is drawn from the formula. What makes it a capacity — that rates below it are achievable and rates above are not — is a theorem about all codes of all lengths, and no figure of three codes at one flip rate contains that.

The question it leaves: the channel where the limit is easy #

Everything here is harder than it looks because the decoder does not know which bits were flipped. There is a channel where it does. Suppose each bit, instead of being flipped, is sometimes erased — delivered as a mark saying “this bit was lost” — so that the receiver knows exactly which positions to distrust.

The capacity of that channel is $1 - \varepsilon$ for an erasure probability $\varepsilon$, higher than the flipping channel’s at every level of noise, and random linear codes reach it with nothing more than the solution of simultaneous linear equations. How cheaply, and with what surprising constant, is the subject of the essay on the erasures a code can see.

The comparison is instructive before it is worked out. An erased bit and a flipped bit are both lost, but an erased bit is lost visibly. The flipping channel’s decoder must first find the damage and then repair it, and finding it is where the entropy $H(p)$ goes; the erasing channel’s decoder is told where the damage is and has only to repair it. The difference between $1 - H(p)$ and $1 - p$ is the price of not knowing where to look.

One number for a noisy line #

The whole theory compresses into the curve on the first figure. A channel that flips a tenth of its bits can carry 0.531 bits of message per bit sent, with any reliability demanded, and cannot carry more. The number comes from a count: noise almost always takes one of about $2^{nH(p)}$ forms, and codewords must be spaced so that those clouds do not overlap.

Three things about it are still worth being surprised by. That reliability does not have to cost rate — repetition’s lesson was wrong. That almost every code is good — the difficulty was never existence. And that it took sixty years after the theorem for a code to be proved to reach the limit with a decoder anyone could run, although engineers had been operating within a whisker of it for a decade and a half.

What the theorem changed was the question engineers asked. Before it, the question was how much reliability a given amount of redundancy buys, and the answer seemed to be diminishing returns without end. After it, the question was how close a practical code can come to a known limit, and the limit was a single number for each channel, computable from the channel’s statistics before any code was designed. Every modern communication standard is specified by how far below capacity it runs.