4 LDPC Codes and Belief Propagation
After completing this chapter, you will be able to: - Define LDPC codes and explain why sparsity enables efficient decoding - Construct Tanner graphs from parity-check matrices - Derive and implement the Belief Propagation (sum-product) algorithm - Apply the Min-Sum approximation for practical implementations - Identify convergence issues and error floors in BP decoding
This chapter assumes familiarity with: - Linear codes and parity-check matrices (Chapter 1) - Probability and Bayes’ theorem - Logarithms and basic calculus (for LLR derivations)
4.1 LDPC Definition and Tanner Graph
Low-Density Parity-Check (LDPC) codes, first discovered by Robert Gallager in 1962 [@gallager1962], are a class of linear codes characterized by sparse parity-check matrices. Despite being overlooked for decades, LDPC codes are now among the most powerful error-correcting codes known, approaching the Shannon limit with practical decoding complexity.
4.1.1 Sparse Parity-Check Matrices
The defining property of an LDPC code is the sparsity of its parity-check matrix.
An LDPC code is a linear code defined by a parity-check matrix \(H\) where each row has bounded weight \(w_r\) and each column has bounded weight \(w_c\), both independent of the block length \(n\). Specifically: - Row weight (number of 1s per check): \(w_r = O(1)\) - Column weight (number of checks per bit): \(w_c = O(1)\)
Such a code is described as an \([n, k, d]\) LDPC code where \(k\) is the dimension and \(d\) is the minimum distance.
The “low-density” refers to the fact that as \(n\) grows, the number of 1s in \(H\) grows linearly with \(n\) (specifically \(w_r(n-k)\) 1s), while the matrix has \(n(n-k)\) entries. Thus the density of 1s goes to zero as \(n → ∞\).
4.2 Example: Small LDPC Code
A \([6, 2, 3]\) LDPC code with parity-check matrix: \[ H = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 \end{pmatrix} \]
Each row has weight 4, each column has weight 1 or 2. This is a valid LDPC code with \(n = 6\) and \(n-k = 3\), encoding \(k = 2\) information bits.
The sparsity of \(H\) is crucial for decoding: it enables efficient message-passing algorithms that run in time linear in the number of edges.
4.2.1 Regular and Irregular LDPC Codes
LDPC codes are further classified by the distribution of their row and column weights.
A regular (or homogeneous) LDPC code has constant row weight \(w_r\) and constant column weight \(w_c\). It is denoted as an \([n, j, k]\) LDPC code where each column of \(H\) contains exactly \(j\) ones and each row contains exactly \(k\) ones.
An irregular LDPC code allows varying row and column weights. The degree distribution is characterized by two polynomials: \[ \lambda(x) = \sum_{i=2}^{d_\lambda} \lambda_i x^{i-1}, \quad \rho(x) = \sum_{i=2}^{d_\rho} \rho_i x^{i-1} \] where \(\lambda_i\) (\(\rho_i\)) is the fraction of edges connected to variable (check) nodes of degree \(i\).
Irregular codes can outperform regular codes by optimizing the degree distribution to maximize “information flow” during belief propagation decoding. This optimization is typically done using density evolution [@richardson2001].
4.2.2 Tanner Graph Representation
The Tanner graph provides a graphical representation of a linear code that facilitates understanding of the decoding algorithm.
The Tanner graph of an \([n, k]\) code with parity-check matrix \(H\) is a bipartite graph with: - \(n\) variable nodes (one for each code bit) - \(n-k\) check nodes (one for each parity-check equation) - Edges connecting variable node \(v_i\) to check node \(c_j\) iff \(H_{j,i} = 1\)
Think of a Tanner graph like a social network between “bits” and “rules.” Variable nodes are people who each hold a secret bit. Check nodes are group chats where connected people must have their bits XOR to zero. The sparse connections mean each person only participates in a few chats, and each chat only involves a few people—this locality is what makes efficient decoding possible.
The bipartite structure separates the two types of nodes, with edges only between variable and check nodes—never between nodes of the same type.
The Tanner graph reveals important structural properties:
- Check nodes enforce parity constraints: the XOR of connected variable bits must equal 0
- Variable nodes represent the bits being constrained
- Short cycles (especially length 4) degrade decoding performance
4.2.3 Girth: Cycle Length in Tanner Graphs
The girth is the length of the shortest cycle in the Tanner graph.
The girth of a Tanner graph is the length of the shortest cycle. For LDPC codes, the girth is typically denoted \(g\).
Cycles cause problems for belief propagation because they create dependencies between messages, violating the assumption of statistical independence that underlies the algorithm. The length-4 cycle is particularly problematic: if \(v_i\) connects to \(c_j\) and \(c_k\), and \(v_l\) also connects to \(c_j\) and \(c_k\), messages can bounce back and forth between \(v_i\) and \(v_l\) through the checks.
Tanner graphs with larger girth generally exhibit better BP decoding performance because: - Longer cycles delay the onset of dependency between messages - More iterations can run before messages become correlated - Tree-like regions (where BP is exact) persist longer
4.3 Example: Girth Calculation
In the \([6, 2, 3]\) LDPC Tanner graph: - Path: \(v_1 → c_1 → v_3 → c_2 → v_4 → c_1\) closes a cycle - This cycle has length 6, so girth \(g = 6\) (no length-4 cycles)
A Tanner graph with no length-4 cycles is called cycle-4-free.
Constructing LDPC codes with large girth is an active research area. Progressive edge growth (PEG) algorithms [@hu2005] can construct codes with girths of 8 or more for block lengths of practical interest.
While large girth is desirable, it is not the only factor determining code performance. The overall degree distribution, EXIT chart characteristics, and trapping set structure also play crucial roles. In practice, irregular codes with moderate girth often outperform regular codes with larger girth.
4.4 Belief Propagation Algorithm
The Belief Propagation (BP) algorithm, also known as the Sum-Product Algorithm, is the cornerstone of modern LDPC decoding. It leverages the Tanner graph structure to efficiently compute approximate marginal probabilities for each bit, enabling near-optimal decoding with linear complexity.
4.4.1 Factor Graph Perspective
BP operates on the code’s factor graph, which factorizes the joint distribution of received values and code constraints.
Let the received vector be \(\mathbf{r} = (r_1, r_2, ..., r_n)\) and let \(c_i\) denote the transmitted bit at position \(i\). The joint distribution factors as: \[ Pr(\mathbf{c}, \mathbf{r}) = \prod_{i=1}^n Pr(r_i | c_i) \prod_{j=1}^{n-k} \mathbf{1}_{H_j \mathbf{c}^T = 0} \]
The second factor enforces each parity-check constraint: the check \(j\) equals 1 only if the parity of bits connected to it is even.
BP computes the marginal distribution \(Pr(c_i | \mathbf{r})\) for each variable node by passing messages along edges. The key insight is that these marginals can be computed efficiently by exchanging messages between neighboring nodes.
A common mistake is assuming BP always finds the optimal (maximum likelihood) decoding. Actually, BP is only exact on tree-structured graphs—and LDPC Tanner graphs contain cycles. On graphs with cycles, BP computes approximate marginals that may not correspond to any valid probability distribution. Despite this theoretical limitation, BP works remarkably well in practice because good LDPC codes have large girth (long shortest cycles), making the local neighborhood tree-like for many iterations.
4.4.2 Message Passing Framework
BP uses two types of messages: - \(m_{c → v}\): information flowing from check node \(c\) to variable node \(v\) - \(m_{v → c}\): information flowing from variable node \(v\) to check node \(c\)
Messages are probability distributions (or their log-likelihood ratios) over the binary values \(\{0, 1\}\). Each message summarizes all information available from the rest of the graph except the receiving node itself.
Let \(N(v)\) denote the neighbors of variable node \(v\), and \(N(c)\) denote the neighbors of check node \(c\). The BP update rules are:
Variable to Check message: \[ m_{v → c}(x) = K_{v,c} Pr(r_v | x) \prod_{c' \in N(v) \setminus \{c\}} m_{c' → v}(x) \]
Check to Variable message: \[ m_{c → v}(x) = \sum_{\mathbf{y} \in \{0,1\}^{N(c)}} \left( \prod_{v' \in N(c) \setminus \{v\}} m_{v' → c}(y_{v'}) \right) \mathbf{1}_{\sum(y) \mod 2 = x} \]
BP works like a gossip network. Each bit asks its neighboring checks: “Based on what you’ve heard from others, what do you think I am?” Each check gathers opinions from its other bits and replies. After several rounds of gossip, everyone converges on a consistent story. The rule “exclude the recipient” prevents echo chambers—you don’t tell someone what they just told you.
The check-to-variable message computes the probability that the parity of all other bits connected to \(c\) equals \(x\), conditioned on the check being satisfied.
4.4.3 Log-Likelihood Ratio Form
Working with probabilities directly can cause numerical underflow. The Log-Likelihood Ratio (LLR) form is more numerically stable.
The LLR of a binary variable \(x\) is: \[
L(x) = \ln\left(\frac{Pr(x=0)}{Pr(x=1)}\right)
\]
Positive LLRs favor \(x=0\), negative LLRs favor \(x=1\), and \(|L|\) measures confidence in the decision.
Think of LLR as a “confidence meter” with a needle. Zero means “no idea,” positive means “probably 0,” negative means “probably 1.” The magnitude tells you how sure: \(L = +10\) means “almost certainly 0,” while \(L = +0.1\) means “slightly leaning toward 0.” Using logs converts multiplying tiny probabilities into adding manageable numbers—essential for numerical stability.
In LLR form, the BP updates become:
Variable to Check: \[
L_{v\to c} = L_c + \sum_{c' \in N(v) \setminus c} L_{c'\to v}
\]
Check to Variable: \[
L_{c\to v} = 2 \tanh^{-1}\left( \prod_{v' \in N(c) \setminus v} \tanh(L_{v'\to c} / 2) \right)
\]
The tanh form is more compact but can be approximated for efficiency (see Section 2.3).
The BP visualization shows how information propagates through the Tanner graph: - Iteration 1: Nodes only have access to direct channel information - Iteration 2: Each node incorporates information from its neighbors - Iteration 3+: Information propagates further; messages stabilize
Convergence typically occurs within 10-50 iterations for well-designed codes.
4.5 Example: LLR Initialization
For a BSC with crossover probability \(p\), the channel LLR for received bit \(r_v\) is: \[ L_c = \ln\left(\frac{1-p}{p}\right) \quad \text{if } r_v = 0 \] \[ L_c = \ln\left(\frac{p}{1-p}\right) \quad \text{if } r_v = 1 \]
For \(p = 0.1\), receiving 0 gives \(L_c = \ln(0.9/0.1) ≈ 2.2\), a positive value favoring \(c_v = 0\).
4.5.1 Iterative Decoding Process
The complete BP decoding algorithm proceeds as follows:
Belief Propagation Decoding
Initialize: For each variable node \(v\), set \(L_{v\to c} = L_c\) for all connected checks \(c\).
Check node update: For each check node \(c\), compute \(L_{c\to v}\) for all connected variables \(v\) using the tanh formula.
Variable node update: For each variable node \(v\), compute updated \(L_{v\to c}\) for all connected checks \(c\).
Tentative decision: Compute the APP (a posteriori probability) LLR for each variable: \[ L_a = L_c + \sum_{c \in N(v)} L_{c\to v} \] If \(|L_a| > 0\) gives a codeword, check if \(H \mathbf{c}^T = \mathbf{0}\).
Convergence check: If syndrome is zero or maximum iterations reached, stop. Otherwise, return to step 2.
4.5.2 Complexity Analysis
The computational complexity of BP is linear in the number of edges in the Tanner graph.
Let \(E\) be the number of edges in the Tanner graph (number of 1s in \(H\)). Each BP iteration requires: - \(O(E)\) operations for check node updates - \(O(E)\) operations for variable node updates
Total complexity per iteration: \(O(E)\).
For a regular \([n, j, k]\) LDPC code, \(E = j × n = k(n-k)\). Since \(j\) and \(k\) are constants (independent of \(n\)), the complexity is \(O(n)\)—linear in the block length. This is dramatically better than the \(O(n 2^k)\) complexity of exhaustive decoding.
4.6 Example: BP Complexity Comparison
For a \([1000, 500, 3]\) regular LDPC code with \(j = 3\), \(k = 6\): - Number of edges \(E = 3 × 1000 = 3000\) - Each iteration: ~6000 elementary operations - 50 iterations: ~300,000 operations
Compare to exhaustive search: \(2^500 ≈ 10^150\) possibilities—completely infeasible.
The combination of near-Shannon-limit performance (approaching the MLD error rate) and linear-time decoding makes LDPC codes uniquely practical. They are now used in 5G/6G communications, WiFi 802.11n/ac/ax, satellite communications, and many other applications where reliable high-rate transmission is required.
4.7 Min-Sum Approximation
The standard sum-product BP algorithm provides excellent performance but requires computationally expensive operations like hyperbolic tangents and their inverses. The Min-Sum approximation simplifies these operations, making BP more suitable for hardware implementation while maintaining competitive performance.
4.7.1 From Sum-Product to Min-Sum
The key observation is that the tanh function in the check node update can be approximated when LLRs are reliable.
The check node update is: \[ L_{c\to v} = 2 \tanh^{-1}\left( \prod_{v' \in N(c) \setminus v} \tanh(L_{v'\to c} / 2) \right) \]
When all incoming messages have the same sign (indicating agreement on the bit value), the product of tanhs can be approximated. Using the identity: \[ \tanh(x/2) = \frac{e^x - 1}{e^x + 1} = \tanh(x/2) \]
we derive the Min-Sum approximation:
For the Min-Sum algorithm, the check-to-variable message is approximated as: \[ L_{c\to v} \approx s_{c\to v} \times \min_{v' \in N(c) \setminus v} |L_{v'\to c}| \] where \(s_{c\to v} = \prod_{v' \in N(c) \setminus v} sgn(L_{v'\to c})\) is the parity (product of signs) of all incoming messages.
The approximation becomes exact when all but one incoming message have infinite confidence (|tanh(L/2)| → 1), hence the name “Min-Sum”—it takes the minimum magnitude and sums the signs.
4.8 Example: Min-Sum Calculation
Suppose a check node receives three messages with LLRs: \[ L_{v'_1\to c} = +2.5, \quad L_{v'_2\to c} = -1.8, \quad L_{v'_3\to c} = +3.2 \]
Min-Sum output to \(v'_1\): - Sign product: \(sgn(+2.5) × sgn(-1.8) × sgn(+3.2) = (+) × (-) × (+) = -\) - Minimum magnitude: \(\min(|+2.5|, |-1.8|, |+3.2|) = 1.8\) - Result: \(L_{c\to v'_1} = -1.8\)
Min-Sum output to \(v'_2\): - Sign product: \(sgn(+2.5) × sgn(-1.8) × sgn(+3.2) = -\) - Minimum magnitude: \(\min(|+2.5|, |-1.8|, |+3.2|) = 1.8\) - Result: \(L_{c\to v'_2} = -1.8\) (but excluding \(v'_2\), so min is 2.5)
Actually excluding the destination: \(\min(|+2.5|, |+3.2|) = 2.5\), sign = (+), so \(L = +2.5\)
4.8.1 Normalized and Offset Min-Sum
The basic Min-Sum approximation tends to overestimate the reliability of messages, leading to degraded performance compared to Sum-Product. Two common refinements address this issue.
The normalized Min-Sum algorithm applies a scaling factor \(\alpha < 1\) to the Min-Sum output: \[ L_{c\to v} = \alpha \times s_{c\to v} \times \min_{v' \in N(c) \setminus v} |L_{v'\to c}| \]
Typical values: \(\alpha \in [0.7, 0.9]\). The optimal \(\alpha\) depends on the code and can be found through density evolution or simulation.
The offset Min-Sum algorithm subtracts a constant offset \(\beta\) before applying the sign: \[ L_{c\to v} = s_{c\to v} \times \max\left(0, \min_{v' \in N(c) \setminus v} |L_{v'\to c}| - \beta\right) \]
This prevents overestimation by zeroing out low-confidence messages. Typical values: \(\beta \in [0.5, 1.5]\).
4.8.2 Implementation Advantages
Min-Sum variants offer significant practical advantages over Sum-Product:
Compared to Sum-Product, Min-Sum requires: - No hyperbolic tangent or arctanh computations - Only comparisons, additions, and sign operations - No division operations
For a check node of degree \(d_c\), Sum-Product requires \(O(d_c)\) tanh and arctanh evaluations, while Min-Sum requires \(O(d_c)\) comparisons plus one final multiplication.
| Algorithm | Operations per check node | Hardware | Performance loss |
|---|---|---|---|
| Sum-Product | \(2(d_c-1)\) tanh/arctanh | Complex | Baseline |
| Min-Sum | \((d_c-1)\) comparisons | Simple | ~0.5 dB |
| Normalized MS | \((d_c-1)\) comparisons + mult. | Simple | ~0.2 dB |
| Offset MS | \((d_c-1)\) comparisons + subtract | Simple | ~0.1 dB |
The normalized and offset Min-Sum variants achieve performance within 0.1-0.2 dB of Sum-Product while maintaining most of the implementation simplicity. This trade-off is often favorable in hardware implementations where computational resources are limited, such as in 5G base stations or satellite receivers.
4.9 BP Convergence and Limitations
Belief Propagation provides excellent performance on LDPC codes, but its approximate nature leads to several failure modes that become increasingly important at low error rates.
4.9.1 Tree-Exactness: The Ideal Case
On Tanner graphs without cycles (trees), BP is exact—it computes the true marginal probabilities after a single pass of message passing.
On an acyclic Tanner graph, the belief propagation algorithm computes the exact a posteriori probabilities after \(g/2\) iterations, where \(g\) is the graph diameter. Each variable’s belief depends only on its true local evidence and the constraints in its neighborhood.
This is why long cycles are problematic: they create “shortcuts” that make messages correlated, violating the independence assumptions underlying BP.
4.9.2 Oscillation and Non-Convergence
In practical LDPC codes with cycles, BP may fail to converge to a stable solution within the maximum number of iterations.
BP oscillation occurs when the sequence of beliefs alternates between two or more states without settling. This typically happens when: - Check nodes receive conflicting messages from variable nodes - The graph structure creates feedback loops that reinforce uncertainty
4.10 Example: Oscillation Pattern
Consider a simple 4-cycle: \(v_1-c_1-v_2-c_2-v_1\). If \(v_1\) and \(v_2\) both receive unreliable information, they may send alternating messages: - Iteration 1: \(v_1\) tells \(c_1\) “I think I’m 0” - Iteration 2: \(c_1\) tells \(v_2\) “0 is unlikely” based on \(c_2\)’s previous message - Iteration 3: \(v_2\) tells \(c_2\) “I think I’m 1” - Iteration 4: \(c_2\) tells \(v_1\) “1 is unlikely”…
The beliefs oscillate indefinitely.
Several techniques mitigate oscillation: - Damping: Blend new messages with previous messages (e.g., 50% new, 50% old) - Serial scheduling: Update nodes sequentially rather than in parallel - Maximum iteration limit: Terminate after fixed number of iterations
4.10.1 Trapping Sets and Error Floors
At low error rates, LDPC codes often exhibit an error floor—a region where the slope of the FER curve decreases dramatically.
A trapping set is a harmful subgraph structure that causes BP to converge to an incorrect codeword or fail to converge. It consists of: - A set of variable nodes \(T\) (the “trapped” variables) - A set of check nodes \(N(T)\) connected to \(T\)
Trapping sets are characterized by \((a, b)\) where \(a = |T|\) and \(b = |N(T) \setminus C_S|\), where \(C_S\) are satisfied checks.
Error floors occur when: 1. An error pattern activates a trapping set 2. The check nodes in \(N(T)\) become unsatisfied but cannot correct the errors 3. BP iterates within the trapping set, never escaping
Typical trapping sets have small \(a\) (10-100 variables) and small \(b\) (even number of unsatisfied checks).
Common trapping set types include: - Elementary trapping sets (ETS): Minimal harmful structures - Near-codewords: Vectors close to codewords (small syndrome weight) - Stopping sets: Variable sets where checks have all even degree
Designing LDPC codes with good error floors requires careful construction to avoid harmful trapping sets. Progressive edge growth (PEG) construction, approximate cycle extrinsic message degree (ACE) optimization, and careful degree distribution design are standard techniques. However, even well-designed codes eventually exhibit error floors at sufficiently low rates—typically \(10^{-12}\) or below for space applications.
4.10.2 Bridging to Quantum Decoding
These classical BP limitations directly transfer to quantum LDPC decoding:
Degeneracy helps: Unlike classical codes, quantum codes have degenerate errors that produce the same syndrome. This can improve performance.
More complex graphs: Quantum codes often have non-bipartite Tanner graphs or additional structure (CSS codes, stabilizer codes).
Same message passing: The fundamental BP algorithm remains the same, but syndrome interpretation differs.
The convergence issues and trapping sets we study here are also relevant for quantum decoding, where post-processing methods like OSD become even more important.
- LDPC codes have sparse parity-check matrices, enabling efficient decoding; sparsity is measured by column weight \(d_v\) and row weight \(d_c\)
- Tanner graphs represent codes as bipartite graphs with variable nodes (bits) and check nodes (constraints); girth affects BP performance
- Log-likelihood ratios (LLRs) represent soft information: \(L = \ln(Pr(c=0)/Pr(c=1))\); positive means likely 0, negative means likely 1
- Belief Propagation iteratively passes messages between variable and check nodes; exact on trees, approximate on graphs with cycles
- Variable-to-check messages sum incoming information excluding the target; check-to-variable messages use the tanh rule for parity constraints
- Convergence is not guaranteed; trapping sets and stopping sets can cause BP to fail even below the code’s correction capability
4.11 Exercises
LLR Computation. Consider a Binary Symmetric Channel with crossover probability \(p = 0.1\).
Compute the channel LLR for a received bit \(y = 1\). Express your answer as \(\ln((1-p)/p)\) and evaluate numerically.
If the channel LLR is \(L = 2.0\), what is the probability that the transmitted bit was 0?
Explain intuitively why a larger magnitude LLR indicates higher confidence in the bit value.
BP Message Passing. Consider a simple LDPC code with parity-check matrix: \[ H = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \end{pmatrix} \]
Draw the Tanner graph for this code, labeling variable nodes \(v_1, ..., v_4\) and check nodes \(c_1, c_2\).
Suppose the initial channel LLRs are \(L_1 = 1.5\), \(L_2 = -0.5\), \(L_3 = 0.8\), \(L_4 = 1.2\). Compute the variable-to-check messages \(\mu_{v_1 \to c_1}\), \(\mu_{v_2 \to c_1}\), \(\mu_{v_3 \to c_1}\) for the first iteration.
Using the tanh rule, compute the check-to-variable message \(\mu_{c_1 \to v_1}\) after the first iteration.
Convergence Analysis. Consider BP decoding on an LDPC code.
Describe what happens when BP converges to a valid codeword. What are the syndrome values?
Explain the concept of a “trapping set” and why it causes BP to fail even when the number of errors is below the code’s correction capability.
If BP fails to converge after 50 iterations, suggest two post-processing strategies that could be applied to improve decoding success.
We have seen how LDPC codes and Belief Propagation provide efficient near-optimal decoding for classical channels. The key insight—iterative message passing on sparse graphs—extends naturally to quantum error correction. The next chapter introduces stabilizer codes and the CSS construction, which build quantum codes from classical linear codes. The syndrome decoding problem becomes richer in the quantum setting due to degeneracy, where different errors can have equivalent effects on the encoded quantum information.