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

IEEE Transactions on Information Theory

Sharp Bounds on Generalized EXIT Functions

Nicolas Macris

Published Jun 28, 2007• 46 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2007.899536

Related papers

Decay of Correlations for Sparse Graph Error Correcting Codes

Shrinivas Kudekar, Nicolas Macris

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.

arXiv:0903.1842•SIAM Journal on Discrete Mathematics•Jan 1, 2011•15 citations

Correlation inequalities: a useful tool in the theory of LDPC codes

Nicolas Macris

It is shown that a correlation inequality of statistical mechanics can be applied to low-density parity-check codes. Thanks to this tool we prove that the growth rate of regular LDPC codes, can be exactly calculated by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. We also consider communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code and prove that (at least part of) the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation decoder. In both problems, the correlation inequality yields sharp lower bounds. We also use a non trivial extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•8 citations

Griffith–Kelly–Sherman Correlation Inequalities: A Useful Tool in the Theory of Error Correcting Codes

Nicolas Macris

It is shown that a correlation inequality of statistical mechanics can be applied to linear low-density parity-check codes. Thanks to this tool we prove that, under a natural assumption, the exponential growth rate of regular low-density parity-check (LDPC) codes, can be computed exactly by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. Then, considering communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code we prove that, under a natural assumption, part of the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation algorithm. The correlation inequality yields a sharp lower bound on the GEXIT curve. We also make an extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem

IEEE Transactions on Information Theory•Jan 23, 2007•49 citations

Analysis of low-density parity-check codes based on EXIT functions

E. Sharon, Alexei Ashikhmin, Simon N. Litsyn

We exploit extrinsic information transfer functions of single parity-check and repetition codes over the binary input additive white Gaussian noise (biAWGN) channel, derived by the authors, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that this method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods

IEEE Transactions on Communications•Aug 1, 2006•38 citations

Tight Bounds for LDPC and LDGM Codes Under MAP Decoding

Andrea Montanari A

A new method for analyzing low-density parity-check (LDPC) codes and low-density generator-matrix (LDGM) codes under bit maximum a posteriori probability (MAP) decoding is introduced. The method is based on a rigorous approach to spin glasses developed by Francesco Guerra. It allows one to construct lower bounds on the entropy of the transmitted message conditional to the received one. Based on heuristic statistical mechanics calculations, we conjecture such bounds to be tight. The result holds for standard irregular ensembles when used over binary-input output-symmetric (BIOS) channels. The method is first developed for Tanner-graph ensembles with Poisson left-degree distribution. It is then generalized to "multi-Poisson" graphs, and, by a completion procedure, to arbitrary degree distribution

arXiv:cs/0407060•IEEE Transactions on Information Theory•Aug 24, 2005•105 citations

Typical performance of regular low-density parity-check codes over general symmetric channels

Toshiyuki Tanaka, David Saad

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay–Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.

arXiv:cond-mat/0204554•Journal of Physics A Mathematical and General•Oct 15, 2003•17 citations
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.
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.
It is shown that a correlation inequality of statistical mechanics can be applied to low-density parity-check codes. Thanks to this tool we prove that the growth rate of regular LDPC codes, can be exactly calculated by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. We also consider communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code and prove that (at least part of) the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation decoder. In both problems, the correlation inequality yields sharp lower bounds. We also use a non trivial extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem
It is shown that a correlation inequality of statistical mechanics can be applied to linear low-density parity-check codes. Thanks to this tool we prove that, under a natural assumption, the exponential growth rate of regular low-density parity-check (LDPC) codes, can be computed exactly by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. Then, considering communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code we prove that, under a natural assumption, part of the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation algorithm. The correlation inequality yields a sharp lower bound on the GEXIT curve. We also make an extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem
We exploit extrinsic information transfer functions of single parity-check and repetition codes over the binary input additive white Gaussian noise (biAWGN) channel, derived by the authors, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that this method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods
A new method for analyzing low-density parity-check (LDPC) codes and low-density generator-matrix (LDGM) codes under bit maximum a posteriori probability (MAP) decoding is introduced. The method is based on a rigorous approach to spin glasses developed by Francesco Guerra. It allows one to construct lower bounds on the entropy of the transmitted message conditional to the received one. Based on heuristic statistical mechanics calculations, we conjecture such bounds to be tight. The result holds for standard irregular ensembles when used over binary-input output-symmetric (BIOS) channels. The method is first developed for Tanner-graph ensembles with Poisson left-degree distribution. It is then generalized to "multi-Poisson" graphs, and, by a completion procedure, to arbitrary degree distribution
Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay–Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.