Abstract
Linear codes constructed via functions over finite fields have become a cornerstone of modern coding theory. This paper explores a refined approach to this construction by investigating the punctured versions of binary linear codes derived from almost bent (AB) functions, quadratic functions, and specific monomials over $\mathbb{F}_{2^m}$. By strategically selecting the "position set" for puncturing using trace functions and cyclotomic classes, the authors identify several new families of binary linear codes. These results include codes with few weights and several distance-optimal codes that achieve or exceed parameters documented in the current literature and standard databases.
Introduction
In the field of coding theory, the primary objective is the design of error-correcting codes with optimal parameters, denoted as $[n, k, d]$, where $n$ represents the code length, $k$ the dimension, and $d$ the minimum Hamming distance. A code is considered optimal if it possesses the largest possible minimum distance for a fixed length and dimension.
While general constructions for linear codes are well-established, identifying codes with a small number of distinct weight distributions ("few-weight codes") remains a significant challenge. Such codes are highly valued for their applications in secret sharing schemes, authentication codes, and the construction of strongly regular graphs. This research addresses a specific gap in the literature: while the base construction $\mathcal{C}(f) = \left\{ \text{Tr}(af(x)+bx)_{x \in \mathbb{F}_{q^m}^*}: a,b \in \mathbb{F}_{q^m} \right\}$ is well-understood, the potential for optimizing these codes through systematic puncturing—specifically how to define the set of coordinates to be removed—has been largely unexplored until now.
Methodology
The researchers utilized a base construction $\mathcal{C}(f)$ where codewords are generated using the trace function of $af(x) + bx$ over the finite field $\mathbb{F}_{2^m}$. The core innovation of this work lies in the puncturing technique, which involves deleting specific coordinates corresponding to a predefined "position set" $D$.
Function Selection
The study focuses on three primary types of functions $f(x)$:
- Almost Bent (AB) Functions: Highly nonlinear functions that exist in odd dimensions and provide excellent resistance to linear and differential cryptanalysis.
- Quadratic Functions: Specifically those of the form $x^{2^k+1}$, which are instrumental in constructing codes with predictable weight distributions.
- Monomials: Various power functions over $\mathbb{F}_{2^m}$.
Position Set Selection
Rather than employing random puncturing, the authors defined the position set $D$ using algebraic properties:
- Trace-Defined Sets: Sets defined as $D = \{x \in \mathbb{F}_{2^m}^* : \text{Tr}(\lambda f(x)) = \nu\}$.
- Cyclotomic Classes: Utilizing subgroups of the multiplicative group of the finite field to determine which bits to remove.
Analytical Framework
To determine the weight distributions and prove the optimality of the resulting codes, the authors employed Walsh transforms and Pless power moments. These mathematical tools allowed for the exact calculation of the frequency of each codeword weight, confirming the "few-weight" nature of the new constructions.
Key Insights and Results
The research demonstrates that puncturing is not merely a method for shortening a code, but a powerful optimization tool. By selecting $D$ via trace-based sets, the authors established an analytical bridge between the original code's algebraic structure and the punctured code's weight enumerator.
Notable Findings:
- AB Function-Derived Codes: The authors generated 5-weight and 6-weight codes. Notably, for $m=7$, they produced an optimal $[71, 13, 28]$ code and a $[56, 14, 20]$ code.
- Quadratic Function-Derived Codes: This family yielded distance-optimal codes, including a $[16, 10, 4]$ code and its dual $[16, 6, 6]$.
- Cyclotomic Codes: Using cyclotomic classes of order $t$, the researchers constructed codes with as few as three weights, such as a $[21, 7, 8]$ code which was proven to be optimal.
- Griesmer Bound: Several of the newly constructed codes were shown to meet the Griesmer bound, the fundamental lower limit on the length of a linear code for given $k$ and $d$.
Furthermore, the study observed that the dual codes of these punctured constructions frequently meet the Sphere Packing Bound, marking them as distance-optimal in their own right.
Conclusion and Future Directions
This paper successfully expands the library of known optimal binary linear codes by applying sophisticated puncturing techniques to established function-based constructions. The results were validated against the Database of Best Linear Codes (codetables.de), confirming their status as state-of-the-art.
Future research may focus on extending these techniques beyond binary fields to non-binary fields ($q > 2$). Additionally, while this study effectively managed specific sets $D$, the general problem of determining code parameters when the number of punctured bits is very large remains an open and complex challenge in coding theory. Exploring other families of power functions and monomials could also yield further improvements in code optimality.
Summary updated