1 Polytope Representations for Linear-Programming Decoding of Non-Binary Linear Codes
Vitaly Skachek, Mark F. Flanagan, Eimear Byrne, Marcus Greferath · 2012
Abstract — In previous work, we demonstrated how decoding of a non-binary linear code could be formulated as a linearprogramming 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 polynomialtime decoders for a wide variety of classical non-binary linear codes. I.