The Problem Shannon Left Behind

Every phone call you make, every video you stream, and every bit your SSD reads back correctly is riding on an idea that spent forty-five years looking impossible. In 1948 Claude Shannon proved that essentially error-free communication over a noisy channel is achievable, then left engineers a problem so hard that closing the gap between his theorem and working hardware took until the 1990s, and the story is still unfolding in the coding standards deployed today. This series traces that story through its three protagonist code families: turbo codes, LDPC codes, and polar codes. This opening page sets up the problem they all answer, equips you with the small toolkit the whole series leans on, and fixes the shared vocabulary (and the classic traps) you’ll need to read any performance curve honestly.

Shannon’s Theorem and Its Two Unsolved Problems

Shannon’s 1948 theorem says that every noisy channel has a capacity $C$, and that for any rate $R < C$ there exist codes making the error probability as small as you like. That is an astonishing claim: noise does not impose a quality ceiling, only a rate ceiling. But look at how the proof works and the trouble starts. Shannon didn’t construct a good code; he showed that a code whose $2^k$ codewords are drawn at random performs well on average, when decoded by maximum-likelihood (ML) decoding, which compares the received word against every codeword and picks the closest.

That proof is famously unhelpful in practice, because it leaves two problems unsolved. First, construction: a random code has no structure, so the only way to specify it is to store all $2^k$ codewords explicitly. For $k = 1000$ information bits (a modest block by modern standards) that is more codewords than atoms in the observable universe. Second, decoding: ML decoding of an unstructured code means checking all $2^k$ candidates, an $O(2^k)$ search that is physically unrealizable for any interesting $k$.

The obvious escape is structure. Give the code algebraic regularity and both problems soften: a compact description replaces the codeword list, and clever algorithms replace brute-force search. But for decades the field’s working belief was that this escape came at a price. Here is the central tension of coding theory in one breath: structure makes decoding tractable, but structure was thought to cost performance; randomness achieves capacity, but random codes cannot be decoded. Highly structured codes (Hamming, BCH, Reed-Solomon, convolutional codes with Viterbi decoding) were decodable and useful, yet they sat stubbornly far from Shannon’s limit. Random codes sat at the limit and were useless.

Every code family in this series is a different answer to the same question: how do I get random-like performance from a structure I can actually decode? Each family’s trick fits in a sentence.

Family	The trick
Turbo	Two simple convolutional codes joined by a long random interleaver. Each is individually decodable; the interleaver supplies the randomness. Decode by having the two decoders exchange soft information iteratively.
LDPC	A sparse parity-check matrix. Sparsity makes local, per-check inference cheap; the random sparse graph supplies the randomness. Decode by belief propagation on the graph.
Polar	A deterministic recursive transform that turns $N$ identical mediocre channels into $N$ channels that are each either almost perfect or almost useless. Send data only on the good ones. No randomness at all.

Notice the historical irony hiding in that table. Shannon’s proof paired an unstructured code with the optimal decoder. All three modern families do the reverse: they pair structured codes with suboptimal decoders. Turbo and LDPC decoding are heuristic (their message-passing algorithms are exactly optimal only on cycle-free graphs, which real codes never are), and the basic successive-cancellation decoder for polar codes is greedy, committing to each bit decision without ever revisiting it. The great empirical surprise of the last three decades is that this concession costs almost nothing: the gap between these practical decoders and true ML decoding turned out to be negligible. The field spent forty years assuming decodability and performance were enemies; they turned out to be nearly free of each other.

Preliminaries

Before you can reason about any of the three families, you need a small amount of classical machinery in hand. None of it is deep, but all of it is used constantly, so it’s worth checking each piece now rather than mid-derivation later.

From linear block codes you need the two matrix descriptions and what they buy you. A $k \times n$ generator matrix $G$ maps information words to codewords, $\mathbf{c} = \mathbf{u}G$, and an $(n-k) \times n$ parity-check matrix $H$ characterizes membership: $\mathbf{c}$ is a codeword exactly when $H\mathbf{c}^\mathsf{T} = \mathbf{0}$. Applying $H$ to a received word gives the syndrome, which depends only on the error pattern, not on which codeword was sent; that separation is what makes algebraic decoding possible at all. The minimum distance $d_{\min}$, the smallest Hamming distance between distinct codewords (equivalently, the smallest weight of a nonzero codeword, by linearity), controls how the code behaves when the channel is good; hold that thought, because the performance vocabulary below returns to it.

