Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Adaptive linear programming decoding of nonbinary linear codes over prime fields
 IEEE transactions on information theory 66 (2020), Nr.3, S.12811317 ISSN: 00189448 

 Englisch 
 Zeitschriftenaufsatz 
 Fraunhofer ITWM () 
Abstract
In this work, we consider adaptive linear programming (ALP) decoding of linear codes over prime fields, i.e., the finite fields Fp of size p where p is a prime, when used over a pary input memoryless channel. In particular, we provide a general construction of valid inequalities (using no auxiliary variables) for the codeword polytope (or the convex hull) of the socalled constantweight embedding of a single paritycheck (SPC) code over any prime field. The construction is based on sets of vectors, called building block classes, that are assembled to form the lefthand side of an inequality according to several rules. In the case of almost doublysymmetric valid classes we prove that the resulting inequalities are all facetdefining, while we conjecture this to be true if and only if the class is valid and symmetric. Valid symmetric classes impose certain symmetry conditions on the elements of the vectors from the class, while valid doublysymmetric classes impose further technical symmetry conditions. For p = 3, there is only a single valid symmetric class and we prove that the resulting inequalities together with the socalled simplex constraints give a complete and irredundant description of the codeword polytope of the embedded SPC code. For p > 5, we show that there are additional facets beyond those from the proposed construction. As an example, for p =7, we provide additional inequalities that all define facets of the embedded codeword polytope. The resulting overall set of linear (in)equalities is conjectured to be irredundant and complete. Such sets of linear (in)equalities have not appeared in the literature before, have a strong theoretical interest, and we use them to develop an efficient (relaxed) ALP decoder for general (nonSPC) linear codes over prime fields. The key ingredient is an efficient separation algorithm based on the principle of dynamic programming. Furthermore, we construct a decoder for linear codes over arbitrary fields E q with q = p m and m > 1 by a factor graph representation that reduces to several instances of the case m =1, which results, in general, in a relaxation of the original decoding polytope. Finally, we present an efficient cutgenerating algorithm to search for redundant paritychecks to further improve the performance towards maximumlikelihood decoding for shorttomedium block lengths. Numerical experiments confirm that our new decoder is very efficient compared to a static LP decoder for various field sizes, checknode degrees, and block lengths.