Contents / Information Theory / Modern Codes: LDPC, Polar and Turbo

Chapter 9

Modern Codes: LDPC, Polar and Turbo

The sparse-graph and polarization constructions that finally reach capacity in practice, and how they are decoded.

Introduction

The sparse-graph and polarization constructions that finally reach capacity in practice, and how they are decoded.

9.1LDPC Codes: Sparsity and Ensembles

Hamming's codes are optimal packings but hopeless at capacity: their distance does not grow with the block length. Shannon's argument says that long random codes are excellent — the problem is decoding them. Robert Gallager's 1963 thesis found the resolution: choose the parity-check matrix at random but sparse, so that the code is still essentially random, yet the constraints are local enough to be resolved by a message-passing algorithm. The idea was forgotten for thirty years, rediscovered by MacKay and Neal in the mid-1990s, and is now in Wi-Fi, DVB-S2, 5G data channels and every hard-disk controller.

Definition 9.1 (LDPC code). An LDPC code is a binary linear code specified by a parity-check matrix $H$ of size $m\times n$ that is sparse: the number of ones per row and per column is bounded by a constant independent of $n$ . The code is the null space,

\mathcal C = \{\mathbf c \in \mathbb F_2^n : H \mathbf c^{\mathsf T} = \mathbf 0\}.

It is $(d_v,d_c)$ -regular if every column has exactly $d_v$ ones and every row exactly $d_c$ .

Proposition 9.2 (Design rate of a regular ensemble). A $(d_v,d_c)$ -regular parity-check matrix satisfies $n d_v = m d_c$ , and the code it defines has rate

R = 1 - \frac mn \ge 1 - \frac{d_v}{d_c},

with equality if and only if $H$ has full row rank.

Proof. Count the ones of $H$ twice: by columns, $n d_v$ ; by rows, $m d_c$ . Hence $m/n = d_v/d_c$ . The dimension of the null space is $n - \mathrm{rank}(H) \ge n - m$ , giving $R \ge 1 - m/n$ , with equality exactly when the rows are independent.∎

The inequality is not pedantry: a random sparse $H$ usually has a few dependent rows, so the true rate slightly exceeds the design rate. Standards fix this by using structured (quasi-cyclic) matrices whose rank is known.

Definition 9.3 (Degree distributions). An irregular LDPC ensemble is described from the edge perspective by

\lambda(x) = \sum_{i\ge2}\lambda_i x^{i-1}, \qquad \rho(x) = \sum_{j\ge2}\rho_j x^{j-1},

where $\lambda_i$ (resp. $\rho_j$ ) is the fraction of edges incident to a variable node of degree $i$ (resp. a check node of degree $j$ ). The design rate is $R = 1 - \frac{\int_0^1\rho}{\int_0^1\lambda}$ .

Intuition. Think of a huge crossword in which every clue involves only a handful of letters and every letter appears in only a handful of clues. No clue determines its letters by itself, but because the clues overlap sparsely, information propagates: solving a few letters unlocks neighbouring clues, and the puzzle unzips. Density is the enemy — a check involving half the bits tells you almost nothing about any one of them.

Theorem 9.4 (Good LDPC ensembles have linearly growing distance). For a $(d_v,d_c)$ -regular ensemble with $d_v \ge 3$ , there is a constant $\delta(d_v,d_c) > 0$ such that a randomly chosen code from the ensemble has minimum distance at least $\delta n$ with probability tending to $1$ as $n \to\infty$ .

Proof. Sketch. A first-moment (union) bound. For each weight $w = \gamma n$ one computes the expected number of codewords of weight $w$ in the ensemble, which is the number of ways of choosing the support, $\binom{n}{w}$ , times the probability that the $w d_v$ edges leaving the support pair up so that every check sees an even number of them. For $d_v\ge3$ that probability decays fast enough that the expectation is exponentially small for all $\gamma$ below some $\delta$ , and Markov's inequality then says almost no code in the ensemble has such a codeword. The case $d_v = 2$ genuinely fails: the code is then a cycle code, with minimum distance $O(\log n)$ . The full computation is in Gallager's thesis; we use only the conclusion.∎

Example 9.5 (A small regular ensemble). Describe the $(3,6)$ -regular LDPC matrix for $n=12$ and check its consistency.

Solution. Design rate $1 - 3/6 = 1/2$ , so $m = n(1-R) = 6$ and $H$ is $6\times 12$ . Counting ones by columns gives $12\times3 = 36$ ; by rows, $6\times6 = 36$ — consistent, as the proposition requires. So $36$ of the $72$ entries are ones; at $n=12$ this is hardly "low density", and it illustrates that sparsity is an asymptotic notion: at $n = 64800$ (DVB-S2) the same degrees leave the matrix $99.99\%$ zeros.□

Pitfall. Sparsity of $H$ does not mean the code is weak or the generator matrix is sparse. $G$ for an LDPC code is typically dense, which is why encoding is done by back-substitution on an approximately lower-triangular $H$ , or by using a quasi-cyclic structure, rather than by multiplying by $G$ .

Exercises for §9.1 →

9.2Tanner Graphs and Belief Propagation

Definition 9.6 (Tanner graph). The Tanner graph of a code with parity-check matrix $H$ is the bipartite graph with $n$ variable nodes (one per coordinate), $m$ check nodes (one per row), and an edge between variable $i$ and check $j$ exactly when $H_{ji} = 1$ . The girth is the length of its shortest cycle.

Decoding is inference on this graph: given the channel observations, compute (or approximate) the posterior probability of each bit, subject to all parity constraints.

Definition 9.7 (Log-likelihood ratio). The LLR of a bit $b$ given an observation $y$ is

L(b) = \log\frac{\Pr[b = 0\mid y]}{\Pr[b=1\mid y]}.

A positive LLR favours $0$ ; the magnitude is the strength of the belief. On $\mathrm{BSC}(p)$ a received $0$ carries $L = \log\frac{1-p}{p}$ ; on a BI-AWGN channel with $\pm1$ signalling, $L = 2y/\sigma^{2}$ .

Theorem 9.8 (Sum-product update rules). In belief propagation on a Tanner graph, with $L_{\mathrm{ch}}(i)$ the channel LLR of bit $i$ , the extrinsic messages are

L_{i\to j} = L_{\mathrm{ch}}(i) + \sum_{j'\in N(i)\setminus\{j\}} L_{j'\to i}, \qquad \tanh\frac{L_{j\to i}}{2} = \prod_{i'\in N(j)\setminus\{i\}} \tanh \frac{L_{i'\to j}}{2}.

The final belief at variable $i$ is $L_i = L_{\mathrm{ch}}(i) + \sum_{j\in N(i)} L_{j\to i}$ .

