AuthorsE. Rosnes and M. Helmling
TitleOn adaptive linear programming decoding of nonbinary linear codes over prime fields
AfilliationCommunication Systems
Project(s)SARDS: Secure and Reliable Distributed Storage Systems
Publication TypeProceedings, refereed
Year of Publication2016
Conference Name9th Int. Symp. Turbo Codes & Iterative Inf. Processing (ISTC)
Date Published09/2016
PublisherIEEE Press

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.

Citation Key25100