Margin Propagation Based XOR-SAT Solvers for Decoding of LDPC Codes
- 18 December 2024
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 73 (7) , 4588-4601
Abstract
Decoding of Low-Density Parity Check (LDPC) codes can be viewed as a special case of XOR-SAT problems, for which low-computational complexity bit-flipping algorithms have been proposed in the literature. However, a performance gap exists between the bit-flipping LDPC decoding algorithms and the benchmark LDPC decoding algorithms, such as the Sum-Product Algorithm (SPA). In this paper, we propose an XOR-SAT solver using log-sum-exponential functions and demonstrate its advantages for LDPC decoding. This is then approximated using the Margin Propagation formulation to attain a low-complexity LDPC decoder. The proposed algorithm uses soft information to decide the bit-flips that maximize the number of parity check constraints satisfied over an optimization function. The proposed solver can achieve results that are within 0.1dB of the Sum-Product Algorithm for the same number of code iterations. It is also at least 10× lower than other Gradient-Descent Bit Flipping decoding algorithms, which are also bit-flipping algorithms based on optimization functions. The approximation using the Margin Propagation formulation does not require any multipliers, resulting in significantly lower computational complexity than other soft-decision Bit-Flipping LDPC decoders.Keywords
All Related Versions
Funding Information
- USIEF-IIE Fulbright Fellowship and by the Washington University McDonnell International Scholars Academy
This publication has 33 references indexed in Scilit:
- A New Probabilistic Gradient Descent Bit Flipping Decoder for LDPC Codes2019
- A continuous-time MaxSAT solver with high analog performanceNature Communications, 2018
- Probabilistic Gradient Descent Bit-Flipping Decoders for Flash Memory Channels2018
- An event-based architecture for solving constraint satisfaction problemsNature Communications, 2015
- Improved Gradient Descent Bit Flipping algorithms for LDPC decoding2012
- An adaptive analog low-density parity-check decoder based on margin propagation2011
- Iterative Error Correction2009
- Sparse Decoding of Low Density Parity Check Codes Using Margin Propagation2009
- Self-corrected Min-Sum decoding of LDPC codes2008
- An Energy-Scalable Margin Propagation-Based Analog VLSI Support Vector Machine2007