Authors | E. Rosnes and M. Helmling |
Title | Constructing valid convex hull inequalities for single parity-check codes over prime fields |
Afilliation | Communication Systems |
Project(s) | SARDS: Secure and Reliable Distributed Storage Systems |
Status | Published |
Publication Type | Proceedings, refereed |
Year of Publication | 2016 |
Conference Name | IEEE International Symposium on Information Theory (ISIT) |
Pagination | 1939-1943 |
Date Published | 07/2016 |
Publisher | IEEE Press |
Abstract | In this work, we present an explicit construction of valid inequalities (using no auxiliary variables) for the convex hull 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. Such sets of inequalities have not appeared in the literature before, have a strong theoretical interest, and can be used to develop an efficient (relaxed) adaptive linear programming decoder for general (non-SPC) linear codes over prime fields. |
Citation Key | 25104 |