Binary linear codes with few weights from Boolean functions

Xiaoqiang Wang, Dabin Zheng, Yan Zhang

TL;DR

This paper introduces new methods for constructing binary linear codes with a limited number of distinct Hamming weights, leveraging the properties of Boolean functions. These codes are of interest for their potential applications in cryptography, secret sharing, and other areas, and the paper provides explicit constructions and analyses of their weight distributions, with some achieving optimal or near-optimal parameters.

What Problem Does This Paper Address?

The field of coding theory is constantly seeking to design efficient error-correcting codes. A particularly desirable property for many applications, such as secret sharing schemes and the construction of combinatorial designs, is for a code to have "few weights," meaning that its codewords have only a small number of distinct Hamming weights. Constructing such codes, especially binary linear codes, has been an active area of research. While many constructions exist, they often rely on specific types of functions and can be difficult to generalize or analyze. This paper aims to address this by providing general constructions for binary linear codes with three or four weights, using Boolean functions with limited Walsh transform values, and then analyzing their properties, including their weight distributions and those of their dual codes.

Methods

The core of this paper lies in constructing linear codes using Boolean functions. The authors define two general classes of binary linear codes, denoted $C_D$ and $C_{D'}$, based on specific defining sets $D$ and $D'$. These defining sets are constructed using pairs of Boolean functions, $f(x)$ and $g(y)$, that have at most three distinct Walsh transform values.

The first class of codes, $C_D$, is defined by a set $D = \{(x, y) \in \mathbb{F}_{2^m} \setminus \{(0,0)\} : f(x) + g(y) = 0 \text{ and } \text{Tr}(x + y) = \epsilon\}$, where $\epsilon \in \{0,1\}$. The second class, $C_{D'}$, uses a defining set $D' = \{(x, y) \in \mathbb{F}_{2^m} \setminus \{(0,0)\} : f(x) + g(y) = 0, \text{Tr}^2(x) = 0, \text{ and } \text{Tr}^2(y) = \epsilon\}$.

The paper then proceeds to:

  1. Analyze the Walsh transform properties of specific quadratic Boolean functions: This is crucial for understanding the behavior of the codes. Lemmas are presented that establish conditions under which $f(w)f(w+1)=0$, a property useful for constructing codes with few weights.
  2. Derive the weight distribution of the constructed codes: This involves intricate algebraic manipulations, often using the properties of trace functions and Walsh transforms. The Pless power moment identities are employed to determine the number of codewords at each weight.
  3. Determine the parameters of the dual codes: The dual code of a linear code is also important, and its parameters (length, dimension, minimum distance) are analyzed.
  4. Identify optimal or almost optimal codes: The constructed codes are compared against known tables of best codes to assess their optimality.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Boolean functions as building blocks for structured codes: The paper demonstrates how carefully chosen Boolean functions, particularly those with limited Walsh transform values, can be used to construct linear codes with a predictable and small number of Hamming weights.
  • The power of Walsh transform analysis: The analysis of Walsh transform values of Boolean functions is shown to be a powerful tool for understanding the weight distribution of the resulting codes. Properties like $f(w)f(w+1)=0$ are key to achieving few-weight codes.
  • Generalizable construction framework: The two proposed general constructions provide a flexible framework for generating families of linear codes with few weights by varying the underlying Boolean functions $f$ and $g$.
  • Connection to optimal codes: The paper successfully constructs several codes that are either optimal or almost optimal according to established benchmarks, highlighting the practical relevance of these theoretical constructions.
  • Dual codes are also interesting: The analysis extends to the dual codes, revealing their own properties and potential for applications.

Key Results

  • Two general constructions for binary linear codes with few weights: The paper presents two distinct methods for constructing linear codes with three or four weights using Boolean functions.
  • Explicit weight distributions and dual code parameters: For specific classes of Boolean functions satisfying certain conditions, the paper provides the exact weight distributions of the constructed codes and the parameters of their dual codes.
  • Identification of optimal and almost optimal codes: Several examples are given where the constructed codes and their duals match or closely approach the best known parameters for their respective lengths and dimensions. For instance, Example 4.8 shows codes with parameters [19,5,8] and [20,6,8] that are optimal.
  • Minimum distance analysis: The minimum distance of some of the constructed codes and their duals are determined, with some dual codes achieving a minimum distance of 3 or 4, which is significant.

Limitations and Future Work

  • Conditions on Boolean functions: The analysis of weight distributions often relies on specific conditions on the Walsh transform values of the Boolean functions $f$ and $g$. While the paper shows that such functions exist, finding and characterizing them for arbitrary parameters can be challenging.
  • Complexity of analysis: The algebraic derivations for weight distributions are complex and can be computationally intensive to generalize for all possible choices of $f$ and $g$.
  • Future Work: The paper suggests that the constructed codes may have applications in secret sharing schemes, association schemes, and strongly regular graphs. Further research could explore these applications in more detail. The authors also mention that the constructed codes are projective, which is a desirable property for certain combinatorial applications. Future work could focus on exploring these projective properties and their implications.

Summary updated

Abstract

Boolean functions have very nice applications in cryptography and coding theory, which have led to a lot of research focusing on their applications. The objective of this paper is to construct binary linear codes with few weights from the defining set, which is defined by some special Boolean functions and some additional restrictions. First, we provide two general constructions of binary linear codes with three or four weights from Boolean functions with at most three Walsh transform values and determine the parameters of their dual codes. Then many classes of binary linear codes with explicit weight enumerators are obtained. Some binary linear codes and their duals obtained are optimal or almost optimal. The binary linear codes obtained in this paper may have a special interest in secret sharing schemes, association schemes, strongly regular graphs.
BibTeX
@inproceedings{wang2021binary,
  author = {Xiaoqiang Wang and Dabin Zheng and Yan Zhang},
  title = {{Binary linear codes with few weights from Boolean functions}},
  booktitle = {Designs},
  year = {2021},
  doi = {10.1007/s10623-021-00898-0},
}
Figure