Proof. Variable rule. Conditioned on the bit value, the incoming pieces of evidence are independent (in a cycle-free graph they come from disjoint subtrees), so their likelihood ratios multiply and their log-likelihood ratios add. Excluding $L_{j\to i}$ from the message sent back to $j$ is what makes the message extrinsic: it carries only evidence $j$ has not already supplied.

Check rule. Let $b_1,\dots,b_k$ be independent bits with $\Pr[b_t = 1] = q_t$ , and let $L_t = \log\frac{1-q_t}{q_t}$ . A standard identity gives $\tanh(L_t/2) = 1-2q_t$ . For the parity $b_1\oplus\cdots\oplus b_k$ , the probability of an even sum satisfies

\Pr[\oplus_t b_t = 0] = \frac12\left(1 + \prod_{t=1}^k (1-2q_t)\right),

which is proved by expanding the product of the generating factors $(1-2q_t)$ , or by induction on $k$ using $\Pr[\text{even}] = \Pr[\text{even}']\,(1-q_k) + \Pr[\text{odd}']q_k$ . Writing the left-hand side as $\frac12(1 + \tanh(L/2))$ where $L$ is the LLR of the parity bit and substituting $1-2q_t = \tanh(L_t/2)$ gives exactly the stated product rule.∎

Corollary 9.9 (Exactness on trees). If the Tanner graph is a tree, belief propagation converges after a number of iterations equal to the tree's diameter, and its output is the exact bitwise a posteriori probability. On a graph with cycles it is an approximation whose fixed points need not be the true posterior.

Proof. On a tree, removing a node's edge to a neighbour splits the graph into disjoint components, so the messages entering along different edges are functions of disjoint sets of observations and are conditionally independent given the bit. The update rules are then exact applications of Bayes' rule, and a single sweep from the leaves inward and back out computes every marginal exactly. Cycles destroy the independence, and the same evidence can circulate and be counted twice.∎

Remark (Why cycles are tolerable). For a random sparse graph, the neighbourhood of a given node within radius $\ell$ is a tree with probability $1-O(1/n)$ . So for a fixed number of iterations the algorithm is asymptotically running on a tree, which is exactly what makes the density-evolution analysis of the next section rigorous. Short cycles hurt at finite length, and constructions such as progressive edge growth and protographs exist to push the girth up.

Example 9.10 (One variable-node update). Variable $v_1$ has channel LLR $L_{\mathrm{ch}} = +2.0$ and is connected to checks $c_2, c_4$ , which send $L_{2\to1} = +1.5$ and $L_{4\to1} = -0.8$ . Compute the belief and both outgoing messages.

Solution. Belief: $L_1 = 2.0 + 1.5 - 0.8 = +2.7$ , so $v_1$ currently favours $0$ .

