2006/09/28 by Michael Chertkov, Chertkov, Michael, Vladimir Chernyak +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Computing Algorithms and Architecture #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.cs/0609154
openalex publication_date 2006/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.