Polytope Representations for Linear-Programming Decoding of Non-Binary Linear Codes

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publication2008 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-6
PublisherIEEE
Pages1508-1512
ISBN (Print)978-1-4244-2256-2
DOIs
Publication statusPublished - 2008
MoE publication typeA4 Article in a conference publication
EventIEEE International Symposium on Information Theory - Toronto, Canada
Duration: 6 Jul 200811 Jul 2008

Publication series

Name IEEE International Symposium on Information Theory. Proceedings
PublisherIEEE
ISSN (Print)2157-8095
ISSN (Electronic)2157-8117

Conference

ConferenceIEEE International Symposium on Information Theory
Abbreviated titleISIT
CountryCanada
CityToronto
Period06/07/200811/07/2008

Cite this