Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances: A Proof From the Polymer Expansion
 
research article

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

Macris, Nicolas  
•
Vuffray, Marc  
2016
Ieee Transactions On Information Theory

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.

  • Details
  • Metrics
Type
research article
DOI
10.1109/Tit.2016.2555843
Web of Science ID

WOS:000382135600013

Author(s)
Macris, Nicolas  
Vuffray, Marc  
Date Issued

2016

Publisher

Ieee-Inst Electrical Electronics Engineers Inc

Published in
Ieee Transactions On Information Theory
Volume

62

Issue

7

Start page

4003

End page

4023

Subjects

Low-density parity-check codes

•

low-density generator-matrix codes

•

graphical models

•

Bethe free energy

•

loop calculus

•

polymer expansion

•

expanders

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ISC  
Available on Infoscience
October 18, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/129849
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés