Linear-Programming Decoding of Nonbinary Linear Codes

• Published in: IEEE transactions on information theory 2009-09, Vol.55 (9), p.4134-4154
• Main Authors: Flanagan, M.F., Skachek, V., Byrne, E., Greferath, M.
• Format: Article
• Language: English
• Subjects: Additive white noise; Additives; Applied sciences; AWGN; Coded modulation; Codes; Coding, codes; Costs; Decision making; Decoders; Decoding; Error analysis; Exact sciences and technology; Information theory; Information, signal and communications theory; Linear code; Linear programming; linear-programming decoding; low-density parity-check (LDPC) codes; Modulation; Modulation coding; Modulation, demodulation; Parity check codes; Phase modulation; Phase shift keying; Polytopes; pseudocodewords; Representations; Signal and communications theory; Simulation; Symbols; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Transmission and modulation (techniques and equipments)
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2009.2025571

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.