Almost MDS codes reveal new structure in designs and resolve Witt problem
On Almost MDS codes holding $(n-k-1)$-designs and an open problem on Witt design
Information Theory
Summary
This paper studies special types of error-correcting codes called almost maximum distance separable (AMDS) codes, focusing on the arrangements (designs) formed by the smallest building blocks in these codes. The authors find precise formulas describing related codes and their properties, which do not depend on the particular parts chosen but only on general parameters. As an important outcome, they solve a previously open question about the relationship between these codes and a known mathematical structure called the Witt design. This helps connect coding theory and combinatorial designs in a clearer way.
What this means in practice
- •For coding engineers: Use explicit formulas from this paper to analyze error patterns and code performance in almost MDS codes with design support.
- •For combinatorial design specialists: Leverage the characterization of complementary designs to better understand how code structure induces complex design relationships, including the Witt design.
Authors
Huakai Wei, Shiyuan Qiang, Shaofang Hong
Abstract
Let $\mathcal{C}$ be an almost maximum distance separable (AMDS) code over the finite fields with parameters $[n,k,n-k]$ whose minimum-weight codewords support an $(n-k-1)$-$(n,n-k,λ)$ design. We first determine the parameters of the dual code $\mathcal{C}^{\bot}$. We also characterize the design and its complementary design supported by the minimum weight codewords of $\mathcal{C}^{\bot}$. In particular, we present explicit formulas for the weight enumerators of all subset codes of $\mathcal{C}^{\bot}$ with length at least $k+1$. These formulas are completely determined by the cardinality of the subset, the dimension, together with the parameter $λ$, and are independent of the specific choice of subsets. As an application, we answer an open problem posed by Wang, Tang and Ding in 2023 by proving that the $3$-design supported by the minimum-weight codewords in their proposed cyclic dual code is isomorphic to the complementary design of the Witt spherical geometry design.