Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC

Pablo M. Olmos, Juan José Murillo-Fuentes, Fernando Pérez-Cruz

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.

Figure 4: Comparison of factor graph structures used in the EP approximation. (a) shows a standard tree-like structure, while (b) illustrates how Tree-EP can incorporate additional dependencies.

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

Abstract

We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.
BibTeX
@article{olmos2013tree,
  author = {Pablo M. Olmos and Juan José Murillo-Fuentes and Fernando Pérez-Cruz},
  title = {{Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC}},
  journal = {IEEE Trans. Information Theory},
  year = {2013},
  url = {https://openreview.net/forum?id=UoQDs5jFfe},
}
Figure