Loop calculus helps to improve belief propagation and linear programming decodings of low-density-parity-check codes

Michael Chertkov, Vladimir Y. Chernyak

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Citations (Scopus)

Abstract

We illustrate the utility of the recently developed loop calculus [1], [2] for improving the Belief Propagation (BP) algorithm. If the algorithm that minimizes the Bethe free energy fails we modify the free energy by accounting for a critical loop in a graphical representation of the code. The log-likelihood specific critical loop is found by means of the loop calculus. The general method is tested using an example of the Linear Programming (LP) decoding, that can be viewed as a special limit of the BP decoding. Considering the (155, 64, 20) code that performs over Additive-White-Gaussian channel we show that the loop calculus improves the LP decoding and corrects all previously found dangerous configurations of log-likelihoods related to pseudo-codewords with low effective distance, thus reducing the code's error-floor.

Original languageEnglish
Title of host publication44th Annual Allerton Conference on Communication, Control, and Computing 2006
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages31-40
Number of pages10
ISBN (Electronic)9781604237924
Publication statusPublished - 2006
Externally publishedYes
Event44th Annual Allerton Conference on Communication, Control, and Computing 2006 - Monticello, United States
Duration: 27 Sep 200629 Sep 2006

Publication series

Name44th Annual Allerton Conference on Communication, Control, and Computing 2006
Volume1

Conference

Conference44th Annual Allerton Conference on Communication, Control, and Computing 2006
Country/TerritoryUnited States
CityMonticello
Period27/09/0629/09/06

Fingerprint

Dive into the research topics of 'Loop calculus helps to improve belief propagation and linear programming decodings of low-density-parity-check codes'. Together they form a unique fingerprint.

Cite this