Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0903.1842 · SIAM Journal on Discrete Mathematics

Decay of Correlations for Sparse Graph Error Correcting Codes

Shrinivas Kudekar, Nicolas Macris

Published Jan 1, 2011• 15 citations
arXivHTMLPDF

Abstract

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 mechanics.

DOI
10.1137/090751827

Related papers

Decay of correlations in low density parity check codes: Low noise regime

Shrinivas Kudekar, Nicolas Macris

Consider transmission over a binary additive white gaussian noise channel using a fixed low-density parity check code. We consider the posterior measure over the code bits and the corresponding correlation between two codebits, averaged over the noise realizations. We show that for low enough noise variance this average correlation decays exponentially fast with the graph distance between the code bits. One consequence of this result is that for low enough noise variance the GEXIT functions (further averaged over a standard code ensemble) of the belief propagation and optimal decoders are the same.

arXiv:0901.3630•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•1 citation

Statistical physics methods for sparse graph codes

Shrinivas Kudekar

This thesis deals with the asymptotic analysis of coding systems based on sparse graph codes. The goal of this work is to analyze the decoder performance when transmitting over a general binary-input memoryless symmetric-output (BMS) channel. We consider the two most fundamental decoders, the optimal maximum a posteriori (MAP) decoder and the sub-optimal belief propagation (BP) decoder. The BP decoder has low-complexity and its performance analysis is, hence, of great interest. The MAP decoder, on the other hand, is computationally expensive. However, the MAP decoder analysis provides fundamental limits on the code performance. As a result, the MAP-decoding analysis is important in designing codes which achieve the ultimate Shannon limit. It would be fair to say that, over the binary erasure channel (BEC), the performance of the MAP and BP decoder has been thoroughly understood. However, much less is known in the case of transmission over general BMS channels. The combinatorial methods used for analyzing the case of BEC do not extend easily to the general case. The main goal of this thesis is to advance the analysis in the case of transmission over general BMS channels. To do this, we use the recent convergence of statistical physics and coding theory. Sparse graph codes can be mapped into appropriate statistical physics spin-glass models. This allows us to use sophisticated methods from rigorous statistical mechanics like the correlation inequalities, interpolation method and cluster expansions for the purpose of our analysis. One of the main results of this thesis is that in some regimes of noise, the BP decoder is optimal for a typical code in an ensemble of codes. This result is a pleasing extension of the same result for the case of BEC. An important consequence of our results is that the heuristic predictions of the replica and cavity methods of spin-glass theory are correct in the realm of sparse graph codes.

•Jan 1, 2009•3 citations

Decay of correlations: An application to low-density parity check codes

Shrinivas Kudekar, Nicolas Macris

Recently the decay of correlations between bits of low density generator matrix (LDGM) codes have been investigated by using high temperature expansions from statistical physics. In this work we apply these ideas to a special class of low density parity check codes (LDPC) on the binary input Gaussian white noise channel (BIAWGNC). We give a rigorous derivation of the maximum a posteriori (MAP) Generalized EXIT curve (the derivative with respect to the noise parameter of the input-output conditional entropy) for high values of the noise. Our result agrees with the formal expressions obtainable from replica calculations, and is the first result that fully justifies the replica formulas beyond the binary erasure channel (BEC). It also shows that the MAP and BP-GEXIT curves are equal in the high noise regime. The ensemble of LDPC codes considered here is constructed by adding randomly a sufficient fraction p of degree one variable nodes to a standard irregular LDPC(Lambda, P) Tanner graphs.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•3 citations

Sharp Bounds on Generalized EXIT Functions

Nicolas Macris

We consider communication over binary-input memoryless symmetric channels with low-density parity-check (LDPC) codes. The relationship between maximum a posteriori and belief propagation decoding is investigated using a set of correlation inequalities that first appeared in statistical mechanics of Gaussian spin glasses. We prove bounds on generalized extrinsic information transfer (EXIT) functions, that are believed to be tight, and discuss their relationship with the ones obtained by the interpolation method.

IEEE Transactions on Information Theory•Jun 28, 2007•46 citations

Conservation laws for coding

Cyril Méasson

This work deals with coding systems based on sparse graph codes. The key issue we address is the relationship between iterative (in particular belief propagation) and maximum a posteriori decoding. We show that between the two there is a fundamental connection, which is reminiscent of the Maxwell construction in thermodynamics. The main objects we consider are EXIT-like functions. EXIT functions were originally introduced as handy tools for the design of iterative coding systems. It gradually became clear that EXIT functions possess several fundamental properties. Many of these properties, however, apply only to the erasure case. This motivates us to introduce GEXIT functions that coincide with EXIT functions over the erasure channel. In many aspects, GEXIT functions over general memoryless output-symmetric channels play the same role as EXIT functions do over the erasure channel. In particular, GEXIT functions are characterized by the general area theorem. As a first consequence, we demonstrate that in order for the rate of an ensemble of codes to approach the capacity under belief propagation decoding, the GEXIT functions of the component codes have to be matched perfectly. This statement was previously known as the matching condition for the erasure case. We then use these GEXIT functions to show that in the limit of large blocklengths a fundamental connection appears between belief propagation and maximum a posteriori decoding. A decoding algorithm, which we call Maxwell decoder, provides an operational interpretation of this relationship for the erasure case. Both the algorithm and the analysis of the decoder are the translation of the Maxwell construction from statistical mechanics to the context of probabilistic decoding. We take the first steps to extend this construction to general memoryless output-symmetric channels. More exactly, a general upper bound on the maximum a posteriori threshold for sparse graph codes is given. It is conjectured that the fundamental connection between belief propagation and maximum a posteriori decoding carries over to the general case.

•Jan 1, 2006•29 citations

EBP-GEXIT Charts Over the Binary-Input AWGN Channel for Generalized and Doubly-Generalized LDPC Codes

Arti D. Yardi, Iryna Andriyanova, Charly Poulliat

