Lowering the error floor of Gallager codes: a statistical-mechanical view
From MaRDI portal
Publication:3301778
DOI10.1088/1742-5468/2014/10/P10042zbMATH Open1456.94133arXiv1407.0521MaRDI QIDQ3301778FDOQ3301778
Authors: Marco Pretti 
Publication date: 11 August 2020
Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1407.0521
Recommendations
Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Linear codes (general theory) (94B05)
Cites Work
- Title not available (Why is that?)
- Information, Physics, and Computation
- Factor graphs and the sum-product algorithm
- Statistical theory of superlattices
- Statistical Physics of Spin Glasses and Information Processing
- Regular and irregular progressive edge-growth tanner graphs
- Advanced mean field methods. Theory and practice
- A note on the cluster variation method.
- Survey propagation: An algorithm for satisfiability
- Divide and Concur and Difference-Map BP Decoders for LDPC Codes
- Message-passing algorithms for inference and optimization
- Lowering the Error Floor of LDPC Codes Using Cyclic Liftings
- Statistical mechanics of low-density parity-check codes
- Statistical theory of superlattices with unequal concentrations of the components
Cited In (2)
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)
