Lowering the error floor of Gallager codes: a statistical-mechanical view

DOI10.1088/1742-5468/2014/10/P10042zbMATH Open1456.94133MaRDI QIDQ3301778FDOQ3301778

Authors Marco Pretti 

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0521

Mathematics Subject Classification ID

Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Linear codes (general theory) (94B05)

Abstract: The problem of error correction for Gallager's low-density parity-check codes is famously equivalent to that of computing marginal Boltzmann probabilities for an Ising-like model with multispin interactions in a non-uniform magnetic field. Since the graph of interactions is locally a tree, the solution is very well approximated by a generalized mean-field (Bethe-Peierls) approximation. Belief propagation (BP) and similar iterative algorithms are an efficient way to perform the calculation, but they sometimes fail to converge, or converge to non-codewords, giving rise to a non-negligible residual error probability (error floor). On the other hand, provably-convergent algorithms are far too complex to be implemented in a real decoder. In this work we consider the application of the probability-damping technique, which can be regarded either as a variant of BP, from which it retains the property of low complexity, or as an approximation of a provably-convergent algorithm, from which it is expected to inherit better convergence properties. We investigate the algorithm behaviour on a real instance of Gallager code, and compare the results with state-of-the-art algorithms.

Recommendations

• Statistical mechanics of low-density parity-check codes
• Weight vs. Magnetization Enumerator for Gallager Codes
• Good error-correcting codes based on very sparse matrices
• Gallager error-correcting codes for binary asymmetric channels
• Improved low-density parity-check codes using irregular graphs

Cites work

• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• A note on the cluster variation method.
• Advanced mean field methods. Theory and practice
• Divide and Concur and Difference-Map BP Decoders for LDPC Codes
• Factor graphs and the sum-product algorithm
• Information, Physics, and Computation
• Lowering the Error Floor of LDPC Codes Using Cyclic Liftings
• Message-passing algorithms for inference and optimization
• Regular and irregular progressive edge-growth tanner graphs
• Statistical Physics of Spin Glasses and Information Processing
• Statistical mechanics of low-density parity-check codes
• Statistical theory of superlattices
• Statistical theory of superlattices with unequal concentrations of the components
• Survey propagation: An algorithm for satisfiability

Cited in

(2)

• Weight vs. Magnetization Enumerator for Gallager Codes
• Statistical Physics of Low Density Parity Check Error Correcting Codes

This page was built for publication: Lowering the error floor of Gallager codes: a statistical-mechanical view

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301778)