Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields

DOI10.1109/TIT.2019.2955504MaRDI QIDQ5123787zbMATH OpenOpenAlexFDO

Authors Eirik Rosnes, Michael Helmling

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.06959

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: In this work, we consider adaptive linear programming (ALP) decoding of linear codes over the finite field $mathbb{F}_p$ 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 $mathbb{F}_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 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.

This page was built for publication: Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5123787)