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:1310.1294 · IEEE Transactions on Information Theory

The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances: A Proof From the Polymer Expansion

Nicolas Macris, Marc Vuffray

Published Apr 28, 2016• 4 citations
arXivHTMLPDF

Abstract

The main objective of this paper is to explore the precise relationship between the Bethe free energy (or entropy) and the Shannon conditional entropy of graphical error correcting codes. The main result shows that the Bethe free energy associated with a low-density parity-check code used over a binary symmetric channel in a large noise regime is, with high probability, asymptotically exact as the block length grows. To arrive at this result, we develop new techniques for rather general graphical models based on the loop sum as a starting point and the polymer expansion from statistical mechanics. The true free energy is computed as a series expansion containing the Bethe free energy as its zeroth-order term plus a series of corrections. It is easily seen that convergence criteria for such expansions are satisfied for general high-temperature models. We apply these general results to the ensembles of low-density generator-matrix and parity-check codes. While the application to generator-matrix codes follows standard high temperature methods, the case of parity-check codes requires non-trivial new ideas, because the hard constraints correspond to a zero-temperature regime. Nevertheless, one can combine the polymer expansion with expander and counting arguments to show that the difference between the true and Bethe free energies vanishes with high probability in the large block length limit.

DOI
10.1109/tit.2016.2555843

Related papers

Beyond the Bethe free energy of LDPC codes via polymer expansions

Nicolas Macris, Marc Vuffray

The loop series provides a formal way to write down corrections to the Bethe entropy (and/or free energy) of graphical models. We provide methods to rigorously control such expansions for low-density parity-check codes used over a highly noisy binary symmetric channel. We prove that in the asymptotic limit of large size, with high probability, the Bethe expression gives an exact formula for the entropy (per bit) of the input word conditioned on the output of the channel. Our methods also apply to more general models.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•4 citations

Beyond the Bethe Free Energy of LDPC Codes via Polymer Expansions

Nicolas Macris, Marc Vuffray

The loop series provides a formal way to write down corrections to the Bethe entropy (and/or free energy) of graphical models. We provide methods to rigorously control such expansions for low-density parity-check codes used over a highly noisy binary symmetric channel. We prove that in the asymptotic limit of large size, with high probability, the Bethe expression gives an exact formula for the entropy (per bit) of the input word conditioned on the output of the channel. Our methods also apply to more general models.

arXiv:1202.2774•Feb 13, 2012•2 citations

Polymer Expansions for Cycle LDPC Codes

Nicolas Macris, Marc Vuffray

Abstract—We prove that the Bethe expression for the con-ditional input-output entropy of cycle LDPC codes on binary symmetric channels above the MAP threshold is exact in the large block length limit. The analysis relies on methods from statistical physics. The finite size corrections to the Bethe expression are expressed through a polymer expansion which is controlled thanks to expander and counting arguments. I.

arXiv:1202.2778•Jan 1, 2012•1 citation

Exact solution for the conditional entropy of Poissonian LDPC codes over the Binary Erasure Channel

Satish Babu Korada, Shrinivas Kudekar, Nicolas Macris

We consider communication over a binary erasure channel with low density parity check codes and optimal maximum a posteriori decoding. It is known that the problem of computing the average conditional entropy, over such code ensembles, in the asymptotic limit of large block length is closely related to computing the free energy of a mean field spin glass in the thermodynamic limit. Tentative, but explicit, formulas for these quantities have been derived thanks to the replica method (of spin glass theory) and are generally conjectured to be exact. In this contribution we show that the replica formulas are indeed exact in the case of Poissonian low density parity check ensembles. Our methods use ideas coming from the recent progress in the rigorous analysis of the Sherrington-Kirkpatrick model and their applications to the theory of error correcting codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•19 citations

Concentration to zero bit-error probability for regular LDPC codes on the binary symmetric channel: Proof by loop calculus

Marc Vuffray, Theodor Misiakiewicz

