  The subject of this paper is transmission over a general class of
binary-input memoryless symmetric channels using error correcting codes based
on sparse graphs, namely low-density generator-matrix and low-density
parity-check codes. The optimal (or ideal) decoder based on the posterior
measure over the code bits, and its relationship to the sub-optimal belief
propagation decoder, are investigated. We consider the correlation (or
covariance) between two codebits, averaged over the noise realizations, as a
function of the graph distance, for the optimal decoder. Our main result is
that this correlation decays exponentially fast for fixed general low-density
generator-matrix codes and high enough noise parameter, and also for fixed
general low-density parity-check codes and low enough noise parameter. This has
many consequences. Appropriate performance curves - called GEXIT functions - of
the belief propagation and optimal decoders match in high/low noise regimes.
This means that in high/low noise regimes the performance curves of the optimal
decoder can be computed by density evolution. Another interpretation is that
the replica predictions of spin-glass theory are exact. Our methods are rather
general and use cluster expansions first developed in the context of
mathematical statistical mechanics.
