Decay of Correlations for Sparse Graph Error Correcting Codes
| dc.creator | Kudekar, Shrinivas | |
| dc.creator | Macris, Nicolas | |
| dc.date | 2009-03-10 | |
| dc.date.accessioned | 2026-07-07T12:51:32Z | |
| dc.date.available | 2026-07-07T12:51:32Z | |
| dc.description | 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. | |
| dc.description | 40 pages, Submitted to SIAM Journal of Discrete Mathematics | |
| dc.identifier | https://arxiv.org/abs/0903.1842 | |
| dc.identifier | http://arxiv.org/abs/0903.1842 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/223019 | |
| dc.subject | Information Theory | |
| dc.title | Decay of Correlations for Sparse Graph Error Correcting Codes | |
| dc.type | text |