Message to $c_2$ (excluding $c_2$ 's own message): $L_{1\to2} = 2.0 + (-0.8) = +1.2$ .

Message to $c_4$ : $L_{1\to4} = 2.0 + 1.5 = +3.5$ .

Each outgoing message omits the recipient's contribution. Including it would return the check's own opinion to it and let a single observation be counted repeatedly around the graph.□

Example 9.11 (One check-node update, exactly and by min-sum). Check $c$ has three other neighbours sending $L = +1.2,\ -0.8,\ +3.5$ . Compute its outgoing message exactly and by the min-sum approximation.

Solution. Exact: $\tanh(0.6) = 0.5370$ , $\tanh(-0.4) = -0.3799$ , $\tanh(1.75) = 0.9414$ . The product is $0.5370 \times (-0.3799)\times 0.9414 = -0.1921$ . Then $L_{c\to} = 2\,\mathrm{artanh}(-0.1921) = -0.3886$ .

Min-sum: the sign is the product of signs, $(+)(-)(+) = -$ ; the magnitude is approximated by the smallest incoming magnitude, $0.8$ . So min-sum gives $-0.8$ , the right sign and an optimistic magnitude — which is why implementations scale it by a factor around $0.75$ .

Note how the exact magnitude $0.39$ is smaller than every incoming magnitude: a parity check is only as confident as its least confident member, because one uncertain bit makes the parity of the rest uncertain.□

Exercises for §9.2 →

9.3Density Evolution, Thresholds and Error Floors

The remarkable feature of LDPC codes is that their asymptotic performance can be computed exactly. Because the local neighbourhood of a node is a tree with high probability, the fraction of erroneous messages evolves according to a deterministic one-dimensional recursion.

Definition 9.12 (Decoding threshold). For an ensemble and a family of channels ordered by a noise parameter $\varepsilon$ , the threshold $\varepsilon^{*}$ is the supremum of noise levels for which the expected fraction of incorrect messages tends to $0$ as the number of iterations and the block length grow.

Theorem 9.13 (Density evolution on the BEC). Consider an irregular ensemble with edge degree distributions $\lambda,\rho$ used on $\mathrm{BEC}(\varepsilon)$ with the peeling (message-passing) decoder. Let $x_\ell$ be the probability that a variable-to-check message is an erasure after $\ell$ iterations. Then $x_0 = \varepsilon$ and

x_{\ell+1} = \varepsilon\,\lambda\big(1 - \rho(1-x_\ell)\big).

The decoder succeeds asymptotically if and only if $\varepsilon\,\lambda(1-\rho(1-x)) < x$ for all $x \in (0,\varepsilon]$ , and the threshold is the largest $\varepsilon$ for which this holds.

Proof. Work in the tree-like local neighbourhood, where all incoming messages are independent.

Check to variable. A check-to-variable message is known (not an erasure) precisely when every other message into that check is known. For a check of degree $j$ this has probability $(1-x_\ell)^{j-1}$ , and averaging over the edge-perspective distribution gives $\rho(1-x_\ell)$ . So a check-to-variable message is an erasure with probability $1-\rho(1-x_\ell)$ .

Variable to check. A variable-to-check message is an erasure precisely when the channel erased the bit and every other incoming check message is an erasure. For a variable of degree $i$ that probability is $\varepsilon\big(1-\rho(1-x_\ell)\big)^{i-1}$ ; averaging over $\lambda$ gives the recursion.

The recursion is monotone increasing in $x$ and $x_{\ell}$ is non-increasing in $\ell$ when it starts at $\varepsilon$ , so it converges to the largest fixed point below $\varepsilon$ . Convergence to $0$ therefore holds exactly when no fixed point exists in $(0,\varepsilon]$ , which is the stated strict-inequality condition.∎

Example 9.14 (Threshold of the $(3,6)$ ensemble on the BEC). Compute the recursion for the regular $(3,6)$ code and estimate its threshold; compare with capacity.

Solution. Regular degrees mean $\lambda(x) = x^{2}$ and $\rho(x) = x^{5}$ , so

x_{\ell+1} = \varepsilon\left(1-(1-x_\ell)^5\right)^{2}.

At $\varepsilon = 0.5$ the map has a fixed point near $x \approx 0.45$ (since $0.5(1-0.55^5)^2 = 0.451$ ), so the decoder stalls there and never clears the block. At $\varepsilon = 0.4$ iterating from $x_0 = 0.4$ gives $0.4(1-0.6^5)^2 = 0.4(0.9222)^2 = 0.340$ , then $0.4(1-0.66^5)^2 = 0.4(0.8748)^2 = 0.306$ , then $0.282$ , $0.262,\dots$ , decreasing steadily to $0$ . The true threshold is $\varepsilon^{*} \approx 0.4294$ , against the capacity limit $\varepsilon = 1 - R = 0.5$ . Irregular ensembles close most of that gap; optimised degree distributions reach $\varepsilon^{*} > 0.499$ .□

Figure 9.15. Density evolution for the

(3,6)

-regular ensemble on

\mathrm{BEC}(0.4)

. The erasure fraction iterates under

x\mapsto 0.4(1-(1-x)^5)^2

; because the curve stays strictly below the diagonal on

(0, 0.4]

, the iteration slides down to

0

and the block decodes. At

\varepsilon = 0.5

the same curve crosses the diagonal near

x=0.45

and the decoder stalls there.

Theorem 9.16 (Stability condition). A necessary condition for the threshold of an ensemble on $\mathrm{BEC}(\varepsilon)$ to be at least $\varepsilon$ is

\varepsilon\,\lambda'(0)\rho'(1) \le 1, \qquad \text{that is} \quad \varepsilon\,\lambda_2 (d_c-1)\le 1 \text{ in the check-regular case}.

Proof. Linearise the density-evolution recursion at $x=0$ . Writing $f(x) = \varepsilon\lambda(1-\rho(1-x))$ , the chain rule gives $f'(0) = \varepsilon \lambda'(0)\rho'(1)$ . If $f'(0) > 1$ then $f(x) > x$ for small positive $x$ , so a fixed point exists arbitrarily close to $0$ and the erasure fraction cannot be driven to zero.∎

The stability condition explains why good irregular ensembles keep the fraction of degree-2 variable nodes small but nonzero: degree-2 nodes speed up the waterfall but, in excess, stall the endgame.

Remark (Error floors and trapping sets). Density evolution describes the waterfall: the steep fall of error rate just below threshold. At high SNR a different mechanism dominates. Small subgraphs — near-codewords, absorbing sets, trapping sets — can hold the decoder in a stable wrong configuration even though the code's true minimum distance is large. The resulting error floor is a plateau in the error-rate curve, and it is a finite-length, decoder-specific phenomenon that density evolution cannot see. Standards mitigate it with girth-optimised constructions and an outer CRC or BCH code.

Intuition. Think of the BEC decoder as unzipping: find a check with exactly one unknown bit, solve it, repeat. Density evolution tracks the fraction of bits still unknown. Below threshold the unzipping never runs out of solvable checks and the whole block resolves; above threshold it jams on a stuck subgraph — a set of bits whose checks each contain at least two of them — and stops.

Example 9.17 (Complexity of message passing). Show that one iteration costs $O(n)$ operations for a fixed degree distribution, and comment on latency.

Solution. The number of edges is $E = n \bar d_v$ , with $\bar d_v$ the average variable degree, a constant. Each iteration performs $O(1)$ work per edge in both directions, so the cost is $\Theta(E) = \Theta(n)$ , and with $I$ iterations the total is $\Theta(In)$ — linear in the block length, unlike the $2^{k}$ of exhaustive maximum-likelihood decoding. The work is also fully parallel across edges, which is why LDPC decoders map so well onto hardware; the latency cost is the $I \approx 10$ to $50$ sequential iterations, mitigated in practice by layered scheduling that propagates information within an iteration.□

Exercises for §9.3 →

9.4Channel Polarization

LDPC and turbo codes approach capacity but do not provably attain it, and their analysis is asymptotic and ensemble-averaged. In 2009 Erdal Arıkan produced the first explicit construction with a proof: a deterministic family of codes, with encoding and decoding in $O(n\log n)$ , that achieves the symmetric capacity of any binary-input memoryless channel. The mechanism is a phenomenon he named channel polarization.

Definition 9.18 (Symmetric capacity and Bhattacharyya parameter). For a binary-input channel $W: \{0,1\}\to\mathcal Y$ , the symmetric capacity $I(W)$ is the mutual information with a uniform input, and the Bhattacharyya parameter is

Z(W) = \sum_{y\in\mathcal Y}\sqrt{W(y\mid 0)W(y\mid 1)} \in [0,1].

$Z(W)$ is an upper bound on the error probability of a maximum-likelihood decision between the two inputs on one use of $W$ ; $I(W)\approx1$ and $Z(W)\approx0$ mean a clean channel, $I(W)\approx0$ and $Z(W)\approx1$ a useless one.

Definition 9.19 (The basic polar transform). Given two independent copies of $W$ and inputs $(u_1,u_2)$ , set $x_1 = u_1\oplus u_2$ , $x_2 = u_2$ , and transmit $x_1,x_2$ . This defines two synthetic channels

W^-(y_1,y_2 \mid u_1) \quad\text{and}\quad W^{+}(y_1,y_2,u_1\mid u_2),

where $W^-$ decodes $u_1$ from the two outputs alone, and $W^{+}$ decodes $u_2$ from the two outputs and a known $u_1$ .

Theorem 9.20 (Conservation and polarization of one step). For any binary-input channel $W$ ,

I(W^-) + I(W^{+}) = 2I(W), \qquad I(W^-) \le I(W) \le I(W^{+}),

with equality in the second display if and only if $I(W) \in\{0,1\}$ .

Proof. The map $(u_1,u_2)\mapsto(x_1,x_2) = (u_1\oplus u_2, u_2)$ is a bijection on $\mathbb F_2^2$ , so with $(U_1,U_2)$ uniform and independent, $(X_1,X_2)$ is also uniform and independent, and $I(U_1,U_2;Y_1,Y_2) = I(X_1,X_2;Y_1,Y_2) = 2I(W)$ because the two uses are independent. The chain rule splits the left side:

I(U_1,U_2;Y_1,Y_2) = I(U_1;Y_1,Y_2) + I(U_2;Y_1,Y_2\mid U_1) = I(W^-) + I(W^{+}),

the two terms being exactly the symmetric capacities of the synthetic channels, since $U_1, U_2$ are uniform. That proves conservation.

For the ordering, note $I(W^{+}) = I(U_2; Y_1,Y_2\mid U_1) \ge I(U_2;Y_2) = I(W)$ : giving the decoder $U_1$ and the extra output $Y_1$ cannot hurt, and conditioning on the independent $U_1$ does not reduce the information here because $U_2$ is independent of $U_1$ . Conservation then forces $I(W^-) = 2I(W)-I(W^{+}) \le I(W)$ . Equality throughout requires $I(W^-)=I(W^+)$ , which happens only in the extreme cases $I(W)\in\{0,1\}$ .∎

Intuition. The transform takes two identical mediocre channels and makes one worse and one better, keeping the total constant. $u_1$ must be read through the interference of $u_2$ , so its channel degrades; $u_2$ , once $u_1$ is known, enjoys both observations, so its channel improves. Capacity is neither created nor destroyed — it is redistributed.

Proposition 9.21 (Erasure channels stay erasure channels). If $W = \mathrm{BEC}(\varepsilon)$ , then $W^{-} = \mathrm{BEC}(2\varepsilon-\varepsilon^{2})$ and $W^{+} = \mathrm{BEC}(\varepsilon^{2})$ .

Proof. For $W^-$ : $u_1 = x_1 \oplus x_2$ can be recovered iff both $x_1$ and $x_2$ arrive, so it is erased with probability $1-(1-\varepsilon)^2 = 2\varepsilon - \varepsilon^{2}$ . For $W^{+}$ : knowing $u_1$ , the value $u_2$ can be recovered from $x_2$ alone or from $x_1 = u_1\oplus u_2$ alone, so it is erased only if both are erased, which has probability $\varepsilon^{2}$ . Both synthetic channels are still erasure channels because the outputs are either fully informative or entirely uninformative. Note $(2\varepsilon-\varepsilon^{2}) + \varepsilon^{2} = 2\varepsilon$ , i.e. $I(W^-)+I(W^+) = 2(1-\varepsilon)$ , in accordance with conservation.∎

Definition 9.22 (Recursive construction). Apply the transform recursively. For $n = 2^m$ , the $n$ synthetic channels $W_n^{(i)}$ , $i=1,\dots,n$ , are obtained by $m$ levels of the basic transform; in the notation above, $W_{2n}^{(2i-1)} = (W_n^{(i)})^{-}$ and $W_{2n}^{(2i)} = (W_n^{(i)})^{+}$ .

Theorem 9.23 (Channel polarization, Arıkan 2009). For any binary-input memoryless channel $W$ and any $\delta\in(0,1)$ , as $n = 2^m \to\infty$ ,

\frac{\left|\{i : I(W_n^{(i)}) > 1-\delta\}\right|}{n} \longrightarrow I(W), \qquad \frac{\left|\{i: I(W_n^{(i)}) < \delta\}\right|}{n}\longrightarrow 1 - I(W).

The fraction of synthetic channels that are neither almost perfect nor almost useless tends to zero.

Proof. Sketch. Let $B_1,B_2,\dots$ be i.i.d. fair bits choosing the $-$ or $+$ branch at each level, and let $I_m = I(W_m)$ be the symmetric capacity of the synthetic channel reached after $m$ steps. Conservation, $I(W^-)+I(W^{+}) = 2I(W)$ , says precisely that

\mathbb E[I_{m+1}\mid I_1,\dots,I_m] = \tfrac12 I(W^-) + \tfrac12 I(W^{+}) = I_m,

so $\{I_m\}$ is a bounded martingale and converges almost surely to some $I_\infty$ , with $\mathbb E[I_\infty] = I(W)$ . The remaining step shows $I_\infty \in \{0,1\}$ almost surely: martingale convergence forces $|I_{m+1}-I_m|\to0$ , while a separate estimate shows that one step moves the capacity by a definite amount unless the channel is already nearly extremal. Since $I_\infty$ takes only the values $0$ and $1$ and has mean $I(W)$ , it equals $1$ with probability exactly $I(W)$ , which is the statement. The quantitative step — that a non-extremal channel polarises at a definite rate — is the technical core of Arıkan's paper and we do not reproduce it.∎

Example 9.24 (Polarization on the BEC, by hand). Start with $\mathrm{BEC}(0.5)$ and run two levels of the recursion, listing the four erasure probabilities.

Solution. Level 1: $\varepsilon^- = 2(0.5)-0.25 = 0.75$ and $\varepsilon^{+} = 0.25$ .

Level 2, applying the same rules to each:

from $0.75$ : $2(0.75)-0.5625 = 0.9375$ and $0.5625$ ;
from $0.25$ : $2(0.25) - 0.0625 = 0.4375$ and $0.0625$ .

So the four synthetic channels have erasure probabilities $0.9375,\ 0.5625,\ 0.4375,\ 0.0625$ — already spreading toward the extremes. Their average is $(0.9375+0.5625+0.4375+0.0625)/4 = 0.5$ , confirming conservation. After $m=10$ levels the great majority of the $1024$ channels sit within $10^{-3}$ of $0$ or $1$ .□

Figure 9.25. Three levels of polarization starting from

\mathrm{BEC}(0.5)

: the erasure probabilities of the eight synthetic channels, sorted by index. Four are heading toward

1

(useless) and four toward

0

(perfect), and their average stays at

0.5

— capacity is redistributed, never created. A polar code of rate

1/2

puts data on indices

4,6,7,8

and freezes the rest.

Exercises for §9.4 →

9.5Construction and Encoding

Polarization hands us $n$ synthetic channels, some nearly perfect and some nearly useless. The code writes data on the good ones and fixes the bad ones to values the decoder already knows.

Definition 9.26 (Polar transform matrix). With $F = \begin{bmatrix}1&0\\1&1\end{bmatrix}$ , the polar transform of length $n=2^m$ is the Kronecker power $G_n = F^{\otimes m}$ (composed with a bit-reversal permutation in Arıkan's original presentation). Encoding is

\mathbf x = \mathbf u\,G_n.

Definition 9.27 (Polar code). Fix a rate $k/n$ . Choose the information set $A \subseteq \{1,\dots,n\}$ with $|A| = k$ to consist of the indices of the $k$ synthetic channels with the smallest Bhattacharyya parameters $Z(W_n^{(i)})$ . The frozen set is $A^{c}$ , and $u_{A^c}$ is fixed to a value known to both ends (usually $\mathbf 0$ ). The codeword is $\mathbf x = \mathbf u G_n$ with $u_A$ carrying the message.

Theorem 9.28 (Encoding complexity). $\mathbf u \mapsto \mathbf u G_n$ can be computed with $\frac n2\log n$ binary additions, i.e. in $O(n\log n)$ time and $O(n)$ space.

Proof. Write $T(n)$ for the cost. The Kronecker structure $G_{2n} = \begin{bmatrix}G_n & 0\\ G_n & G_n\end{bmatrix}$ (up to the standard index permutation) means the length- $2n$ transform consists of $n$ XORs combining the two halves followed by two independent length- $n$ transforms, so $T(2n) = 2T(n) + n$ with $T(1) = 0$ . By induction $T(n) = \frac n2\log n$ : indeed if $T(n) = \frac n2 \log n$ then $T(2n) = n\log n + n = \frac{2n}{2}\log(2n)$ . This is the butterfly structure of the fast Hadamard transform.∎

Proposition 9.29 (Polar codes are linear, and their rate). A polar code is the linear code generated by the rows of $G_n$ indexed by $A$ , so it is an $[n,k]$ linear code of rate $k/n$ when the frozen values are zero.

Proof. With $u_{A^c} = \mathbf 0$ , $\mathbf x = \mathbf u G_n = \sum_{i\in A}u_i (G_n)_{i,\cdot}$ , a linear span of $|A| = k$ rows. The rows of $G_n$ are linearly independent because $G_n = F^{\otimes m}$ and $F$ is invertible over $\mathbb F_2$ (indeed $F^{2} = I$ ), so $G_n$ is invertible and its $k$ selected rows are independent.∎

Remark (Choosing the frozen set). For the BEC the parameters $Z(W_n^{(i)})$ follow the exact recursion of the erasure proposition, so the information set is computable in $O(n)$ arithmetic. For general channels one uses density evolution on quantised distributions, the Gaussian approximation, or — as in 5G — a single fixed reliability sequence tabulated once and nested across lengths. Note that the good set depends on the channel quality, so a polar code designed for one SNR is slightly mismatched at another.

Example 9.30 (A length-8 polar code). Take $\mathrm{BEC}(0.5)$ , $n=8$ , $k=4$ . Determine the information set.

Solution. Apply the erasure recursion three times. From $0.5$ : level 1 gives $(0.75, 0.25)$ ; level 2 gives $(0.9375, 0.5625, 0.4375, 0.0625)$ ; level 3 gives

(0.99609,\ 0.87891,\ 0.80859,\ 0.31641,\ 0.68359,\ 0.19141,\ 0.12109,\ 0.00391).

The four smallest erasure probabilities are at indices $8, 7, 6, 4$ , so $A = \{4,6,7,8\}$ and the frozen set is $\{1,2,3,5\}$ . The average of the eight numbers is $0.5$ , as conservation demands. Note that the good indices are the ones with many $+$ branches in their binary expansion — the pattern that the 5G reliability sequence tabulates once and for all.□

Pitfall. Frozen bits are not wasted parity; they are positions whose value is known in advance to the decoder. That knowledge is what the successive-cancellation decoder leans on. Setting them to random-but-known values works equally well on a symmetric channel; setting them to values the decoder does not know destroys the code.

Exercises for §9.5 →

9.6Successive Cancellation Decoding

The decoder mirrors the encoder's recursion, deciding $u_1,u_2,\dots,u_n$ in order and using each decision as known side information for the next.

Method 9.31 (Successive cancellation decoding). For $i = 1,\dots,n$ :

If $i \in A^{c}$ , set $\hat u_i$ to the known frozen value.
Otherwise compute the LLR $L_n^{(i)}(y^n, \hat u^{i-1})$ of the $i$ -th synthetic channel, using the recursive butterfly, and set $\hat u_i = 0$ if $L_n^{(i)} > 0$ and $1$ otherwise.

Proposition 9.32 (LLR recursions). Writing $L^{-}$ and $L^{+}$ for the LLRs of the two synthetic channels built from LLRs $L_1$ and $L_2$ , and $\hat u_1$ for the earlier decision,

L^{-} = 2\,\mathrm{artanh}\!\left(\tanh\frac{L_1}{2}\tanh\frac{L_2}{2}\right), \qquad L^{+} = L_2 + (-1)^{\hat u_1}L_1.

Proof. For $L^{-}$ : $u_1 = x_1\oplus x_2$ is a parity of two independently observed bits, so the check-node (box-plus) rule proved in the LDPC section applies verbatim. For $L^{+}$ : given $u_1$ , the observation $y_1$ is a noisy version of $x_1 = u_1\oplus u_2$ , so it is evidence about $u_2$ with the sign of its LLR flipped when $u_1 = 1$ , while $y_2$ is direct evidence about $x_2 = u_2$ . Independent evidence adds in the LLR domain, giving the stated sum.∎

Theorem 9.33 (Decoding complexity). Successive cancellation decoding of a length- $n$ polar code costs $O(n\log n)$ operations.

Proof. Let $D(n)$ be the cost of decoding all $n$ bits. The recursion computes, from the $n$ channel LLRs, two length- $n/2$ decoding problems — one for the odd-indexed ("minus") branch, one for the even ("plus") branch — each preceded by $n/2$ combining operations, and the plus branch reuses the already decided bits. So $D(n) = 2D(n/2) + O(n)$ , with $D(1) = O(1)$ , and the master theorem gives $D(n) = O(n\log n)$ .∎

Theorem 9.34 (Block error bound). Under successive cancellation with genie-free decoding, the block error probability of a polar code with information set $A$ satisfies

P_e \le \sum_{i\in A} Z\big(W_n^{(i)}\big).

Proof. Sketch. Consider the first index at which the decoder errs. Conditioned on all previous decisions being correct, the decision on $u_i$ is a maximum-likelihood binary decision on the synthetic channel $W_n^{(i)}$ , whose error probability is at most $Z(W_n^{(i)})$ — the standard Bhattacharyya bound on the error of a binary hypothesis test. Union bounding over $i\in A$ gives the claim. Arıkan's rate-of-polarization theorem then shows that for any $R<I(W)$ one can choose $A$ with $\sum_{i\in A}Z(W_n^{(i)}) = O(2^{-\sqrt n})$ , which is what makes polar codes capacity-achieving.∎

Example 9.35 (Decoding a length-2 polar code). Let $n=2$ with $u_1$ frozen to $0$ , so the code is $\{(0,0),(1,1)\}$ . The channel LLRs are $L_1 = +0.4$ and $L_2 = +3.0$ . Decode.

Solution. $u_1$ is frozen, so $\hat u_1 = 0$ without computation — which is fortunate, since its synthetic channel is the bad one: $L^{-} = 2\,\mathrm{artanh}(\tanh(0.2)\tanh(1.5)) = 2\,\mathrm{artanh}(0.1974\times0.9051) = 2\,\mathrm{artanh}(0.1787) = 0.361$ , a weak belief.

Then $L^{+} = L_2 + (-1)^{0}L_1 = 3.0+0.4 = 3.4$ , a strong belief, so $\hat u_2 = 0$ . The decoded codeword is $(0,0)$ .

Observe the polarization concretely: the two channel LLRs of magnitude $0.4$ and $3.0$ became a synthetic pair of magnitudes $0.36$ and $3.4$ — one worse than either, one better than both.□

Remark (SC list decoding). Plain SC is greedy: one early wrong decision is never revisited, and at short lengths it falls well short of maximum likelihood. SC list decoding keeps the $L$ most likely partial paths (typically $L = 8$ or $32$ ), doubling the list at each information bit and pruning; its complexity is $O(Ln\log n)$ . Concatenating a CRC over the information bits and selecting the surviving path that passes the CRC gives CRC-aided SCL, which at short lengths is close to the finite-length bounds and is what 5G actually deploys. The CRC here is not an error detector bolted on afterwards; it is part of the code.

Intuition. Successive cancellation is a relay race in a fixed order. Each runner may consult everything the earlier runners decided, and the positions have been chosen so that by the time a runner has to make a real decision, the accumulated information makes it nearly obvious. The weakness is that nobody checks the earlier runners' work — hence list decoding, which keeps several teams running and lets the CRC pick the winner at the end.

Exercises for §9.6 →

9.7Performance in Standards

Remark (Where polar codes stand). The honest summary is three claims, one asymptotic and two practical.

Asymptotically, polar codes are the first explicit, low-complexity family proved to achieve the symmetric capacity of any binary-input memoryless channel. That is a theorem, and it is what makes them a landmark.

At finite length, plain SC decoding is mediocre; polar codes became competitive only with CRC-aided list decoding, whose complexity is $L$ times larger. With $L=8$ and a CRC of $11$ to $24$ bits, at block lengths of a few hundred bits they match or beat LDPC and turbo codes and come within a few tenths of a dB of the finite-blocklength (normal-approximation) bound.

At long lengths and high rates, LDPC codes generally win on throughput per unit of silicon, because belief propagation is fully parallel while SC list decoding is inherently sequential across bits.

Example 9.36 (Polar codes in 5G New Radio). Summarise the deployment choices in 5G and why they follow from the theory.

Solution. 5G NR uses polar codes for the control channels — downlink control information (PDCCH), uplink control (PUCCH), and the broadcast channel — and LDPC codes for the data channel. The control payloads are short (tens to a few hundred bits) and must meet block error rates of $10^{-2}$ to $10^{-5}$ with very low latency, exactly the regime where CRC-aided SCL is strongest and where LDPC thresholds do not apply. Distributed CRC bits let the decoder prune list paths early, and a fixed nested reliability sequence avoids per-SNR construction. Rate matching by puncturing, shortening or repetition supports arbitrary lengths, since the natural lengths are only powers of two. The data channel, by contrast, carries long blocks at high throughput, which is where LDPC parallelism wins — so 5G runs both families, each where the theory says it belongs.□

Pitfall. "Capacity-achieving" is an asymptotic statement about a sequence of codes, not a claim about any particular block length. A length- $512$ polar code is not at capacity, and plain SC decoding of it is not even close; the gap is closed by list size, CRC and rate matching, all of which are finite-length engineering outside the theorem.

Exercises for §9.7 →

9.8Convolutional Codes and Turbo Concatenation

In 1993 Berrou, Glavieux and Thitimajshima reported bit error rates within half a decibel of the Shannon limit at rate $1/2$ — a claim so far beyond the state of the art that the audience largely disbelieved it until the simulations were reproduced. Their construction combined two ingredients that had been available for thirty years: convolutional codes, and the idea of exchanging soft information between decoders. We treat convolutional codes first, because turbo codes are built out of them and because the Viterbi algorithm is the cleanest example of decoding by dynamic programming.

Definition 9.37 (Convolutional encoder). A rate- $1/r$ binary convolutional encoder with constraint length $K$ maps an input stream $u_1,u_2,\dots$ to $r$ output streams by

v^{(j)}_t = \sum_{i=0}^{K-1} g^{(j)}_i\, u_{t-i} \pmod 2, \qquad j = 1,\dots,r,

a convolution of the input with fixed generator sequences $g^{(j)}$ . The encoder is a finite-state machine whose state is the contents of its $K-1$ memory cells, so it has $2^{K-1}$ states.

Definition 9.38 (Trellis and free distance). The trellis of a convolutional encoder is the graph whose nodes are (time, state) pairs and whose edges are the state transitions, labelled by the output symbols they emit. The free distance $d_{\mathrm{free}}$ is the minimum Hamming weight of any nonzero codeword, equivalently the minimum weight of any path that leaves the zero state and later returns to it.

Example 9.39 (The rate- $1/2$ , $K=3$ encoder). Describe the encoder with generators $g^{(1)} = (1,1,1)$ and $g^{(2)} = (1,0,1)$ , written in octal as $(7,5)$ , and find its free distance.

Solution. The state is $(u_{t-1},u_{t-2})$ , so there are $4$ states. On input $u_t$ the encoder emits $v^{(1)} = u_t\oplus u_{t-1}\oplus u_{t-2}$ and $v^{(2)} = u_t \oplus u_{t-2}$ .

For the free distance, drive the encoder with the input $1,0,0$ from the zero state: the outputs are $11$ , then $10$ , then $11$ , after which the encoder is back in state $00$ and emits zeros. The total weight is $2+1+2 = 5$ . No shorter or lighter excursion exists (a single-step excursion cannot return to zero, and the other short excursions have weight $\ge 6$ ), so $d_{\mathrm{free}} = 5$ . This encoder can therefore correct up to $\lfloor(5-1)/2\rfloor = 2$ errors within a constraint span, and it is the classic $(7,5)$ code used in countless textbooks and in the CCSDS convolutional standard's ancestor.□

Theorem 9.40 (Viterbi decoding is maximum likelihood, in linear time). For a convolutional code of $2^{K-1}$ states used over a memoryless channel for $T$ steps, the Viterbi algorithm returns a maximum-likelihood codeword using $O(T\,2^{K-1})$ operations and $O(2^{K-1})$ surviving paths.

Proof. Maximum-likelihood decoding maximises $\sum_{t} \log p(y_t \mid v_t)$ over paths through the trellis, an additive path metric. The key observation is the principle of optimality: if a maximum-metric path passes through state $s$ at time $t$ , its initial segment must be a maximum-metric path among all paths ending at $(t,s)$ — otherwise replacing that segment would improve the total. So it suffices to keep, for each of the $2^{K-1}$ states at each time, one survivor with its metric. Extending all survivors by one step costs $O(2^{K-1})$ per time step (two incoming edges per state, a constant), for $O(T2^{K-1})$ overall, and a traceback at the end recovers the path. Since every path is represented by a survivor at some stage, the maximum over final states is the global maximum.∎

Intuition. Exhaustive maximum-likelihood decoding would examine $2^{T}$ input sequences. Viterbi exploits the fact that the encoder's memory is only $K-1$ bits: two input histories that end in the same state are interchangeable from then on, so only the better one needs to be remembered. The cost is exponential in the memory, not in the message length.

Definition 9.41 (Recursive systematic convolutional encoder). An RSC encoder is obtained from a feedforward encoder by feeding back one output into the input and transmitting the information bit itself. Its transfer function is rational, $\big(1, \frac{g^{(2)}(D)}{g^{(1)}(D)}\big)$ , so a single input $1$ produces an output of infinite (or very long) weight, whereas a feedforward encoder responds to it with a burst of weight at most $K r$ .

That last clause is why turbo codes use RSC components rather than ordinary ones, as the next theorem makes precise.

Definition 9.42 (Turbo encoder, parallel concatenation). A turbo encoder feeds the information block $\mathbf u$ of length $k$ to one RSC encoder, and the permuted block $\Pi(\mathbf u)$ to a second RSC encoder. Transmitted are the systematic bits $\mathbf u$ and the two parity streams $\mathbf p^{(1)}, \mathbf p^{(2)}$ , giving rate $1/3$ before puncturing; puncturing the parity streams alternately gives rate $1/2$ .

Theorem 9.43 (Interleaver gain). For a parallel concatenation of two RSC encoders with a uniform random interleaver of length $k$ , the contribution to the bit error probability from input sequences of weight $w$ scales as $k^{1-w}$ . Hence weight- $1$ inputs contribute $O(1)$ and every heavier input contributes a vanishing amount, so the dominant error events come from the lowest input weight that produces a finite-weight codeword in both encoders.

Proof. Sketch. Under the uniform interleaver model — averaging over all $k!$ permutations — the probability that a weight- $w$ input producing a particular low-weight parity pattern in encoder 1 also produces a low-weight pattern in encoder 2 is governed by the number of ways of placing $w$ ones, $\binom kw \approx k^w/w!$ , against the number of "bad" placements, which grows like $k^{\lfloor w/2 \rfloor}\cdots$ ; carrying the count through gives the exponent $1-w$ for the multiplicity per information bit. For an RSC encoder a weight- $1$ input produces an infinite-weight (in practice, very heavy) parity sequence, so $w=1$ contributes nothing; $w=2$ is the first relevant weight and it already carries the factor $k^{-1}$ . The full derivation is Benedetto and Montorsi's uniform-interleaver analysis, which we cite rather than reproduce.∎

Remark (Why RSC, in one sentence). With feedforward components a weight- $1$ input gives low-weight parity in both encoders no matter how they are interleaved, so there is no interleaver gain at all; recursion is what forces the low-weight error events to require at least two well-placed ones, and the interleaver then makes that coincidence rare.

Example 9.44 (Rate and block structure). A rate- $1/3$ turbo code carries $k = 1000$ information bits. How many bits are transmitted, and what changes at rate $1/2$ ?

Solution. Systematic $1000$ plus two parity streams of $1000$ each gives $3000$ transmitted bits, a rate of $1/3$ (ignoring the few tail bits used to return each encoder to the zero state). To reach rate $1/2$ , puncture the parity: keep $p^{(1)}_t$ for odd $t$ and $p^{(2)}_t$ for even $t$ , transmitting $1000$ systematic plus $1000$ parity bits in total. Puncturing raises the rate and lowers the effective free distance, which is the usual trade.□

Pitfall. The interleaver is not a scrambler for security or for burst protection, and a "nice" interleaver such as a block (row-column) permutation is a poor choice: it maps some low-weight patterns to other low-weight patterns. S-random and quadratic permutation polynomial interleavers are used precisely because they guarantee that nearby positions are separated.

Exercises for §9.8 →

9.9Iterative Decoding and Extrinsic Information

Neither constituent decoder can decode the turbo code on its own — each sees only its own parity. The turbo principle is to let them take turns, each passing the other only what the other does not already know.

Definition 9.45 (Soft-input soft-output decoding, BCJR). The BCJR algorithm computes, for each information bit of a trellis code, the exact a posteriori LLR

L(u_t) = \log\frac{\Pr[u_t = 0\mid \mathbf y]}{\Pr[u_t=1\mid\mathbf y]},

by a forward recursion $\alpha_t(s)$ over states, a backward recursion $\beta_t(s)$ , and branch metrics $\gamma_t(s',s)$ , combining them as $\Pr[u_t = b \mid\mathbf y] \propto \sum_{(s',s):u=b}\alpha_{t-1}(s')\gamma_t(s',s)\beta_t(s)$ . Its cost is $O(T2^{K-1})$ , the same order as Viterbi, with a larger constant.

Definition 9.46 (Extrinsic information). Write the output LLR of a decoder as

L_{\mathrm{post}}(u_t) = L_{\mathrm{ch}}(u_t) + L_{\mathrm{a}}(u_t) + L_{\mathrm{e}}(u_t),

the channel LLR of the systematic bit, the a priori LLR supplied by the other decoder, and the remainder $L_{\mathrm{e}}$ , which is the extrinsic information: what this decoder learned about $u_t$ from its parity and from the other bits, excluding what it was told.

Method 9.47 (Turbo iteration).

Decoder 1 runs BCJR on the first trellis with a priori LLRs $L_{\mathrm a}^{(1)}$ (zero on the first pass) and outputs extrinsic $L_{\mathrm e}^{(1)}$ .
Interleave: $L_{\mathrm a}^{(2)} = \Pi\big(L_{\mathrm e}^{(1)}\big)$ .
Decoder 2 runs BCJR on the second trellis and outputs $L_{\mathrm e}^{(2)}$ .
De-interleave: $L_{\mathrm a}^{(1)} = \Pi^{-1}\big(L_{\mathrm e}^{(2)}\big)$ ; return to step 1.
After the last iteration, decide $\hat u_t$ from the sign of the total a posteriori LLR.

Proposition 9.48 (Why only extrinsic information may be passed). If a decoder passes its full a posteriori LLR instead of the extrinsic part, the same evidence is returned to its source and counted twice; the iteration then develops a positive feedback loop whose beliefs grow without bound and which converges to a confident answer independent of whether that answer is right.

Proof. The LLR update rule is exact only for independent pieces of evidence, which is what allows likelihood ratios to multiply. If decoder 2 receives $L_{\mathrm{post}}^{(1)} = L_{\mathrm{ch}} + L_{\mathrm a}^{(1)} + L_{\mathrm e}^{(1)}$ , the term $L_{\mathrm a}^{(1)}$ is precisely the information decoder 2 supplied on the previous half-iteration, and the channel term is already in decoder 2's own input. Adding them again multiplies the same likelihood ratio twice, which is the error of treating dependent evidence as independent; iterating the doubling makes $|L|$ grow geometrically, and the sign is fixed early by whichever hypothesis happened to lead.∎

Intuition. Two experts examine the same patient from different angles. Progress is made only when each reports what their own examination added, rather than repeating back what the other told them — otherwise the pair talk themselves into certainty by hearing their own opinions returned as confirmation.

Example 9.49 (One half-iteration in numbers). On rate- $1/2$ turbo decoding, the systematic bit $u_5$ has channel LLR $+0.3$ and decoder 1 has a priori $L_{\mathrm a}^{(1)}(u_5) = 0$ on the first pass. Its BCJR output is $L_{\mathrm{post}}^{(1)}(u_5) = +2.6$ . What is passed to decoder 2, and to which position?

Solution. The extrinsic part is $L_{\mathrm e}^{(1)} = L_{\mathrm{post}}^{(1)} - L_{\mathrm{ch}} - L_{\mathrm a}^{(1)} = 2.6 - 0.3 - 0 = +2.3$ . That value — not $2.6$ — is interleaved and delivered to decoder 2 as a priori information at position $\Pi(5)$ , say position $42$ .

If decoder 2 then returns extrinsic $-0.7$ for that bit, decoder 1's next pass runs with $L_{\mathrm a}^{(1)}(u_5) = -0.7$ , and its total belief becomes $0.3 - 0.7 + L_{\mathrm e}^{(1),\text{new}}$ . The disagreement is exactly the useful signal: two nearly independent views of the same bit that differ are what drives the iteration.□

Remark (EXIT charts). Convergence is analysed with extrinsic information transfer charts: plot each constituent decoder's output mutual information against its input mutual information, and superimpose the second decoder's curve with axes swapped. The iteration is the staircase between the two curves, and it reaches the top-right corner — perfect information, hence successful decoding — if and only if a tunnel remains open between them. The SNR at which the tunnel closes is the iterative decoding threshold, the turbo analogue of the LDPC threshold computed by density evolution.

Exercises for §9.9 →

9.10Performance, Error Floors and Applications

Remark (The two regions of a turbo code's error curve). A turbo code's bit error rate against SNR has two distinct regions. The waterfall is a near-vertical drop starting just above the iterative threshold, and it is what made the codes famous. The error floor is the shallow region at higher SNR, where the curve flattens; it is governed by the few low-weight codewords that the interleaver failed to break up, and by the maximum-likelihood distance spectrum rather than by the iterative decoder.

Example 9.50 (Reading the gap to capacity honestly). A rate- $1/2$ turbo code with interleaver length $65536$ reaches a bit error rate of $10^{-5}$ at $E_b/N_0 \approx 0.7$ dB on the AWGN channel. How far from the limit is that?

Solution. The relevant limit is the binary-input AWGN capacity at rate $1/2$ , which requires $E_b/N_0 \ge 0.187$ dB; the unconstrained-input Shannon limit for rate $1/2$ is $0$ dB, and using it would flatter the code. So the gap is about $0.7 - 0.19 = 0.5$ dB, the number Berrou and co-authors reported, and it is measured at a specific error rate and block length. Shrinking the interleaver to $10^3$ costs several tenths of a dB and raises the error floor; enlarging it to $10^5$ buys perhaps $0.2$ dB more and lowers the floor, since interleaver gain scales the floor by $k^{-1}$ for the dominant weight- $2$ events.□

Pitfall. Quoting "within $0.5$ dB of Shannon" without saying which limit, at which error rate, with which block length and how many iterations is the most common overstatement in coding papers. The binary-input limit is the right comparison for a binary code, and it sits about $0.19$ dB above the unconstrained one at rate $1/2$ .

Remark (Where each family is deployed). Turbo codes were adopted in 3G UMTS and in 4G LTE data channels, and in the CCSDS deep-space standard where the interleaver may be very long and latency is irrelevant. 5G moved the data channel to LDPC codes and the control channels to polar codes, for reasons that are about implementation rather than about distance: belief propagation parallelises across edges, whereas BCJR is sequential along a trellis and has to be run twice per iteration. The turbo principle — exchanging extrinsic information between soft-in soft-out blocks — survives everywhere, including in turbo equalisation and in joint detection-and-decoding receivers.

Intuition. Two weak codes, plus a shuffle, plus a conversation, equal one very strong code. Neither constituent code has a large free distance; what the interleaver does is make it overwhelmingly unlikely that an error pattern is simultaneously plausible to both decoders.

Exercises for §9.10 →

Common Mistakes

Confusing LDPC with turbo codes: both are iteratively decoded and capacity-approaching, but LDPC codes are defined by a sparse parity-check matrix and decoded on its Tanner graph, whereas turbo codes concatenate convolutional codes through an interleaver.
**Assuming any sparse $H$ gives a good code**: degree-2-heavy ensembles violate the stability condition, short cycles wreck finite-length performance, and $d_v = 2$ ensembles have logarithmic minimum distance.
Treating belief propagation as maximum likelihood: it is exact only on trees. On a loopy graph it may converge to a non-codeword, oscillate, or stop at a trapping set.
Reading a threshold as a finite-length guarantee: thresholds are asymptotic. A length-1000 code performs visibly worse than its ensemble threshold predicts.
Forgetting that the all-zero codeword suffices for simulation: for a linear code on a symmetric channel the error probability does not depend on the transmitted codeword, so simulations transmit $\mathbf 0$ — but only after checking that the decoder itself is symmetric.
Ignoring the error floor: the waterfall is not the whole curve. Systems that need error rates below $10^{-12}$ care more about trapping sets than about the threshold.
Reading the polarization theorem as a finite-length guarantee: it says the *fraction* of extremal channels converges. At any finite $n$ many synthetic channels are still mediocre, and they are the ones that cause errors.
Confusing the polar transform with the FFT: $G_n$ has the butterfly structure of a fast Hadamard transform, but the code lies in the choice of frozen set, which is channel-dependent and has no analogue in signal processing.
Thinking frozen bits carry information: they carry *known* values. Their role is to make the good synthetic channels usable, not to add parity.
Assuming SC is maximum likelihood: it is greedy and cannot revisit a decision. SCL with $L>1$ plus a CRC is what approaches ML.
Designing the information set at the wrong SNR: the ordering of synthetic channels depends on the channel. A set chosen for a clean channel is wrong for a noisy one, which is why standards fix a single nested reliability sequence as a compromise.
Expecting polar codes to dominate everywhere: at long blocks and high rates LDPC codes usually win on implementation; 5G deploys both for exactly that reason.
Calling every concatenation "turbo": the classical construction is *parallel* concatenation of two RSC encoders. Serial concatenation is a different (and sometimes better) architecture with its own analysis.
Using feedforward components: without recursion there is no interleaver gain, and the error floor does not fall with block length.
Passing a posteriori instead of extrinsic information: this double-counts evidence and produces a confidently wrong decoder.
Expecting a short turbo code to perform well: interleaver gain is a $k^{-1}$ effect. Short blocks have visible floors, which is why 5G control channels use polar codes instead.
Treating the BCJR as maximum likelihood for the whole code: it is exact for one constituent trellis; the concatenation is decoded only approximately, by iteration.
Comparing against the wrong Shannon limit: for binary signalling the relevant number at rate $1/2$ is $0.187$ dB in $E_b/N_0$ , not $0$ dB.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Linear and Hamming Codes Rate–Distortion Theory →

Helpful?