Improving code design limits using weight patterns and phases
Linear Programming Bounds for LCD Codes via Gauss Phases
Information TheoryDiscrete Mathematics
Summary
This paper explores a special type of error-correcting code called LCD codes that help detect and fix errors in data. The authors found a new way to understand these codes by studying certain mathematical values related to the code's structure. They used these insights to create a more precise method to calculate the best possible performance of these codes. Their approach improves previous techniques, giving tighter bounds on how well these codes can work. This helps researchers better understand and design more efficient error-correcting codes.
linear codeLCD codefinite fieldweight enumeratorlinear programmingHamming distancedual codeMacWilliams identitiesphase constraintserror-correcting codes
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.