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

Tight bounds for LDPC and LDGM codes under MAP decoding

Andrea Montanari A

Published Jan 1, 2005• 101 citations
OpenAlex

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

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

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

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

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

Asymptotic MAP upper bounds for LDPC codes

David Matas, Meritxell Lamarca

This paper aims at computing tight upper bounds for the maximum a posteriori threshold of low-density parity check codes in the asymptotic blocklength regime for the transmission over binary-input memoryless symmetric-output channels. While these bounds are already known, we propose a novel derivation based on a completely different approach: based solely on the concept of the chain rule and the conditional entropy, resorting to the concentration theorem for the code ensemble to compute the syndrome entropy with low complexity employing density evolution.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•0 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 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
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
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.
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.
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.
This paper aims at computing tight upper bounds for the maximum a posteriori threshold of low-density parity check codes in the asymptotic blocklength regime for the transmission over binary-input memoryless symmetric-output channels. While these bounds are already known, we propose a novel derivation based on a completely different approach: based solely on the concept of the chain rule and the conditional entropy, resorting to the concentration theorem for the code ensemble to compute the syndrome entropy with low complexity employing density evolution.