Noisy-channel coding theorem

The result that made reliable communication over unreliable hardware a solved question in principle and an open one in practice for the next fifty years. Every discrete memoryless channel has a capacity

C = max_{P_X} I(X;Y)

the largest mutual information any input distribution can push through it, and reliable communication is possible at every rate below C and impossible above it.

Sourced from information-theory-inference-learning-algorithms, held in ../machine-learning-wiki (see the provenance note on information-theory).

The three parts

MacKay states it as two positive claims and one negative (ch. 10):

1. For any ε > 0 and any rate R < C, there exists — for large enough blocklength N — a code of rate R and a decoder whose maximal block error probability is below ε.
2. If a bit error rate p_b is acceptable, rates up to R(p_b) = C / (1 − H₂(p_b)) are achievable.
3. No rate above R(p_b) is achievable.

Part 1 is the famous one; parts 2 and 3 together draw the achievable region of the rate/error plane, and part 3 is what makes the boundary a limit rather than a record.

The number that makes it surprising

For a binary symmetric channel that flips each bit with probability f, capacity is C(f) = 1 − H₂(f). At f = 0.1 — a channel corrupting a tenth of everything — C ≈ 0.53. So a rate-½ code communicates at arbitrarily small error over it.

MacKay dramatises the gap against the naive approach with disk drives. Triple repetition gets a bit error rate of about 3% at rate ⅓; reaching 10⁻¹⁵ by repetition takes sixty copies. Shannon's answer to the same question:

"What performance are you trying to achieve? 10⁻¹⁵? You don't need sixty disk drives — you can get that performance with just two disk drives (since 1/2 is less than 0.53). And if you want p_b = 10⁻¹⁸ or 10⁻²⁴ or anything, you can get there with two disk drives too!"

The qualification MacKay adds himself is the one that matters for coding-theory: the required blocklength may be larger than the disk.

How it is proved, and what the proof withholds

Shannon does not exhibit a code. He computes the average block error probability over all randomly generated codes, shows the average is small, and concludes that good codes exist. MacKay's analogy:

"Imagine that we wish to prove that there is a baby in a class of one hundred babies who weighs less than 10 kg. Individual babies are difficult to catch and weigh. Shannon's method … is to scoop up all the babies and weigh them all at once on a big weighing machine."

The decoder in the proof is a typical-set decoder: declare the codeword that is jointly typical with the received sequence, and fail if there is not exactly one. It is chosen because it is easy to analyse, not because anyone would build it.

Two refinements sharpen the asymptotics without closing the gap. The random-coding exponent E_r(R) bounds achievable error as p_B ≤ exp[−N E_r(R)], and the sphere-packing exponent E_sp(R) bounds it from below — but even for the binary symmetric channel there is no simple expression for E_r(R), and MacKay notes Berlekamp's practical objection: a customer does not know his channel well enough for these functions to be the useful output. Plot a system's performance across a range of noise levels instead.

The consequence

The theorem is an existence proof whose object cannot be built at the size it requires: encoding and decoding a random code of blocklength N costs resources exponential in N. Everything in coding-theory follows from trying to close that gap, and the codes that finally did (low-density-parity-check-code, turbo codes, fountain-code) all kept the randomness and constrained it into a sparse graph.

Related

information-theory · entropy · coding-theory · error-correcting-code · source-coding-theorem · claude-shannon · information-theory-inference-learning-algorithms · mathematics · synthesis