Low-Complexity LP Decoding of Nonbinary Linear Codes
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 non-binary linear codes. However, the most important problem with LP decoding for both binary and non-binary 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 sub-gradient LCLP decoding algorithm.