  We present the tree-structure expectation propagation (Tree-EP) algorithm 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
asymptotic threshold of the TEP decoder is the same as the BP decoder for
regular and optimized codes, we propose a scaling law (SL) for finite-length
LDPC codes, which accurately approximates the TEP improved performance and
facilitates its optimization.
