Report
Decay of Correlations for Sparse Graph Error Correcting Codes
| العنوان: | Decay of Correlations for Sparse Graph Error Correcting Codes |
|---|---|
| المؤلفون: | Kudekar, Shrinivas, Macris, Nicolas |
| سنة النشر: | 2009 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Information Theory |
| الوصف: | 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. Comment: 40 pages, Submitted to SIAM Journal of Discrete Mathematics |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/0903.1842 |
| رقم الانضمام: | edsarx.0903.1842 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |