Decay of correlations for sparse graph error correcting codes

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 suboptimal belief propagation decoder are investigated. We consider the correlation (or covariance) between two code-bits, 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 given low-density generator-matrix codes and a high enough noise parameter and also for given low-density parity-check codes and a low enough noise parameter. This has many consequences. Appropriate performance curves — called generalized extrinsic information transfer (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 mechanic


Published in:
SIAM JOURNAL ON DISCRETE MATHEMATICS, 25, 2, 956-988
Year:
2011
ISSN:
0895-4801
Keywords:
Note:
Special issue on constraint satisfaction problems and message passing algorithms
Laboratories:




 Record created 2009-04-04, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)