Decay of Correlations for Sparse Graph Error Correcting Codes

Details Decay of Correlations for Sparse Graph Error Correcting Codes Decay of Correlations for Sparse Graph Error Correcting Codes

2009-03-10

arxiv.org/abs/0903.1842v1

Computer Science

Information Theory

40 pages, Submitted to SIAM Journal of Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Decay of Correlations for Sparse Graph Error Correcting Codes 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 Decay of Correlations for Sparse Graph Error Correcting Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decay of Correlations for Sparse Graph Error Correcting Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-122938