|Authors||E. Rosnes and M. Helmling|
|Title||On adaptive linear programming decoding of nonbinary linear codes over prime fields|
|Project(s)||SARDS: Secure and Reliable Distributed Storage Systems|
|Publication Type||Proceedings, refereed|
|Year of Publication||2016|
|Conference Name||9th Int. Symp. Turbo Codes & Iterative Inf. Processing (ISTC)|
In this work, we study linear programming (LP) decoding of nonbinary linear codes over prime fields. In particular, we develop a novel separation algorithm for valid inequalities describing the codeword polytope of the so-called constant-weight embedding of a single parity-check (SPC) code over any prime field. The algorithm has linear (in the length of the SPC code) complexity, is structurally different from the one for binary codes, and is based on the principle of dynamic programming. Furthermore, it is the basis of the proposed efficient (relaxed) adaptive LP (ALP) decoder for general (non-SPC) linear codes over any prime field, generalizing the well-known ALP decoding algorithm for binary codes. Numerical results show that the ALP decoding algorithm is very efficient compared to a static approach.