Some punctured codes of several families of binary linear codes

Xiaoqiang Wang, Dabin Zheng, Cunsheng Ding

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)$:

  1. Almost Bent (AB) Functions: Highly nonlinear functions that exist in odd dimensions and provide excellent resistance to linear and differential cryptanalysis.
  2. Quadratic Functions: Specifically those of the form $x^{2^k+1}$, which are instrumental in constructing codes with predictable weight distributions.
  3. 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

Abstract

Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by $\mathcal{C}(f)=\left\{ {\rm Tr}(af(x)+bx)_{x \in \mathbb{F}_{q^m}^*}: a,b \in \mathbb{F}_{q^m} \right\}$, where $q$ is a prime power, $\bF_{q^m}^*=\bF_{q^m} \setminus \{0\}$, $\tr$ is the trace function from $\bF_{q^m}$ to $\bF_q$, and $f(x)$ is a function from $\mathbb{F}_{q^m}$ to $\mathbb{F}_{q^m}$ with $f(0)=0$. Almost bent functions, quadratic functions and some monomials on $\bF_{2^m}$ were used in the first construction, and many families of binary linear codes with few weights were obtained in the literature. This paper studies some punctured codes of these binary codes. Several families of binary linear codes with few weights and new parameters are obtained in this paper. Several families of distance-optimal binary linear codes with new parameters are also produced in this paper.
BibTeX
@misc{wang2021some,
  author = {Xiaoqiang Wang and Dabin Zheng and Cunsheng Ding},
  title = {{Some punctured codes of several families of binary linear codes}},
  year = {2021},
  eprint = {2101.08425},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.08425},
}

Loading related content...

Figure