Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes

Abstract

We illustrate the utility of the recently developed loop calculus 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-Noise 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.

10 pages, 2 figures; Invited talk at 44-th annual Allerton Conference on Communications, Control and Computing, Sep 27-Sep 29, 2006

References in corpus (7)

• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes
• Loop series for discrete statistical models on graphs
• Towards Low-Complexity Linear-Programming Decoding
• Loop Calculus in Statistical Physics and Information Science
• Adaptive Linear Programming Decoding
• Characterizations of Pseudo-Codewords of LDPC Codes
• Improving convergence of Belief Propagation decoding

Cited by in corpus (9)

• Critical phenomena in complex networks
• Belief Propagation and Loop Series on Planar Graphs
• Polytope of Correct (Linear Programming) Decoding and Low-Weight Pseudo-Codewords
• Approximate inference on planar graphs using Loop Calculus and Belief Propagation
• New Understanding of the Bethe Approximation and the Replica Method
• Provably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC
• Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs
• A Separation Algorithm for Improved LP-Decoding of Linear Block Codes
• Bethe Free Energy Approach to LDPC Decoding on Memory Channels