46.08.01 · information-theory / modern-codes

LDPC Codes, Tanner Graphs, Belief Propagation, and Density Evolution Analysis

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.4; Richardson & Urbanke 2008 Modern Coding Theory (Cambridge) §§3-4 (density evolution, stability condition, threshold phenomenon); Gallager 1962 Low-Density Parity-Check Codes (MIT PhD thesis)

Intuition Beginner

Imagine you have a large sheet of equations, each involving only a few unknowns. Each equation checks whether a small group of bits satisfies a parity constraint (their sum is even). Each bit appears in only a few equations. The sheet is "sparse" — most entries are zero. This sparse system of checks is a low-density parity-check code, or LDPC code.

Why sparsity matters: a dense parity-check matrix (like Hamming codes use) gives strong algebraic structure but does not scale. A sparse matrix gives you something different — you can decode by passing simple messages between bits and checks, iteratively, without solving the whole system at once. Each bit sends its best guess to the checks it participates in. Each check sends back information about what the bit should be, based on the other bits in that check. After several rounds, the bits converge to a consistent codeword.

Think of it like a group of students solving a puzzle together. Each student knows their own clue and can share hints with a few neighbours. After enough rounds of sharing, the whole group converges on the answer. No student needs to see the entire puzzle — just local information, iterated.

Robert Gallager invented these codes in his 1962 PhD thesis at MIT. At the time, computers were too slow for iterative decoding to be practical, so the codes were forgotten for three decades. In 1996, David MacKay and Radford Neal rediscovered them and demonstrated near-capacity performance. Today, LDPC codes are in every modern communication standard: Wi-Fi (802.11n/ac/ax), 5G cellular, satellite links, and hard drive storage.

Visual Beginner

Component	Analogy	Role
Variable node	A student with a clue	Represents one bit of the codeword
Check node	A classroom rule	Represents one parity constraint
Edge	A conversation	Connects a bit to a check it participates in
Message	A whispered hint	Probabilistic opinion passed along an edge
Iteration	One round of sharing	All messages update simultaneously

Figure: A Tanner graph for a small LDPC code with 6 variable nodes (circles, labelled $v_{1}$ through $v_{6}$ ) and 4 check nodes (squares, labelled $c_{1}$ through $c_{4}$ ). Each variable node connects to 2 check nodes; each check node connects to 3 variable nodes. This is a (2,3)-regular code. Messages flow left-to-right (variable to check) and right-to-left (check to variable) in alternating rounds.

The Tanner graph is bipartite: edges only connect variable nodes to check nodes, never variable-to-variable or check-to-check. The graph structure exactly mirrors the sparsity pattern of the parity-check matrix.

Worked example Beginner

Consider a tiny (3,6)-regular LDPC code with block length $n = 12$ and $m = 6$ parity checks, so the rate is $R = 1 - 6/12 = 1/2$ . Each bit participates in 3 checks; each check involves 6 bits. Suppose we transmit the all-zeros codeword over a binary symmetric channel with crossover probability $p = 0.05$ (5% chance each bit flips).

The channel output has, on average, $12 \times 0.05 = 0.6$ bit errors. Let us say the received word is $y = (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)$ , where bit 3 was flipped by the channel.

Each bit starts with a log-likelihood ratio (LLR) from the channel. For the binary symmetric channel with crossover $p$ , the LLR for received bit $y_{i}$ is:

L_{ch} (y_{i}) = lo g \frac{1 - p}{p} .

With $p = 0.05$ : $L_{ch} = lo g (0.95/0.05) = lo g (19) \approx 2.94$ . A positive LLR means the bit is more likely 0. For the flipped bit 3, the received value is 1, so its LLR is $- 2.94$ (leaning toward bit value 1, which is wrong).

In the first round of belief propagation, each variable node sends its channel LLR to each of its 3 neighbouring check nodes. Each check node then combines the messages from its other 5 neighbours (excluding the target variable) to send back a message. The check-to-variable message says: "given what the other bits in this check look like, what should your bit be?"

For check nodes connected to the error bit $v_{3}$ , one of the 5 other bits will contribute wrong information, but the other 4 contribute correct information. The majority vote of the check node will point the bit back toward 0. After a few iterations, the error is corrected. The decoder converges because the channel is "clean enough" — the error rate of 5% is well below the decoding threshold for a (3,6)-regular code, which is approximately 8.4% on the binary symmetric channel.

Check your understanding Beginner

Formal definition Intermediate+

Let $F_{2}$ denote the binary field. An LDPC code of length $n$ with $m$ parity checks is defined by a parity-check matrix $H \in F_{2}^{m \times n}$ that is sparse: the number of nonzero entries per row and per column is bounded by constants independent of $n$ .

Definition (Regular LDPC code). A $(j, k)$ -regular LDPC code has a parity-check matrix $H$ where every column contains exactly $j$ ones and every row contains exactly $k$ ones. The parameters satisfy $n \cdot j = m \cdot k$ (equal total edge count counted by rows and columns). The design rate is $R = 1 - m / n = 1 - j / k$ .

Definition (Tanner graph). The Tanner graph of $H$ is a bipartite graph $G = (V \cup C, E)$ where $V = {v_{1}, \dots, v_{n}}$ is the set of variable nodes (one per column of $H$ ), $C = {c_{1}, \dots, c_{m}}$ is the set of check nodes (one per row of $H$ ), and $(v_{i}, c_{j}) \in E$ iff $H_{j i} = 1$ . For a $(j, k)$ -regular code, every variable node has degree $j$ and every check node has degree $k$ .

Definition (Irregular LDPC code). An irregular LDPC code is described by two polynomials. The variable-node degree distribution from the edge perspective is:

λ (x) = i = 2 \sum d_{v} λ_{i} x^{i - 1}

where $λ_{i}$ is the fraction of edges connected to variable nodes of degree $i$ , and $d_{v}$ is the maximum variable-node degree. The check-node degree distribution is:

ρ (x) = i = 2 \sum d_{c} ρ_{i} x^{i - 1}

where $ρ_{i}$ is the fraction of edges connected to check nodes of degree $i$ , and $d_{c}$ is the maximum check-node degree. The rate of the irregular code is:

R = 1 - \frac{\sum _{i} ρ _{i} / i}{\sum _{i} λ _{i} / i} .

A $(j, k)$ -regular code has $λ (x) = x^{j - 1}$ and $ρ (x) = x^{k - 1}$ .

Counterexamples to common slips

Sparsity is asymptotic. For a $(3, 6)$ code of length $n$ , the density of $H$ is $3/ n$ , which vanishes as $n \to \infty$ . A fixed $6 \times 12$ matrix with 3 ones per column is not "low-density" in the asymptotic sense — the code is too short for the sparsity to matter.
The Tanner graph must be acyclic for exact belief propagation. If the Tanner graph has cycles, belief propagation is no longer exact — messages become correlated after one traversal of each cycle. Practical LDPC codes always have cycles, but the graph is designed so the shortest cycle (the girth) is long enough that BP converges before correlations corrupt the messages.
Rate is a design rate, not always achievable. The formula $R = 1 - j / k$ gives the design rate assuming all $m$ rows of $H$ are linearly independent. If $H$ has linearly dependent rows, the actual rate is higher, but the code is weaker because fewer independent constraints are enforced.

Key theorem with proof Intermediate+

Theorem (Belief propagation update rules). Consider an LDPC code with Tanner graph $G = (V \cup C, E)$ . Let $L_{i \to j}$ denote the log-likelihood ratio message from variable node $v_{i}$ to check node $c_{j}$ in the current iteration, and $L_{j \to i}$ the message from $c_{j}$ to $v_{i}$ . Let $N (i)$ be the set of check-node neighbours of $v_{i}$ and $N (j)$ the set of variable-node neighbours of $c_{j}$ . The belief propagation update rules are:

Variable-to-check update:

L_{i \to j} = L_{ch} (i) + j^{'} \in N (i) ∖ {j} \sum L_{j^{'} \to i}

Check-to-variable update:

tanh (\frac{L _{j \to i}}{2}) = i^{'} \in N (j) ∖ {i} \prod tanh (\frac{L _{i^{'} \to j}}{2})

where $L_{ch} (i)$ is the channel log-likelihood ratio for bit $i$ .

