Title :
Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC
Author :
Olmos, Pablo M. ; Murillo-Fuentes, Juan Jose ; Perez-Cruz, Fernando
Author_Institution :
Dept. Teor. de la Senal y Comun., Univ. Carlos III de Madrid, Leganés, Spain
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.
Keywords :
decoding; parity check codes; BEC; LDPC decoding; Tanner graph; belief propagation; binary erasure channel; decode low-density parity-check codes; discrete memoryless channels; peeling-type algorithm; tree-structure expectation propagation; Algorithm design and analysis; Approximation algorithms; Approximation methods; Complexity theory; Decoding; Parity check codes; Probability density function; Belief-propagation (BP); LDPC codes; binary erasure channel; expectation propagation; finite-length analysis; random graph evolution;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2013.2245494