Low-Complexity LP Decoding of Nonbinary Linear Codes

• Published in: IEEE transactions on communications 2013-08, Vol.61 (8), p.3073-3085
• Main Authors: Punekar, M., Vontobel, P. O., Flanagan, M. F.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Applied sciences; Binary system; Blocking; Channels; Codes; Coding, codes; Complexity; Complexity theory; coordinate-ascent algorithm; Decoding; Exact sciences and technology; Information, signal and communications theory; Iterative decoding; Keying; LDPC codes; Linear code; Linear programming; Linear programming decoding; Mathematical analysis; Modulation, demodulation; nonbinary codes; Signal and communications theory; Solvers; subgradient algorithm; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Transmission and modulation (techniques and equipments); Vectors
• ISSN: 0090-6778; 1558-0857
• DOI: 10.1109/TCOMM.2013.070213.120801

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z 4 , GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.