Proof. The variable-node update combines independent evidence. Variable node $v_{i}$ has access to the channel observation $L_{ch} (i)$ and the incoming messages from all neighbouring check nodes except $c_{j}$ (to avoid feeding back information that originated from $c_{j}$ ). Since the messages from different check nodes concern disjoint parity constraints, the combined LLR is the sum:

L_{i \to j} = L_{ch} (i) + j^{'} \neq = j \sum L_{j^{'} \to i} .

The check-node update uses the parity constraint. Check node $c_{j}$ enforces the equation $⨁_{i \in N (j)} x_{i} = 0$ (mod 2). The LLR for the XOR of two independent binary random variables $X_{1}, X_{2}$ with LLRs $L_{1}, L_{2}$ satisfies:

tanh (\frac{L _{X_{1} \oplus X_{2}}}{2}) = tanh (\frac{L _{1}}{2}) tanh (\frac{L _{2}}{2}) .

This is the box-plus (or tanh) rule. By induction, the LLR of the XOR of $∣ N (j) ∣ - 1$ variables is given by the product of their tanh values, which yields the check-node update. The exclusion of $v_{i}$ from the product enforces the extrinsic message principle: $c_{j}$ sends to $v_{i}$ only information derived from the other variable nodes. $□$

Bridge. The belief propagation update rules build toward density evolution in 46.08.01 (this unit's advanced section) by providing the exact functional map from input message densities to output message densities at each node type. This functional map appears again in 46.08.02 as the same sum-product structure used in turbo decoding, and in 40.06.06 as the soft-decoding generalisation of the syndrome-based algebraic decoder. The foundational reason the tanh product rule works is that parity constraints in $F_{2}$ define XOR operations whose likelihood ratios factor through the tanh identity, and this is exactly the algebraic structure that makes iterative decoding tractable. The central insight is that the graph sparsity keeps each update local (constant cost per node), while the global structure of the Tanner graph ensures that information propagates across all bits over multiple iterations.

Exercises Intermediate+

Exercise (hard, short answer).

Prove the box-plus (tanh) rule: if $X_{1}$ and $X_{2}$ are independent binary random variables taking values in ${0, 1}$ with LLRs $L_{1}$ and $L_{2}$ , then the LLR of $Z = X_{1} \oplus X_{2}$ satisfies $tanh (L_{Z} /2) = tanh (L_{1} /2) \cdot tanh (L_{2} /2)$ .

Hint

Write $P (Z = 0) = P (X_{1} = X_{2})$ and $P (Z = 1) = P (X_{1} \neq = X_{2})$ , then express in terms of the individual probabilities.

Answer

Let $p_{i} = P (X_{i} = 0)$ and $q_{i} = 1 - p_{i}$ . Then $L_{i} = ln (p_{i} / q_{i})$ and $tanh (L_{i} /2) = (e^{L_{i}} - 1) / (e^{L_{i}} + 1) = (p_{i} - q_{i}) / (p_{i} + q_{i}) = 2 p_{i} - 1$ . Independence gives $P (Z = 0) = p_{1} p_{2} + q_{1} q_{2}$ and $P (Z = 1) = p_{1} q_{2} + q_{1} p_{2}$ . Then:

tanh (L_{Z} /2) = 2 P (Z = 0) - 1 = 2 (p_{1} p_{2} + q_{1} q_{2}) - 1 = 2 p_{1} p_{2} + 2 (1 - p_{1}) (1 - p_{2}) - 1.

Expanding: $2 p_{1} p_{2} + 2 - 2 p_{1} - 2 p_{2} + 2 p_{1} p_{2} - 1 = 4 p_{1} p_{2} - 2 p_{1} - 2 p_{2} + 1 = (2 p_{1} - 1) (2 p_{2} - 1) = tanh (L_{1} /2) \cdot tanh (L_{2} /2)$ .

Exercise (hard, short answer).

For the binary erasure channel with erasure probability $ϵ$ , belief propagation simplifies: messages are either real numbers (known bits) or "erased" (unknown bits). State the BP update rules for the BEC and show that BP decoding succeeds iff the induced subgraph of erased variable nodes has no stopping set.

Hint

On the BEC, LLRs are either $+ \infty$ , $- \infty$ , or 0 (erased). A check node can recover a variable if all other variables in that check are known.

Answer

On the BEC, the channel output for each bit is either the correct value (known) or an erasure symbol. LLRs are $\pm \infty$ for known bits and 0 for erased bits. Variable-to-check: send the channel value if known, otherwise the product of all incoming check messages (any nonzero message restores the bit). Check-to-variable: send the XOR of all other incoming variable messages, but only if all other variables are known; otherwise send 0 (erased).

A stopping set is a subset $S$ of variable nodes such that every check node connected to $S$ is connected to at least two variable nodes in $S$ . If the erased positions form a stopping set, no check node has a single erased neighbour, so no bit can be recovered by BP. Conversely, if the erased positions do not form a stopping set, there exists a check node with exactly one erased neighbour, so that bit is recovered; removing it may expose another such check, and the process continues until all erasures are resolved or a stopping set is reached. BP succeeds iff no stopping set is reached.

Exercise (hard, short answer).

Show that the (3,6)-regular LDPC code has a density evolution threshold on the binary erasure channel of $ϵ^{*} = (5 - 1) /2 \approx 0.429$ (the reciprocal of the golden ratio). That is, for $ϵ < ϵ^{*}$ , the erasure probability after BP decoding converges to zero.

Hint

On the BEC, the density evolution equation for a $(j, k)$ -regular code is $x_{ℓ + 1} = ϵ \cdot (1 - (1 - x_{ℓ})^{k - 1})^{j - 1}$ where $x_{ℓ}$ is the erasure probability at iteration $ℓ$ . Find the fixed point.

Answer

On the BEC, the density evolution recurrence for a $(3, 6)$ -regular code is:

x_{ℓ + 1} = ϵ (1 - (1 - x_{ℓ})^{5})^{2} .

The threshold $ϵ^{*}$ is the largest $ϵ$ for which the fixed point $x^{*} = 0$ is stable, i.e., $ϵ^{*} = 1/ max_{x \in [0, 1]} (1 - (1 - x)^{5})^{2} / x$ . Setting the derivative of $f (x) = ϵ (1 - (1 - x)^{5})^{2}$ at $x = 0$ to equal 1 gives $ϵ^{*} \cdot 2 \cdot 5^{2} \cdot x = x$ at the leading order, but the exact computation requires solving $ϵ = x / (1 - (1 - x)^{5})^{2}$ at the maximum. The fixed-point equation $ϵ = x / (1 - (1 - x)^{5})^{2}$ evaluated at the critical point yields $ϵ^{*} \approx 0.429$ . More precisely, expanding $(1 - (1 - x)^{5}) = 5 x - 10 x^{2} + 10 x^{3} - 5 x^{4} + x^{5}$ and solving the fixed-point condition numerically gives $ϵ^{*} = 0.4294...$ , which is approximately $(5 - 1) /2$ .

Lean formalization Intermediate+

Mathlib does not define sparse parity-check matrices, Tanner graphs, or iterative message-passing algorithms. The SimpleGraph type can represent bipartite graphs but lacks the variable/check node labelling, the degree-distribution polynomials $λ (x)$ and $ρ (x)$ , and the BP update rules. The density evolution analysis requires a functional that maps a distribution on $R \cup {\pm \infty}$ to a new distribution under the tanh-product and summation operations; this is absent. A Codex.CodingTheory.LDPC module defining a ParityCheckMatrix type with sparsity constraints, the associated Tanner graph, and a MessagePassing procedure would be the load-bearing first step; this unit ships without it.

Advanced results Master

Density evolution

Density evolution is the analytical tool that predicts the performance of belief propagation decoding on LDPC codes in the limit of infinite blocklength. The key idea: in the limit $n \to \infty$ , the Tanner graph of a random $(j, k)$ -regular LDPC code is locally tree-like (the girth grows as $Ω (lo g n)$ ), so messages arriving at any node are approximately independent. This independence assumption allows us to track the probability distribution of messages through iterations as a deterministic dynamical system.

Let $f_{v}$ denote the density transformation at a variable node of degree $d_{v}$ and $f_{c}$ the density transformation at a check node of degree $d_{c}$ . For the binary erasure channel, the density is fully characterised by a single scalar $x_{ℓ}$ , the erasure probability of a randomly chosen message at iteration $ℓ$ . The density evolution equation for a $(j, k)$ -regular code on the BEC is:

x_{ℓ + 1} = ϵ \cdot λ (1 - ρ (1 - x_{ℓ}))

where $λ$ and $ρ$ are the edge-degree distribution polynomials. For a $(3, 6)$ -regular code ( $λ (x) = x^{2}$ , $ρ (x) = x^{5}$ ), this becomes:

x_{ℓ + 1} = ϵ \cdot (1 - (1 - x_{ℓ})^{5})^{2} .

For general channels (BSC, AWGN), the density is a distribution on $R$ , and the evolution involves convolutions (at variable nodes) and a nonlinear transformation involving the tanh product rule (at check nodes). Richardson and Urbanke (2001) showed that this infinite-dimensional dynamical system can be analysed to compute the threshold precisely.

The threshold phenomenon

Definition (BP threshold). The belief propagation threshold for an LDPC ensemble with degree distributions $(λ, ρ)$ on a channel family ${p_{σ}}$ parameterised by $σ$ is:

σ^{*} = sup {σ : BP decoding error probability \to 0 as ℓ \to \infty} .

The threshold is a property of the degree distribution, not of any individual code. For the (3,6)-regular ensemble on the BSC, the threshold is $p^{*} \approx 0.084$ . For the BEC, $ϵ^{*} \approx 0.429$ . Shannon capacity for rate $1/2$ on the BSC is $H^{- 1} (1/2) \approx 0.110$ , so the (3,6)-regular code achieves about 76% of capacity.

The threshold phenomenon says that BP decoding undergoes a phase transition: below the threshold, the error probability converges to zero exponentially fast in the number of iterations; above the threshold, it converges to a nonzero constant. This is analogous to a physical phase transition, and the mathematical structure is the same as that of spin glasses in statistical mechanics.

Capacity-approaching irregular codes

The breakthrough of Luby, Mitzenmacher, Shokrollahi, Spielman, and Stemann (1997, 2001) was to show that irregular LDPC codes can approach the Shannon capacity arbitrarily closely by optimising the degree distributions $λ (x)$ and $ρ (x)$ . The key insight: nodes of high degree act as "super-nodes" that collect information from many checks and broadcast it widely, accelerating convergence. Nodes of low degree provide the majority of the code's structure and redundancy.

For the BEC, the optimisation problem is: given a target erasure rate $ϵ$ , find $(λ, ρ)$ maximising $R = 1 - \sum ρ_{i} / i \cdot \sum λ_{i} / i$ subject to the stability condition $λ_{2} ρ^{'} (1) < 1$ and the convergence condition $x_{ℓ} \to 0$ under density evolution. Using linear programming over the degree distribution coefficients, codes achieving rates within $1 0^{- 6}$ bits of Shannon capacity on the BEC have been constructed (for example, by Shokrollahi and Urbanke's Tornado/LDPC constructions).

For the AWGN channel, Chung, Forney, Riley, and Urbanke (2001) constructed irregular LDPC codes that achieve rates within 0.0045 dB of the Shannon limit at block length $n = 1 0^{7}$ . These codes use variable-node degrees up to 8000 and are the closest any practical code has come to the Shannon limit.

Stability condition

The stability condition is a local analysis of the density evolution fixed point at $x = 0$ . For a general binary-input memoryless symmetric channel, the condition is:

λ_{2} ρ^{'} (1) \cdot T_{ch} < 1

where $T_{ch}$ is the Bhattacharyya parameter of the channel. For the BEC with erasure probability $ϵ$ , $T_{ch} = ϵ$ , so the condition becomes $λ_{2} ρ^{'} (1) ϵ < 1$ . This ensures that the all-zero fixed point of the density evolution is stable, i.e., small residual error rates decay to zero. The stability condition gives a necessary condition for the threshold, and in many cases it is also sufficient.

Synthesis. Density evolution is the analytical engine that transforms belief propagation from an algorithm into a theory; the threshold phenomenon is the central insight that BP decoding undergoes a sharp phase transition at a channel parameter determined entirely by the degree distribution; the stability condition is the bridge between the local (linearised) analysis of the fixed point at zero error and the global convergence of the density evolution map; and the optimisation of irregular degree distributions puts these together to close the gap to Shannon capacity. The generalises from the BEC analysis to general symmetric channels through the same functional iteration on message densities, and the foundational reason LDPC codes can approach capacity is that the sparsity of the Tanner graph simultaneously ensures low decoding complexity (linear in $n$ ) and long-range information propagation (through the expander-like structure of the graph).

Full proof set Master

Proposition (Girth and independence). For a random $(j, k)$ -regular LDPC code ensemble with block length $n$ , the expected girth of the Tanner graph is at least $Ω (lo g n)$ . Consequently, messages within $⌊ g /4 ⌋$ iterations of BP, where $g$ is the girth, are statistically independent.

Proof. Consider a breadth-first search from an arbitrary edge in the Tanner graph. At depth $ℓ$ , the search tree has at most $((j - 1) (k - 1))^{ℓ}$ edges. A cycle of length $2 ℓ$ exists only if two distinct paths from the root reconnect at the same node. For a random bipartite graph with $n$ variable nodes and $m = nj / k$ check nodes, the probability that a given pair of paths of length $ℓ$ reconnect is at most $1/ min (n, m)$ at each reconnection opportunity. There are $((j - 1) (k - 1))^{2 ℓ}$ candidate path pairs, so the expected number of cycles of length $2 ℓ$ is at most $((j - 1) (k - 1))^{2 ℓ} / n$ . This vanishes when $((j - 1) (k - 1))^{ℓ} ≪ n$ , which holds for $ℓ \leq c lo g n$ where $c$ depends on $j$ and $k$ . Direct computation shows $c = 1/ (4 lo g ((j - 1) (k - 1)))$ suffices, giving girth $g \geq c^{'} lo g n$ . Messages within $g /4$ iterations traverse only the tree neighbourhood, which is cycle-free, ensuring independence. $□$

Proposition (Density evolution for the BEC). For an LDPC code ensemble with degree distributions $(λ, ρ)$ on the BEC with erasure probability $ϵ$ , the probability $x_{ℓ}$ that a randomly chosen message is erased at iteration $ℓ$ satisfies:

x_{ℓ + 1} = ϵ \cdot λ (1 - ρ (1 - x_{ℓ})) .

Proof. On the BEC, a check node can recover an erased variable if and only if all other variables in that check are known (non-erased). A check-to-variable message from a check node of degree $i$ is erased iff all $i - 1$ other variable-to-check messages are erased, each with probability $x_{ℓ}$ . So the check-to-variable erasure probability for a degree- $i$ check is $x_{ℓ}^{i - 1}$ .

Averaging over the edge-degree distribution $ρ$ , the check-to-variable erasure rate is:

i \sum ρ_{i} x_{ℓ}^{i - 1} = ρ (x_{ℓ}) .

Now consider a variable node of degree $j$ . Its outgoing variable-to-check message is erased iff the channel erased it (probability $ϵ$ ) AND all $j - 1$ incoming check messages are erased (each with probability $ρ (x_{ℓ})$ ). The conditional erasure probability is $ρ (x_{ℓ})^{j - 1}$ .

Averaging over $λ$ and including the channel erasure:

x_{ℓ + 1} = ϵ j \sum λ_{j} ρ (x_{ℓ})^{j - 1} = ϵ λ (ρ (x_{ℓ})) .

To convert to the standard form, substitute $ρ (x_{ℓ}) = 1 - (1 - ρ (x_{ℓ}))$ and define $1 - ρ (x_{ℓ})$ as the probability a check message provides information. On the BEC, a check message provides information with probability $1 - x_{ℓ}^{d_{c} - 1}$ for a degree- $d_{c}$ check, so $ρ (x_{ℓ}) = \sum_{i} ρ_{i} x_{ℓ}^{i - 1}$ and $1 - ρ (x_{ℓ}) = \sum_{i} ρ_{i} (1 - x_{ℓ}^{i - 1})$ . The standard literature form uses the complementary variable: writing $1 - ρ (x)$ in terms of $1 - x$ gives $ρ (1 - x) = \sum ρ_{i} (1 - x)^{i - 1}$ as the fraction of check messages that provide information (all others known). Then the erasure fraction at the check output is $1 - ρ (1 - x_{ℓ})$ , and the variable-node combining gives $x_{ℓ + 1} = ϵ λ (1 - ρ (1 - x_{ℓ}))$ .

Verification for the $(3, 6)$ -regular code: $λ (x) = x^{2}$ , $ρ (x) = x^{5}$ , giving $x_{ℓ + 1} = ϵ (1 - (1 - x_{ℓ})^{5})^{2}$ , which matches the known recurrence. $□$

Connections Master

46.01.01 — Entropy and mutual information set the fundamental limits (Shannon capacity) that LDPC codes approach; the gap between the BP threshold and capacity is measured in terms of the mutual information between channel input and output.
40.06.06 — Linear codes and their parity-check matrices are the algebraic substrate on which LDPC codes are built; the LDPC construction adds the sparsity constraint that enables iterative decoding.
46.03.01 — Channel capacity is the benchmark: the BP threshold of an LDPC ensemble is always below Shannon capacity, and the goal of degree-distribution optimisation is to close this gap.
40.06.07 — Perfect codes (Hamming, Golay) achieve maximum-likelihood decoding bounds but have fixed rates; LDPC codes sacrifice algebraic perfection for flexible rates and near-capacity performance via iterative decoding.
46.02.01 — The asymptotic equipartition property guarantees that long codes concentrate around their ensemble average, which is the statistical foundation for density evolution's $n \to \infty$ analysis.

Historical & philosophical context Master

Robert Gallager developed LDPC codes in his 1962 MIT doctoral thesis, "Low-Density Parity-Check Codes," supervised by Peter Elias and Claude Shannon. Gallager constructed $(j, k)$ -regular ensembles, devised the iterative decoding algorithm (then called "probabilistic decoding"), and proved that the minimum distance of his random codes grew linearly with block length with high probability. His thesis was published as an MIT Press monograph in 1963.

Despite their theoretical elegance, Gallager's codes were impractical for the computers of the 1960s. Decoding required iterative floating-point operations on large matrices, and the computational cost exceeded what was feasible. The codes fell into obscurity for three decades. The coding theory community focused on algebraic codes (Reed-Solomon, BCH) and convolutional codes with Viterbi decoding, which had efficient hardware implementations.

The rediscovery began in 1996 when David MacKay and Radford Neal published "Near Shannon Limit Performance of Low Density Parity Check Codes" in Electronics Letters (vol. 32, pp. 1645-1646). They demonstrated that Gallager's codes, when decoded with modern hardware, achieved bit-error rates of $1 0^{- 6}$ at signal-to-noise ratios within 0.3 dB of the Shannon limit on the AWGN channel. This result, coming just two years after Berrou, Glavieux, and Thitimajshima's 1993 turbo code breakthrough, reignited interest in iterative decoding.

The theoretical framework was completed by Thomas Richardson and Ruediger Urbanke in their 2001 paper "The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding" (IEEE Transactions on Information Theory, vol. 47, pp. 599-618). They introduced density evolution as a rigorous analytical tool, proved the concentration of individual code performance around the ensemble average, and computed the BP threshold for various channels and degree distributions. Their 2008 book Modern Coding Theory (Cambridge University Press) is the definitive treatment.

The parallel development of irregular LDPC codes by Luby, Mitzenmacher, Shokrollahi, Spielman, and Stemann (STOC 1997, and subsequent papers) showed that optimising the degree distribution could close the gap to capacity entirely on the BEC. Chung, Forney, Riley, and Urbanke (2001) extended this to the AWGN channel, constructing codes within 0.0045 dB of capacity. These results cemented LDPC codes as the practical realisation of Shannon's 1948 promise.

LDPC codes entered commercial standards in the 2000s. They replaced turbo codes in the 5G NR (New Radio) standard (3GPP Release 15, 2017) for the data channel, and they are the FEC scheme in Wi-Fi 802.11n/ac/ax, DVB-S2 (satellite television), and IEEE 802.3an (10GBASE-T Ethernet). The victory of LDPC over turbo codes in 5G was decided by LDPC's superior throughput at high data rates and lower decoding latency.

Bibliography Master

@phdthesis{gallager1962,
  author = {Gallager, R. G.},
  title  = {Low-Density Parity-Check Codes},
  school = {Massachusetts Institute of Technology},
  year   = {1962},
}
@book{gallager1963,
  author    = {Gallager, R. G.},
  title     = {Low-Density Parity-Check Codes},
  publisher = {MIT Press},
  year      = {1963},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{richardson-urbanke2008,
  author    = {Richardson, T. and Urbanke, R.},
  title     = {Modern Coding Theory},
  publisher = {Cambridge University Press},
  year      = {2008},
}
@article{mackay-neal1996,
  author  = {MacKay, D. J. C. and Neal, R. M.},
  title   = {Near Shannon Limit Performance of Low Density Parity Check Codes},
  journal = {Electronics Letters},
  volume  = {32},
  pages   = {1645--1646},
  year    = {1996},
}
@inproceedings{luby1997,
  author    = {Luby, M. G. and Mitzenmacher, M. and Shokrollahi, M. A. and Spielman, D. A. and Stemann, V.},
  title     = {Practical Loss-Resilient Codes},
  booktitle = {Proc. 29th ACM STOC},
  pages     = {150--159},
  year      = {1997},
}
@article{richardson-urbanke2001,
  author  = {Richardson, T. and Urbanke, R.},
  title   = {The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding},
  journal = {IEEE Transactions on Information Theory},
  volume  = {47},
  pages   = {599--618},
  year    = {2001},
}
@article{chung2001,
  author  = {Chung, S.-Y. and Forney, G. D. and Riley, T. J. and Urbanke, R.},
  title   = {On the Design of Low-Density Parity-Check Codes Within 0.0045 dB of the Shannon Limit},
  journal = {IEEE Communications Letters},
  volume  = {5},
  pages   = {58--60},
  year    = {2001},
}

Prerequisites

46.01.01
40.06.06
46.03.01

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.2 (sparse parity-check matrices as graphs, iterative decoding as passing messages along wires)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.4 (Tanner graphs, belief propagation algorithm, message-passing schedules, density evolution)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.1-7.4; Richardson & Urbanke 2008 Modern Coding Theory (Cambridge) §§3-4 (density evolution, stability condition, threshold phenomenon); Gallager 1962 Low-Density Parity-Check Codes (MIT PhD thesis)

References

Gallager, R. G. — Low-Density Parity-Check Codes · MIT Press (1963); originally PhD thesis, MIT, 1962. Chapter 2 defines $(j, k)$ -regular LDPC codes: a binary parity-check matrix $H$ of size $m \times n$ where each column has weight $j$ and each row has weight $k$ , with $m$ and $n$ large so the matrix is sparse. Chapter 3 introduces probabilistic (message-passing) decoding, computing log-likelihood ratios at variable and check nodes. Chapter 4 analyses the ensemble performance using the density of the message distribution.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 7.1: definition of LDPC codes and sparse parity-check matrices. Section 7.2: Tanner graph representation with variable nodes and check nodes. Section 7.3: belief propagation decoding on the Tanner graph, update rules for log-likelihood ratios. Section 7.4: density evolution and the threshold phenomenon for the binary erasure channel.
Richardson, T. & Urbanke, R. — Modern Coding Theory · Cambridge University Press (2008). Chapter 3: message-passing decoding on factor graphs, the sum-product algorithm. Chapter 4: density evolution as the tracking of the message-density distribution through iterations; the threshold $p^{*}$ below which the bit-error probability vanishes. The stability condition for the binary erasure channel: $λ_{2} ρ^{'} (1) < 1$ where $λ$ and $ρ$ are the edge-degree distributions.
MacKay, D. J. C. & Neal, R. M. — Near Shannon Limit Performance of Low Density Parity Check Codes · Electronics Letters 32 (1996) 1645-1646. Rediscovered LDPC codes 30 years after Gallager, demonstrating near-capacity performance on the binary erasure channel and the AWGN channel. Sparked the modern resurgence of iterative decoding and the development of density evolution analysis.
Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A., Spielman, D. A. & Stemann, V. — Practical Loss-Resilient Codes · Proc. 29th ACM STOC (1997) 150-159. Introduced irregular LDPC codes for the binary erasure channel, showing that degree distribution optimization can close the gap to channel capacity. The Tornado codes built on this insight.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m