New linear programming method improves bounds for error correcting codes
Linear Programming Bounds for LCD Codes via Gauss Phases
Information TheoryDiscrete Mathematics
Summary
This paper explores a special kind of error-correcting code called LCD codes, which are used to detect and correct errors in data. The authors found a new way to use math and linear programming to better understand and limit the possible arrangements of these codes, making the analysis more precise. Their new method uses fewer complex constraints but still improves on previous techniques. They tested their method on known cases and showed it can produce tighter bounds than existing approaches.
What this means in practice
- •For telecommunications engineers: Use the improved linear programming constraints to design error-correcting codes with better guaranteed error performance.
- •For software developers in data storage: Implement tighter verification steps for LCD codes to enhance data integrity checks in storage systems.
Authors
Ming-Hsuan Kang, Maosheng Xiong
Abstract
For $q\in\set{2,3}$, we show that a $k$-dimensional linear code over the finite field $\F_q$ of order $q$ is linear complementary dual (LCD) exactly when one root-of-unity value of its weight enumerator has magnitude $q^{k/2}$. We convert the phase of this value, together with the parity type in the binary case, into exact linear constraints on the weight distribution and incorporate them into a Gauss-phase linear program. The resulting program uses only the ordinary weight distributions of the code and its dual and adds only a constant-size set of branch equations to the usual Hamming/MacWilliams constraints, so it remains close in size to the standard Hamming LP while retaining additional arithmetic information. Computations over the audited binary and ternary ranges show systematic strengthening of the Hamming LCD relaxation. In the binary case, comparison with the established mixed joint-weight-enumerator LP yields four strict improvements, lowering the benchmark upper bound by one in each case. Each strict comparison is verified exactly by rational feasibility witnesses and integer Farkas certificates.