  A framework for linear-programming (LP) decoding of nonbinary linear codes
over rings is developed. This framework facilitates linear-programming based
reception for coded modulation systems which use direct modulation mapping of
coded symbols. It is proved that the resulting LP decoder has the
'maximum-likelihood certificate' 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 linear-programming
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
the [11,6] ternary Golay code with ternary PSK modulation over 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 LDPC codes with
corresponding PSK modulations over AWGN.
