Polytope Representations for Linear-Programming Decoding of Non-Binary Linear Codes
arXiv:0712.4075 · doi:10.1109/ISIT.2008.4595239
Abstract
In previous work, we demonstrated how decoding of a non-binary linear code could be formulated as a linear-programming problem. In this paper, we study different polytopes for use with linear-programming decoding, and show that for many classes of codes these polytopes yield a complexity advantage for decoding. These representations lead to polynomial-time decoders for a wide variety of classical non-binary linear codes.
5 pages, to appear in 2008 IEEE International Symposium on Information Theory