Tree-Structure Expectation Propagation for LDPC Decoding over the BEC

Details Tree-Structure Expectation Propagation for LDPC Decoding over the BEC Tree-Structure Expectation Propagation for LDPC Decoding over the BEC

2012-01-03

arxiv.org/abs/1201.0715v2

Computer Science

Information Theory

22 pages. arXiv admin note: substantial text overlap with arXiv:1009.4287

Scientific paper

We present the tree-structure expectation propagation (Tree-EP) to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). EP 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 pair-wise 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 regime over the BEC. While the TEP decoder asymptotically performs as the BP for regular and optimized codes. For finite-length LDPC codes, we derive a scaling law to predict the decoder performance that can be used for LDPC optimization.

Affiliated with

Also associated with

No associations

Rating

Tree-Structure Expectation Propagation for LDPC Decoding over the BEC does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tree-Structure Expectation Propagation for LDPC Decoding over the BEC, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree-Structure Expectation Propagation for LDPC Decoding over the BEC will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184315