Symptom

Your link drops 1% of bits. You need reliable delivery, so you triple every bit and take a majority vote. Now an error needs two of three bits to flip, which happens with probability about $3 \times 10^{-4}$ — better, but you paid 3x in bandwidth and the error rate is still not zero.

You want it lower, so you send five copies. Then seven. The error rate falls and the throughput falls with it, and the obvious extrapolation is depressing: arbitrarily reliable communication costs arbitrarily much bandwidth, and the efficiency of a reliable channel tends to zero. That extrapolation is the intuition essentially everyone has, it is what repetition coding demonstrates, and it dominated engineering practice before 1948.

It is false, and its falseness is probably the most surprising single result in this series. There is a rate — a strictly positive one, computable from the noise level — below which you can drive the error probability as close to zero as you like without reducing the rate at all. Reliability is not bought with bandwidth. It is bought with block length, which is to say with latency and computation, and those are much cheaper things to spend.

Statement

Define the channel capacity as the maximum mutual information between input and output over all input distributions:

$$C = \max_{p(x)} I(X; Y).$$

Then for any rate $R < C$ and any $\varepsilon > 0$, there exists a block length $n$ and a code of rate $R$ with error probability less than $\varepsilon$. Conversely, for any $R > C$, the error probability is bounded away from zero — no code at any block length achieves reliable communication above capacity.

Two halves, and both matter. The forward part says reliability below capacity is free in the currency you expected to pay. The converse says capacity is a hard wall: the failure above it is not gradual degradation but a genuine impossibility, and this is the part that makes $C$ a law rather than a benchmark.

For the binary symmetric channel with crossover probability $p$:

$$C = 1 - H(p).$$

At $p = 0.01$, $C = 1 - 0.0808 = 0.919$ bits per channel use. So the 1%-error link can carry 0.919 bits of reliable payload per bit sent — a 9% overhead, not a 200% one. Repetition coding at 3x uses 33% of the channel to get $10^{-4}$; capacity says 92% of it gets you $10^{-15}$.

Argument

Why capacity is mutual information. $I(X;Y) = H(X) - H(X \mid Y)$ is the uncertainty about the input, minus what remains after seeing the output. That is exactly “how much of what I sent got through.” Maximizing over input distributions asks how much can get through if I choose my signalling well. For the BSC, symmetry makes uniform input optimal, and $H(X \mid Y) = H(p)$ because knowing the output leaves precisely the uncertainty of whether this bit was flipped. Hence $C = 1 - H(p)$, and the interpretation is direct: the noise consumes $H(p)$ bits of every bit you send, and the rest is yours.

The forward proof: random coding. This is Shannon’s move and it is worth following, because it is the reason the theorem arrived thirty years before anyone could use it.

Pick $2^{nR}$ codewords of length $n$ uniformly at random, and give the codebook to both parties. To decode, find the unique codeword that is jointly typical with the received sequence — roughly, the one whose empirical correlation with the output matches what the channel statistics predict.

Now bound the error. Two things go wrong: the transmitted codeword is not typical with the output (probability $\to 0$ by the law of large numbers, since $n$ independent uses concentrate — this is T008), or some other codeword is jointly typical by accident. The number of sequences jointly typical with a given output is about $2^{n H(X|Y)}$ out of $2^{nH(X)}$ total, so a random codeword collides with probability about $2^{-nI(X;Y)}$. Union bound over the $2^{nR}$ competitors:

$$P(\text{error}) \lesssim 2^{nR} \cdot 2^{-nI(X;Y)} = 2^{-n(I - R)}.$$

If $R < I$, this goes to zero exponentially in $n$. That is the theorem. The rate stays fixed and the errors vanish, paid for by block length.

Two features of this argument are worth naming. First, it proves that the average code over the random ensemble is good, so a good code must exist — without producing one. Second, expurgation (throwing away the worst half of the codewords) upgrades average error to maximal error at negligible rate cost. This is the probabilistic method (T007’s existence-proof pattern) doing the heaviest lifting anyone has ever asked of it.

The converse. Fano’s inequality bounds the residual uncertainty given the output: $H(W \mid \hat{W}) \le 1 + P_e \cdot nR$. Chain it with the data processing inequality — information cannot increase along the Markov chain $W \to X^n \to Y^n \to \hat{W}$ — and you get $nR \le nC + 1 + P_e nR$, so

$$P_e \ge 1 - \frac{C}{R} - \frac{1}{nR}.$$

