  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.
