Linear-Programming Decoding of Nonbinary Linear Codes

DOI10.1109/TIT.2009.2025571MaRDI QIDQ4973980zbMATH OpenFDO

Authors Mark F. Flanagan, Vitaly Skachek, Eimear Byrne, Marcus Greferath

Publication date 8 August 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.4360

Mathematics Subject Classification ID

Linear programming (90C05) Applications of mathematical programming (90C90) Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: We develop a framework for linear-programming (LP) decoding of non-binary linear codes over rings. We prove that the resulting LP decoder has the `maximum likelihood certificate' property, and we show that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. LP decoding performance is illustrated for the (11,6,5) ternary Golay code with ternary PSK modulation over AWGN, and in this case it is shown that the LP decoder performance is comparable to codeword-error-rate-optimum hard-decision based decoding.

Cited in

(7)

• Monotonic optimization based decoding for linear codes
• Linear Programming Decoding of Spatially Coupled Codes
• An Efficient Pseudocodeword Search Algorithm for Linear Programming Decoding of LDPC Codes
• A New Linear Programming Approach to Decoding Linear Block Codes
• Iterative Approximate Linear Programming Decoding of LDPC Codes With Linear Complexity
• Analog Product Codes Decodable by Linear Programming
• Efficient Implementation of Linear Programming Decoding

This page was built for publication: Linear-Programming Decoding of Nonbinary Linear Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973980)