AuthorsE. Rosnes and M. Helmling
TitleOn adaptive linear programming decoding of linear codes over GF(8)
AfilliationCommunication Systems
Project(s)SARDS: Secure and Reliable Distributed Storage Systems
Publication TypeProceedings, refereed
Year of Publication2016
Conference NameInf. Theory Appl. (ITA)
Date Published02/2016
PublisherIEEE Press

In this work, we consider adaptive linear programming (LP) decoding of linear codes over GF(8). In particular, we give explicit constructions of valid inequalities (using no auxiliary variables) for the codeword polytope (or the convex hull) of the so-called constant-weight embedding of a single parity-check code over GF(8) that all are facet-defining. We conjecture that these inequalities together with so-called simplex constraints give a complete and irredundant description of the embedded (under the constant-weight embedding) codeword polytope. Furthermore, these sets of inequalities are used to develop an efficient (as compared to a static approach) exact (assuming that the conjecture is true) adaptive LP decoder for linear codes over GF(8). Numerical results show that only a very small subset of these inequalities is necessary for achieving close-to-exact LP decoding performance.

Citation Key25105