2011/05/24 by Shrinivas Kudekar, Kudekar, Shrinivas, Jason K. Johnson +3
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1105.4665
openalex publication_date 2011/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider transmission over a binary-input additive white Gaussian noise channel using low-density parity-check codes. One of the most popular techniques for decoding low-density parity-check codes is the linear programming decoder. In general, the linear programming decoder is suboptimal. I.e., the word error rate is higher than the optimal, maximum a posteriori decoder. In this paper we present a systematic approach to enhance the linear program decoder. More precisely, in the cases where the linear program outputs a fractional solution, we give a simple algorithm to identify frustrated cycles which cause the output of the linear program to be fractional. Then adding these cycles, adaptively to the basic linear program, we show improved word error rate performance.