In this paper we consider regular low-density parity-check codes over a binary-symmetric channel in the decoding regime. We prove that up to a certain noise threshold the bit-error probability of the bit-sampling decoder converges in mean to zero over the code ensemble and the channel realizations. To arrive at this result we show that the bit-error probability of the sampling decoder is equal to the derivative of a Bethe free entropy. The method that we developed is new and is based on convexity of the free entropy and loop calculus. Convexity is needed to exchange limit and derivative and the loop series enables us to express the difference between the bit-error probability and the Bethe free entropy. We control the loop series using combinatorial techniques and a first moment method. We stress that our method is versatile and we believe that it can be generalized for LDPC codes with general degree distributions and for asymmetric channels.

arXiv:1509.05477•Allerton Conference on Communication, Control, and Computing•Sep 1, 2015•0 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 main objective of this paper is to explore the precise relationship between the Bethe free energy (or entropy) and the Shannon conditional entropy of graphical error correcting codes. The main result shows that the Bethe free energy associated with a low-density parity-check code used over a binary symmetric channel in a large noise regime is, with high probability, asymptotically exact as the block length grows. To arrive at this result, we develop new techniques for rather general graphical models based on the loop sum as a starting point and the polymer expansion from statistical mechanics. The true free energy is computed as a series expansion containing the Bethe free energy as its zeroth-order term plus a series of corrections. It is easily seen that convergence criteria for such expansions are satisfied for general high-temperature models. We apply these general results to the ensembles of low-density generator-matrix and parity-check codes. While the application to generator-matrix codes follows standard high temperature methods, the case of parity-check codes requires non-trivial new ideas, because the hard constraints correspond to a zero-temperature regime. Nevertheless, one can combine the polymer expansion with expander and counting arguments to show that the difference between the true and Bethe free energies vanishes with high probability in the large block length limit.
The loop series provides a formal way to write down corrections to the Bethe entropy (and/or free energy) of graphical models. We provide methods to rigorously control such expansions for low-density parity-check codes used over a highly noisy binary symmetric channel. We prove that in the asymptotic limit of large size, with high probability, the Bethe expression gives an exact formula for the entropy (per bit) of the input word conditioned on the output of the channel. Our methods also apply to more general models.
The loop series provides a formal way to write down corrections to the Bethe entropy (and/or free energy) of graphical models. We provide methods to rigorously control such expansions for low-density parity-check codes used over a highly noisy binary symmetric channel. We prove that in the asymptotic limit of large size, with high probability, the Bethe expression gives an exact formula for the entropy (per bit) of the input word conditioned on the output of the channel. Our methods also apply to more general models.
We consider communication over a binary erasure channel with low density parity check codes and optimal maximum a posteriori decoding. It is known that the problem of computing the average conditional entropy, over such code ensembles, in the asymptotic limit of large block length is closely related to computing the free energy of a mean field spin glass in the thermodynamic limit. Tentative, but explicit, formulas for these quantities have been derived thanks to the replica method (of spin glass theory) and are generally conjectured to be exact. In this contribution we show that the replica formulas are indeed exact in the case of Poissonian low density parity check ensembles. Our methods use ideas coming from the recent progress in the rigorous analysis of the Sherrington-Kirkpatrick model and their applications to the theory of error correcting codes.
In this paper we consider regular low-density parity-check codes over a binary-symmetric channel in the decoding regime. We prove that up to a certain noise threshold the bit-error probability of the bit-sampling decoder converges in mean to zero over the code ensemble and the channel realizations. To arrive at this result we show that the bit-error probability of the sampling decoder is equal to the derivative of a Bethe free entropy. The method that we developed is new and is based on convexity of the free entropy and loop calculus. Convexity is needed to exchange limit and derivative and the loop series enables us to express the difference between the bit-error probability and the Bethe free entropy. We control the loop series using combinatorial techniques and a first moment method. We stress that our method is versatile and we believe that it can be generalized for LDPC codes with general degree distributions and for asymmetric channels.
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.