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:cs/0407060 · IEEE Transactions on Information Theory

Tight Bounds for LDPC and LDGM Codes Under MAP Decoding

Andrea Montanari A

Published Aug 24, 2005• 105 citations
arXivHTMLPDF

Abstract

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

DOI
10.1109/tit.2005.853320

Related papers

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 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 method is illustrated on codes with Poisson left degree distributions when used over binary input output symmetric channels. However, it is arguably much more general. UMR 8549, Unité Mixte de Recherche du Centre National de la Recherche Scientifique et de l ’ Ecole Normale

•Jan 1, 2005•101 citations

Tight bounds for LDPC codes under MAP decoding

Andrea Montanari A

We present a new approach to the analysis of codes on graphs under symbol-maximum a posteriori probability (MAP) decoding. The approach is based on Guerra's interpolation technique for spin glasses. The basic idea is to consider a smooth interpolation between the original decoding problem, and a much simpler system in which each bit is retransmitted without coding through a (different) "effective" channel. Quite interestingly, the resulting expressions are strictly related to the density-evolution analysis of belief propagation decoding. The fundamental quantities involved in the interpolation procedure are, for instance, the same as in density evolution, i.e. densities of messages. Motivated by heuristic statistical mechanics results, we conjecture our bounds to be tight.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•2 citations

Sharp Bounds for Optimal Decoding of Low-Density Parity-Check Codes

Shrinivas Kudekar, Nicolas Macris

Consider communication over a binary-input memoryless output-symmetric channel with low-density parity-check (LDPC) codes and maximumaposteriori(MAP) decoding. The replica method of spin glass theory allows to conjecture an analytic formula for the average input-output conditional entropy per bit in the infinite block length limit. Montanari proved a lower bound for this entropy, in the case of LDPC ensembles with convex check degree polynomial, which matches the replica formula. Here we extend this lower bound to any irregular LDPC ensemble. The new feature of our work is an analysis of the second derivative of the conditional input-output entropy with respect to noise. A close relation arises between this second derivative and correlation or mutual information of codebits. This allows us to extend the realm of the ldquointerpolation method,rdquo in particular, we show how channel symmetry allows to control the fluctuations of the ldquooverlap parametersrdquo.

arXiv:0807.3065•IEEE Transactions on Information Theory•Sep 16, 2009•32 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

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information Theory•Jan 1, 2001•3,067 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information Theory•Jan 1, 2001•157 citations
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
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 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 method is illustrated on codes with Poisson left degree distributions when used over binary input output symmetric channels. However, it is arguably much more general. UMR 8549, Unité Mixte de Recherche du Centre National de la Recherche Scientifique et de l ’ Ecole Normale
We present a new approach to the analysis of codes on graphs under symbol-maximum a posteriori probability (MAP) decoding. The approach is based on Guerra's interpolation technique for spin glasses. The basic idea is to consider a smooth interpolation between the original decoding problem, and a much simpler system in which each bit is retransmitted without coding through a (different) "effective" channel. Quite interestingly, the resulting expressions are strictly related to the density-evolution analysis of belief propagation decoding. The fundamental quantities involved in the interpolation procedure are, for instance, the same as in density evolution, i.e. densities of messages. Motivated by heuristic statistical mechanics results, we conjecture our bounds to be tight.
Consider communication over a binary-input memoryless output-symmetric channel with low-density parity-check (LDPC) codes and maximumaposteriori(MAP) decoding. The replica method of spin glass theory allows to conjecture an analytic formula for the average input-output conditional entropy per bit in the infinite block length limit. Montanari proved a lower bound for this entropy, in the case of LDPC ensembles with convex check degree polynomial, which matches the replica formula. Here we extend this lower bound to any irregular LDPC ensemble. The new feature of our work is an analysis of the second derivative of the conditional input-output entropy with respect to noise. A close relation arises between this second derivative and correlation or mutual information of codebits. This allows us to extend the realm of the ldquointerpolation method,rdquo in particular, we show how channel symmetry allows to control the fluctuations of the ldquooverlap parametersrdquo.
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 present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.
We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.