Margin Propagation based XOR-SAT Solvers for Decoding of LDPC Codes
<|reference_start|>Margin Propagation based XOR-SAT Solvers for Decoding of LDPC Codes: 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.1$dB of the Sum-Product Algorithm for the same number of code iterations. It is also at least 10x lesser 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.<|reference_end|>
@article{nandi2024margin,
    title={Margin Propagation based XOR-SAT Solvers for Decoding of LDPC Codes},
    author={Ankita Nandi, Shantanu Chakrabartty, and Chetan Singh Thakur},
    journal={arXiv preprint arXiv:2402.04959},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.04959},
    primaryClass={cs.IT eess.SP math.IT}
}