This work proposes a tractable evaluation of the maximum a posteriori (MAP) threshold of sparse-graph ensembles, by using an approximation for the extended belief propagation generalized extrinsic information transfer (EBP-GEXIT) function, first proposed by Measson et al. The approximation allows to find a MAP threshold in such numerically involved cases as the binary-input additive white Gaussian noise (AWGN) channel, graph ensembles with general component codes and/or irregularities. The paper contains examples of estimations of the MAP thresholds in the case of irregular low-density parity-check (LDPC), generalized LDPC, and doubly generalized LDPC codes ensembles. Our estimations are confirmed by numerical simulations.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•4 citations
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 mechanics.
Consider transmission over a binary additive white gaussian noise channel using a fixed low-density parity check code. We consider the posterior measure over the code bits and the corresponding correlation between two codebits, averaged over the noise realizations. We show that for low enough noise variance this average correlation decays exponentially fast with the graph distance between the code bits. One consequence of this result is that for low enough noise variance the GEXIT functions (further averaged over a standard code ensemble) of the belief propagation and optimal decoders are the same.
This thesis deals with the asymptotic analysis of coding systems based on sparse graph codes. The goal of this work is to analyze the decoder performance when transmitting over a general binary-input memoryless symmetric-output (BMS) channel. We consider the two most fundamental decoders, the optimal maximum a posteriori (MAP) decoder and the sub-optimal belief propagation (BP) decoder. The BP decoder has low-complexity and its performance analysis is, hence, of great interest. The MAP decoder, on the other hand, is computationally expensive. However, the MAP decoder analysis provides fundamental limits on the code performance. As a result, the MAP-decoding analysis is important in designing codes which achieve the ultimate Shannon limit. It would be fair to say that, over the binary erasure channel (BEC), the performance of the MAP and BP decoder has been thoroughly understood. However, much less is known in the case of transmission over general BMS channels. The combinatorial methods used for analyzing the case of BEC do not extend easily to the general case. The main goal of this thesis is to advance the analysis in the case of transmission over general BMS channels. To do this, we use the recent convergence of statistical physics and coding theory. Sparse graph codes can be mapped into appropriate statistical physics spin-glass models. This allows us to use sophisticated methods from rigorous statistical mechanics like the correlation inequalities, interpolation method and cluster expansions for the purpose of our analysis. One of the main results of this thesis is that in some regimes of noise, the BP decoder is optimal for a typical code in an ensemble of codes. This result is a pleasing extension of the same result for the case of BEC. An important consequence of our results is that the heuristic predictions of the replica and cavity methods of spin-glass theory are correct in the realm of sparse graph codes.
Recently the decay of correlations between bits of low density generator matrix (LDGM) codes have been investigated by using high temperature expansions from statistical physics. In this work we apply these ideas to a special class of low density parity check codes (LDPC) on the binary input Gaussian white noise channel (BIAWGNC). We give a rigorous derivation of the maximum a posteriori (MAP) Generalized EXIT curve (the derivative with respect to the noise parameter of the input-output conditional entropy) for high values of the noise. Our result agrees with the formal expressions obtainable from replica calculations, and is the first result that fully justifies the replica formulas beyond the binary erasure channel (BEC). It also shows that the MAP and BP-GEXIT curves are equal in the high noise regime. The ensemble of LDPC codes considered here is constructed by adding randomly a sufficient fraction p of degree one variable nodes to a standard irregular LDPC(Lambda, P) Tanner graphs.
We consider communication over binary-input memoryless symmetric channels with low-density parity-check (LDPC) codes. The relationship between maximum a posteriori and belief propagation decoding is investigated using a set of correlation inequalities that first appeared in statistical mechanics of Gaussian spin glasses. We prove bounds on generalized extrinsic information transfer (EXIT) functions, that are believed to be tight, and discuss their relationship with the ones obtained by the interpolation method.
This work deals with coding systems based on sparse graph codes. The key issue we address is the relationship between iterative (in particular belief propagation) and maximum a posteriori decoding. We show that between the two there is a fundamental connection, which is reminiscent of the Maxwell construction in thermodynamics. The main objects we consider are EXIT-like functions. EXIT functions were originally introduced as handy tools for the design of iterative coding systems. It gradually became clear that EXIT functions possess several fundamental properties. Many of these properties, however, apply only to the erasure case. This motivates us to introduce GEXIT functions that coincide with EXIT functions over the erasure channel. In many aspects, GEXIT functions over general memoryless output-symmetric channels play the same role as EXIT functions do over the erasure channel. In particular, GEXIT functions are characterized by the general area theorem. As a first consequence, we demonstrate that in order for the rate of an ensemble of codes to approach the capacity under belief propagation decoding, the GEXIT functions of the component codes have to be matched perfectly. This statement was previously known as the matching condition for the erasure case. We then use these GEXIT functions to show that in the limit of large blocklengths a fundamental connection appears between belief propagation and maximum a posteriori decoding. A decoding algorithm, which we call Maxwell decoder, provides an operational interpretation of this relationship for the erasure case. Both the algorithm and the analysis of the decoder are the translation of the Maxwell construction from statistical mechanics to the context of probabilistic decoding. We take the first steps to extend this construction to general memoryless output-symmetric channels. More exactly, a general upper bound on the maximum a posteriori threshold for sparse graph codes is given. It is conjectured that the fundamental connection between belief propagation and maximum a posteriori decoding carries over to the general case.
This work proposes a tractable evaluation of the maximum a posteriori (MAP) threshold of sparse-graph ensembles, by using an approximation for the extended belief propagation generalized extrinsic information transfer (EBP-GEXIT) function, first proposed by Measson et al. The approximation allows to find a MAP threshold in such numerically involved cases as the binary-input additive white Gaussian noise (AWGN) channel, graph ensembles with general component codes and/or irregularities. The paper contains examples of estimations of the MAP thresholds in the case of irregular low-density parity-check (LDPC), generalized LDPC, and doubly generalized LDPC codes ensembles. Our estimations are confirmed by numerical simulations.