Paper Info
Title
Tree-Structure Expectation Propagation for LDPC Decoding in Erasure Channels
Abstract
In this paper we present a new algorithm, denoted as TEP, to decode low-density parity-check (LDPC) codes over the Binary Erasure Channel (BEC). The TEP decoder is derived applying the expectation propagation (EP) algorithm with a tree- structured approximation. Expectation Propagation (EP) is a generalization to 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 pair-wise marginal constraints in some check nodes of the LDPC code's Tanner graph. The algorithm has the same computational complexity than BP, but it can decode a higher fraction of errors when applied over the BEC. In this paper, we focus on the asymptotic performance of the TEP decoder, as the block size tends to infinity. We describe the TEP decoder by a set of differential equations that represents the residual graph evolution during the decoding process. The solution of these equations yields the capacity of this decoder for a given LDPC ensemble over the BEC. We show that the achieved capacity with the TEP is higher than the BP capacity, at the same computational complexity.
Year
Venue
Keywords
2010
Clinical Orthopaedics and Related Research
exponential family,binary erasure channel,computational complexity,ldpc code,erasure channel,tree structure,low density parity check,differential equation,information theory,belief propagation
Field
DocType
Volume
Discrete mathematics,Low-density parity-check code,Binary erasure channel,Tree structure,Expectation propagation,Tanner graph,Decoding methods,Mathematics,Belief propagation,Computational complexity theory
Journal
abs/1009.4
Citations 
PageRank 
References 
3
0.41
22
Authors
3
Name
Order
Citations
PageRank
Pablo M. Olmos111418.97
Juan José Murillo-Fuentes218223.93
Fernando Pérez-Cruz374961.24