From convolutional codes you need the picture of an encoder as a small shift register whose generator polynomials tap its state, and the two equivalent unrollings of that state machine: the state diagram and, unrolled in time, the trellis. The trellis matters because the Viterbi algorithm is nothing more than a shortest-path search through it, and the trellis view is the doorway to the soft-decision decoders at the heart of turbo decoding. The convolutional analogue of minimum distance is the free distance $d_{\text{free}}$, the lowest weight of any path that leaves the all-zero state and returns to it.

You also need the three channel models the whole literature is calibrated against. The binary symmetric channel BSC($p$) flips each bit independently with probability $p$. The binary erasure channel BEC($\epsilon$) never lies but sometimes shrugs: each bit arrives intact or is erased with probability $\epsilon$, and its analytical transparency makes it the sandbox where nearly every theorem in this series is proved first. The binary-input AWGN channel adds Gaussian noise to a BPSK symbol and is where real radios live. Each has a known capacity, and “gap to capacity” always means the gap to the relevant one of these.

Finally, one classical estimate ties distance to error probability. For soft-decision decoding on the BI-AWGN channel, the union bound sums pairwise error probabilities over all wrong codewords using the Gaussian tail function $Q(\cdot)$:

$$P_e \le \sum_{\mathbf{c} \ne \mathbf{c}_0} Q\!\left(\sqrt{2\, d(\mathbf{c},\mathbf{c}_0)\, R\, \tfrac{E_b}{N_0}}\right).$$

Proof of the union bound

Linearity: the multiset of distances from any codeword to the rest of the code is the same for every choice of reference codeword. A linear code $C \subseteq \mathbb{F}_2^n$ is a subgroup under XOR, and Hamming distance is XOR weight, $d(\mathbf{c}, \mathbf{c}_0) = \mathrm{wt}(\mathbf{c} \oplus \mathbf{c}_0)$. For fixed $\mathbf{c}_0 \in C$, translation $\mathbf{c} \mapsto \mathbf{c} \oplus \mathbf{c}_0$ is a bijection of $C$ onto itself (it is its own inverse, and closure keeps it inside $C$), so

