2017/08/23 by Rosnes, Eirik, Helmling, Michael
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1708.06959
In this work, we consider adaptive linear programming (ALP) decoding of linear codes over the finite field \mathbbFp of size p where p is a prime. In particular, we provide a general construction of valid inequalities for the codeword polytope of the so-called constant-weight embedding of a single parity-check (SPC) code over any prime field. The construction is based on classes of building blocks that are assembled to form the left-hand side of an inequality according to several rules. In the case of almost doubly-symmetric valid classes we prove that the resulting inequalities are all facet-defining, while we conjecture this to be true if and only if the class is valid and symmetric. For p=3, there is only a single valid symmetric class and we prove that the resulting inequalities together with the so-called simplex constraints give a completely 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. We use these inequalities to develop an efficient (relaxed) ALP decoder for general (non-SPC) 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 \mathbbFq with q=pm 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 cut-generating algorithm to search for redundant parity-checks to further improve the performance towards maximum-likelihood decoding for short-to-medium block lengths. Numerical experiments confirm that our new decoder is very efficient compared to a static LP decoder for various field sizes, check-node degrees, and block lengths.