Above capacity, $P_e$ is bounded below by a positive constant no matter how large $n$ is. Bigger blocks do not help. The wall is real.

The fifty-year gap. Shannon proved a good code exists in 1948 with no way to build one; random codes need exponential-time decoding. Hamming and Reed–Solomon codes came close on some channels; convolutional codes with Viterbi decoding got closer. Turbo codes (Berrou, 1993) came within 0.5 dB of capacity and stunned the field. LDPC codes — invented by Gallager in 1962, forgotten as computationally infeasible, rediscovered in the 1990s — do it too and are now in Wi-Fi 6, 5G, and DVB-S2. Polar codes (Arıkan, 2008) are the first provably capacity-achieving construction with practical decoding, and are in 5G control channels. The theorem set the target and the target held for half a century.

Forbids

Reliable communication above capacity, at any block length or complexity. If your channel’s capacity is 100 Mbps you will not get 110 Mbps reliably. Not with a better code, not with more compute. Claims to the contrary are claims to have broken the converse.

Reliability requiring rate to vanish. The repetition-coding intuition is wrong. Any scheme whose overhead grows without bound as the target error rate falls is leaving capacity on the table, and is beatable by a fixed-rate code with a longer block.

Beating capacity by retransmission. Feedback does not increase the capacity of a memoryless channel. ARQ and TCP retransmission improve practical throughput on bursty channels and change nothing about the limit.

Does not forbid

It does not say the code is easy to find, and for fifty years it was not. Shannon’s proof is non-constructive, which is why the achievable-rate curve and the practical-rate curve were far apart for decades. This is the honest reading of “reliability is free”: free in bandwidth, expensive in ingenuity.

It does not make latency free, and this is the trade that actually bites. Error probability falls like $2^{-n(C-R)}$, so approaching capacity needs large $n$, and $n$ is buffered symbols before you can decode. This is why deep-space links (Voyager used a concatenated Reed–Solomon/convolutional code) happily use enormous blocks and why real-time voice does not. 5G’s control channels use short polar codes and its data channels use long LDPC codes for exactly this reason.

It does not apply to adversarial errors. The capacity is computed for a probabilistic channel. An adversary who chooses which bits to flip is a different model, and the achievable rates are lower — this is the domain of Hamming’s combinatorial bound (T022) rather than Shannon’s probabilistic one, and the gap between the two is why the two theories coexist rather than one subsuming the other.

It does not require knowing the channel. Rateless codes (fountain codes, LT and Raptor) generate limitless encoded symbols and let the receiver stop when it has enough. RaptorQ is standardized and used in 3GPP multicast; the receiver does not need to know the erasure rate in advance, which is a genuine practical escape from having to estimate $p$.

It does not say error-free. The theorem gives arbitrarily small error, never zero. Every real link has a residual error rate, which is why storage systems layer checksums above error-correcting codes, and why “10^-15 uncorrectable bit error rate” appears on drive datasheets rather than “no errors.”

It does not mean separate source and channel coding is always right. Shannon’s separation theorem says compressing then coding loses nothing asymptotically — but at finite block length, and especially over multiple-user channels, joint source-channel coding wins. This is why video codecs and their transport are co-designed rather than layered.

Boundary

  • Finite block length. Polyanskiy, Poor and Verdú’s normal approximation gives the achievable rate at block length $n$ as roughly $C - \sqrt{V/n},Q^{-1}(\varepsilon)$, where $V$ is channel dispersion. This is the theorem made engineering-usable, and it is what tells you whether a 1000-symbol block is enough.
  • The Gaussian channel. $C = \frac{1}{2}\log_2(1 + \mathrm{SNR})$ per use, which becomes the Shannon–Hartley formula $C = B\log_2(1 + S/N)$. Every claim about how fast a wireless link could go traces here, and it is why increasing bandwidth beats increasing power: capacity is linear in $B$ and logarithmic in SNR.
  • Channels with memory and feedback. Real channels are bursty. Interleaving spreads a burst across blocks so it looks memoryless to the decoder, which is a general and cheap trick. Feedback does not raise capacity but does reduce the block length needed, which is a latency win.
  • The erasure channel is the friendly case. Capacity is $1 - p$, and the codes are simple: any $k$ of $n$ symbols suffice with an MDS code. This is exactly RAID and erasure-coded object storage, and it is why distributed storage math is tractable while wireless is not.
  • The gap to T022. Shannon says what is achievable on average against random noise. Hamming says what is possible in the worst case against any $t$ errors. Both are real bounds and neither implies the other, which is the subject of the next post.