$\{\, d(\mathbf{c}, \mathbf{c}_0) : \mathbf{c} \in C \,\} \;=\; \{\, \mathrm{wt}(\mathbf{c} \oplus \mathbf{c}_0) : \mathbf{c} \in C \,\} \;=\; \{\, \mathrm{wt}(\mathbf{c}') : \mathbf{c}' \in C \,\},$

the weight distribution of $C$: independent of $\mathbf{c}_0$. The union bound sums a fixed function $g(d) = Q(\sqrt{2dRE_b/N_0})$ over exactly this multiset of distances; a sum depends only on the multiset of values fed into it, not on which codeword produced which value, so its total is likewise independent of which codeword is transmitted.

Channel symmetry: the pairwise error probability between two codewords depends only on their Hamming distance $d$, not on which coordinates differ or which two codewords they are. This is exactly what Step 2 below computes directly: the result $Q(\sqrt{d}\, a/\sigma)$ depends on $\mathbf{c}$ and $\mathbf{c}_0$ only through $d$, because AWGN treats every coordinate identically and the derivation only ever uses the size of the differing set $D$, never its location.

Linearity fixes the multiset of distances each term of the union bound ranges over; channel symmetry fixes the value of each term as a function of distance alone. Together they make $P_e$ independent of the transmitted codeword, so it suffices to evaluate the bound for one convenient choice of $\mathbf{c}_0$. Assume without loss of generality that the all-zero codeword $\mathbf{c}_0$ is transmitted, mapped under BPSK to $\mathbf{x}_0 = (a, a, \dots, a)$.

Step 1: maximum-likelihood decoding is minimum-distance decoding. Every codeword maps under BPSK to a signal point of the same energy, $\|\mathbf{x}\|^2 = na^2$, so maximizing the AWGN likelihood $p(\mathbf{y} \mid \mathbf{x}) \propto \exp(-\|\mathbf{y}-\mathbf{x}\|^2 / 2\sigma^2)$ over codewords is the same as minimizing the Euclidean distance $\|\mathbf{y} - \mathbf{x}\|$. The ML decoder simply picks the closest signal point.

Step 2: the pairwise error probability. Fix one competing codeword $\mathbf{c} \ne \mathbf{c}_0$ at Hamming distance $d = d(\mathbf{c}, \mathbf{c}_0)$, and let $D$ be the set of $d$ coordinates where $\mathbf{c}$ and $\mathbf{c}_0$ differ; there $x_i = -a$ while $x_{0,i} = +a$. The coordinates outside $D$ are identical in $\mathbf{x}$ and $\mathbf{x}_0$, so they contribute equally to both distances and cancel, leaving

$\|\mathbf{y} - \mathbf{x}\|^2 < \|\mathbf{y} - \mathbf{x}_0\|^2 \;\iff\; \sum_{i \in D} (y_i + a)^2 < \sum_{i \in D} (y_i - a)^2 \;\iff\; \sum_{i \in D} y_i < 0.$

Substituting $y_i = a + w_i$ with $w_i \sim \mathcal{N}(0, \sigma^2)$ i.i.d. gives $\sum_{i \in D} y_i = da + Z$ with $Z \sim \mathcal{N}(0, d\sigma^2)$, so

$\Pr[\mathbf{c} \text{ preferred over } \mathbf{c}_0] = \Pr[Z < -da] = Q\!\left(\sqrt{d}\, \frac{a}{\sigma}\right).$

Writing $E_c = a^2$ for the energy per coded symbol, $\sigma^2 = N_0/2$, and $E_b = E_c / R$ for the energy per information bit, $a^2/\sigma^2 = 2E_c/N_0 = 2RE_b/N_0$, so this pairwise error probability is exactly $Q\!\left(\sqrt{2\,d\,R\,E_b/N_0}\right)$: the summand of the boxed bound.

Step 3: the union bound. The decoder errs exactly when some competing codeword beats $\mathbf{c}_0$: the error event is the union, over every $\mathbf{c} \ne \mathbf{c}_0$, of the pairwise events just computed. Boole’s inequality bounds the probability of a union by the sum of the individual probabilities,

$P_e = \Pr\!\left[\bigcup_{\mathbf{c} \ne \mathbf{c}_0} \{\mathbf{c} \text{ preferred over } \mathbf{c}_0\}\right] \le \sum_{\mathbf{c} \ne \mathbf{c}_0} \Pr[\mathbf{c} \text{ preferred over } \mathbf{c}_0] = \sum_{\mathbf{c} \ne \mathbf{c}_0} Q\!\left(\sqrt{2\, d(\mathbf{c},\mathbf{c}_0)\, R\, \frac{E_b}{N_0}}\right). \qquad \blacksquare$

At high SNR the nearest codewords dominate this sum, which is precisely why $d_{\min}$ rules the high-SNR regime; at low SNR the bound goes slack, which is an early hint that a different kind of analysis will be needed there. Both halves of that observation drive the series.

Log-Likelihood Ratios

All three decoders in this series traffic in the same quantity, so it deserves its own introduction. The log-likelihood ratio of a bit $x$ is

$$L(x) = \ln \frac{\Pr[x=0]}{\Pr[x=1]},$$

and its two components carry the two things a decoder can know about a bit. The sign is the hard decision: $L > 0$ favours bit $0$, $L < 0$ favours bit $1$. The magnitude is the confidence: $|L| = 4$ is a near-certainty, $|L| = 0.1$ is barely better than a coin flip, and $L = 0$ is total ignorance. Everything the turbo, LDPC, and polar-list decoders do can be read as arithmetic on these two components: combining independent pieces of evidence adds LLRs, and the various message-passing update rules are just careful bookkeeping about which evidence may be added where. LLRs are the working currency of this entire series; when in doubt about what a decoder equation means, translate it back into “sign is the vote, magnitude is the conviction.”

Now for the trap, and it is worth flagging in bold because it is the single most common source of confusion when reading across papers: two opposite sign conventions coexist in the literature. These notes use $L(x) = \ln \Pr[x=0]/\Pr[x=1]$ throughout, so positive LLR means bit $0$; under the standard BPSK mapping $0 \mapsto +1$, $1 \mapsto -1$, positive LLR also means the transmitted symbol was $+1$. Plenty of papers put $\Pr[x=1]$ on top instead, which silently negates every equation. If a formula from an external source disagrees with one here by an overall sign, check the convention before checking the algebra. (The original sources have their own quirks too: Gallager’s 1963 thesis works in raw probabilities rather than LLRs, and Arıkan’s 2009 paper uses likelihood ratios rather than their logarithms; the relevant pages of this series translate as needed.)

One concrete LLR appears so often it should be memorized. For the BI-AWGN channel with transmitted amplitude $a$, noise variance $\sigma^2$, and received sample $y$, the channel LLR is exactly linear in the observation:

$$L_{\text{ch}}(y) = \frac{2a}{\sigma^2}\, y = L_c\, y, \qquad L_c \triangleq \frac{2a}{\sigma^2}.$$

The received value itself is the evidence; the channel reliability $L_c$ just scales it. A strongly positive $y$ through a clean channel yields a large positive LLR, and the same $y$ through a noisy channel yields a timid one. Every decoder in this series takes $L_{\text{ch}}$ as its raw input.

Performance Metrics and Terminology

The three families will be judged against each other constantly, so the judging language needs to be precise from the start. A coded system’s error-rate curve, plotted against SNR, has two characteristic regions. The waterfall region (or cliff) is the SNR range where the error rate plunges steeply, often by orders of magnitude within a fraction of a dB. The error floor is the flattening that can appear at high SNR, where the curve stops plunging and settles into a shallow slope. These two regions are governed by different properties of the code. The waterfall is governed by the threshold: the worst channel parameter for which the iterative decoder’s error probability can be driven to zero as the block length and iteration count both grow without bound. A threshold is an asymptotic quantity; a finite-length code approaches it but never reaches it. The floor, by contrast, is governed by the code’s low-weight codewords and similar small weak spots, which is to say by $d_{\min}$ and its friends, exactly as the union bound predicted.

Here is the trap worth internalizing now, because it will save you from misreading half the plots in this field: threshold and minimum distance are independent knobs. A code can have a wonderful threshold and a terrible floor, or a mediocre threshold and a floor too low to measure. Turbo codes are the classic example: a spectacular waterfall startlingly close to capacity, and a clearly visible floor caused by a small population of low-weight codewords. Forney’s remark, quoted by Benedetto and Montorsi, captures how thoroughly this scrambled the field’s instincts: “Turbo codes seem to turn the conventional design principles on their head; they make error coefficients more important than minimum distance!” The error coefficient (how many bad codewords there are) had always been a second-order correction to the distance (how far away they are); turbo codes inverted that priority, and the notion of interleaver gain, the factor by which the error coefficient shrinks as the interleaver grows, will make the inversion quantitative when the series reaches the turbo pages.

Two more terms round out the vocabulary. Coding gain is the honest bottom line: the dB of $E_b/N_0$ saved at a fixed error rate compared with uncoded transmission. And a final bookkeeping trap: BLER versus BER. Block (frame) error rate counts a block as wrong if any bit in it is wrong; bit error rate counts wrong bits. The polar literature habitually plots BLER, the turbo literature habitually plots BER, and the two can differ by orders of magnitude for the same system. Never compare curves across that distinction without converting.

Organization of This Series

Three families, three tricks, and yet by the end of the series a single picture will hold them all: every decoder we study is message passing on a factor graph, and the families differ only in the graph’s shape and the schedule of the messages. The LDPC graph is sparse, random, and locally tree-like, and its decoder floods messages between all nodes in parallel. The turbo “graph” is two strong trellis codes tied through an interleaver into one enormous cycle, and its decoder alternates between the two halves, exchanging carefully filtered soft information. The polar graph is a rigid butterfly network of $N \log N$ nodes, and its basic decoder passes messages in one fixed sequential order. Same mathematics, three geometries. The chronological route the series takes runs from Gallager’s 1963 thesis, through the 1993 turbo shock (the turbo pages) and the rediscovery and modern analysis of LDPC codes (density evolution), to Arıkan’s polar codes (capacity by construction) and the list-decoding refinements that carried all of this into deployed silicon, where the finale weighs the families against each other in practice.

Check Yourself

1. Shannon proved that random codes achieve capacity. Name the two distinct reasons they are useless in practice, and say which operation each reason breaks.
2. Under this series’ sign convention, a decoder holds $L(x) = -3.1$ for some bit. What is the hard decision, what does the magnitude tell you, and what BPSK symbol does the decision correspond to?
3. A paper you are reading gives the AWGN channel LLR as $L_{\text{ch}}(y) = -\tfrac{2a}{\sigma^2} y$. Is the paper wrong?
4. Your colleague claims: “This code’s density-evolution threshold is nearly at capacity, so its error floor must be very low too.” What is wrong with the inference, and which code family is the classic counterexample?
5. All three modern code families use decoders that are provably not maximum-likelihood. Why did this turn out not to matter?
6. You are comparing a polar-code plot against a turbo-code plot from different papers and the polar curve looks an order of magnitude worse at the same SNR. What should you check before concluding anything?

Answers

1. Construction and decoding. A random code has no compact description, so encoding/storage requires keeping all $2^k$ codewords explicitly; and with no structure to exploit, decoding by maximum likelihood requires an $O(2^k)$ search over all of them. Either one alone is fatal for realistic $k$.

2. The sign is negative, so the hard decision is bit $1$ (this series puts $\Pr[x=0]$ in the numerator, so negative favours $1$). The magnitude $3.1$ says the decoder is quite confident, corresponding to roughly $\Pr[x=1] \approx 0.96$. Under the mapping $0 \mapsto +1$, $1 \mapsto -1$, the decision corresponds to transmitted symbol $-1$.

3. Not necessarily. It is almost certainly using the opposite LLR convention, $L(x) = \ln \Pr[x=1]/\Pr[x=0]$, which negates every LLR expression. Check the paper’s definition before hunting for an algebra error; mixed sign conventions are the single most common source of confusion when reading across the literature.

4. Threshold and minimum distance are independent knobs. The threshold governs the waterfall region (where the cliff sits); the error floor is governed by low-weight codewords, i.e. by minimum distance and error coefficients. A code can have a near-capacity threshold and a high floor at the same time. Turbo codes are the classic example: spectacular waterfall, visible floor, which is what prompted Forney’s remark that turbo codes make error coefficients more important than minimum distance.

5. Empirically, the gap between these suboptimal decoders and true ML decoding proved negligible: belief propagation on loopy LDPC graphs, iterative turbo decoding, and (list-augmented) successive cancellation all land close enough to ML that the lost performance is a rounding error next to the gain from being computationally feasible at all. Tractability turned out to cost almost nothing.

6. Check what each axis actually plots. Polar papers usually report block error rate (BLER), turbo papers usually report bit error rate (BER), and BLER is always at least as large as BER for the same system, often by orders of magnitude. Curves across that distinction are not comparable without conversion.

Where This Leaves Us

The stage is set: Shannon guaranteed that capacity is reachable, his random-coding proof left both construction and decoding unsolved, and the field spent decades believing that the structure needed for decodability necessarily forfeited performance. You now hold the toolkit the series assumes (linear and convolutional codes, the three channel models, LLRs with this series’ sign convention, the union bound) and the vocabulary for judging what follows, including the crucial independence of threshold and minimum distance. The next entry rewinds to 1963, when a doctoral student named Robert Gallager quietly wrote down sparse random parity-check matrices and an iterative decoder to go with them, essentially solving the problem thirty years early, only for the work to be shelved as impractical and forgotten. Gallager’s Sparse Graphs picks up there.