Linear-Programming Decoding of Nonbinary Linear Codes

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

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

46 Citations (Scopus)


A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-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 (ML) 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 LP 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 phase-shift keying (PSK) modulation over additive white Gaussian noise (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 low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

Original languageEnglish
Pages (from-to)4134-4154
Number of pages21
JournalIEEE Transactions on Information Theory
Issue number9
Publication statusPublished - Sept 2009
MoE publication typeA1 Journal article-refereed
EventIEEE International Symposium on Information Theory - Toronto, Canada
Duration: 6 Jul 200811 Jul 2008


  • pseudocodewords
  • coded modulation
  • linear-programming decoding
  • low-density parity-check (LDPC) codes


Dive into the research topics of 'Linear-Programming Decoding of Nonbinary Linear Codes'. Together they form a unique fingerprint.

Cite this