Abstract
This paper presents Tree-Structure Expectation Propagation (Tree-EP), a novel decoding framework for Low-Density Parity-Check (LDPC) codes. By capturing pairwise dependencies between variable nodes through a Markov tree structure, Tree-EP generalizes standard Belief Propagation (BP). For the Binary Erasure Channel (BEC), this framework simplifies into a linear-complexity "peeling" decoder (TEP) that significantly improves finite-length performance by resolving stopping sets that stall traditional BP.
Introduction
Low-Density Parity-Check (LDPC) codes are essential for approaching channel capacity in modern communication systems. Typically, these codes are decoded using Belief Propagation (BP), which is optimal on tree graphs but suboptimal on the loopy graphs characteristic of real-world codes. In such graphs, BP assumes variable nodes are independent, leading to failures on "stopping sets"—subgraphs where no parity check has only one unknown variable. While Maximum A Posteriori (MAP) decoding is the theoretical gold standard, its computational complexity is prohibitive for large codes. This work introduces Tree-EP as a computationally efficient middle ground, offering $O(n)$ complexity while outperforming BP in practical, finite-length scenarios.
Methods
The core of the proposed approach is the use of Expectation Propagation (EP), a technique from machine learning, to approximate the joint probability of bits. Unlike BP, which approximates the posterior as a product of independent marginals, Tree-EP utilizes a Markov tree structure. This allows the decoder to account for pairwise interactions between variables connected to the same check node, effectively "seeing" through certain cycles that would otherwise cause BP to fail.
For the Binary Erasure Channel (BEC), Tree-EP reduces to a simplified "peeling" algorithm called the TEP decoder. While a standard BP peeling decoder only processes check nodes of degree one (revealing one bit), the TEP decoder also handles degree-two check nodes. When a degree-two check node is encountered (e.g., $V_1 \oplus V_2 = 0$), the decoder recognizes the equality of the two variables and "merges" them in the graph. This simplification can create new degree-one nodes, allowing the decoding process to continue where BP would have stalled.
The authors further provide a theoretical framework using Wormald’s Theorem and differential equations to track the graph's evolution. This enables the derivation of scaling laws—mathematical tools to predict performance across different code lengths without exhaustive simulation.
Key Results and Discussion
The TEP decoder was evaluated on regular (3,6) and irregular LDPC ensembles with block lengths ranging from $n = 2^{10}$ to $n = 2^{17}$. Key findings include:
- Finite-Length Gain: TEP consistently decodes a higher fraction of errors than BP, particularly in the "waterfall" region where error rates drop sharply.
- Efficiency: TEP can achieve the same error performance as BP using approximately half the block length, which is a significant advantage for latency-sensitive applications.
- Complexity: Despite the additional work of merging nodes, the total complexity remains $O(n)$, making it a viable drop-in replacement for BP.
- Scaling Law Accuracy: The derived scaling laws were shown to be highly accurate, matching experimental simulation data for both regular and irregular codes.
Limitations and Future Work
While TEP offers substantial gains for finite-length codes, the authors note that for many standard optimized ensembles, it does not improve the asymptotic threshold (the performance as $n \to \infty$). Future research will focus on finding specific code ensembles that show asymptotic gains under TEP and extending the $O(n)$ implementation to other channels, such as the Binary Symmetric Channel or Gaussian noise, where the mathematics are more complex.
Summary updated