Several classes of two-weight and three-weight linear codes.

Dabin Zheng, Zhao Qing, Xiaoqiang Wang

Abstract

Linear codes with few weights are essential for applications in secret sharing, authentication codes, and combinatorics. This paper constructs new classes of two-weight and three-weight linear codes using defining sets over finite fields. By applying the theory of quadratic forms and Weil sums, the authors determine explicit weight distributions and demonstrate that several resulting codes are optimal or almost optimal relative to the Griesmer bound.

Introduction

Linear codes are fundamental in digital communication and cryptography. A key characteristic of these codes is their weight distribution—the frequency of codewords with specific numbers of non-zero elements. Codes with a small number of distinct non-zero weights, such as two-weight or three-weight codes, are particularly valuable. They possess a rich mathematical structure that facilitates the construction of secret sharing schemes, authentication codes, and strongly regular graphs.

Construction Methodology

The research utilizes a "defining set" construction. For a finite field $\mathbb{F}_{p^m}$, a code $\mathcal{C}_D$ is defined by a set $D \subseteq \mathbb{F}_{p^m}^2$. The authors specifically investigate defining sets $D$ characterized by the trace equation: $$\text{Tr}(x^{p^k+1} + y^{p^\ell+1}) = c$$ where $c \in \mathbb{F}_p$. This approach generalizes previous work by allowing for flexible exponents ($p^k+1$ and $p^\ell+1$) and varying the constant $c$, thereby expanding the known families of few-weight codes.

To derive the parameters and weight distributions, the authors employ several advanced algebraic tools:

  • Quadratic Forms: The trace functions are analyzed as quadratic forms to determine the rank and structural properties of the codes.
  • Weil and Gaussian Sums: These exponential sums are critical for calculating the exact number of codewords for each weight.
  • Pless Power Moment Identities: These identities are used to verify the consistency of the derived weight distributions.

Analytical Results

The primary contribution of this work is the explicit determination of weight distributions for various parameter sets. The following tables illustrate the weight distributions for specific classes of two-weight codes derived in the study.

Weight distribution for a class of two-weight linear codes.
Weight distribution for an alternative class of two-weight linear codes.

These distributions show that the codes maintain a predictable structure, which is vital for their application in cryptographic protocols.

Optimality and Applications

A significant finding is that many of the constructed codes are optimal or near-optimal according to the Griesmer bound. For example, the paper identifies a $[16, 4, 9]$ code and a $[10, 4, 6]$ code that achieve the best possible minimum distance for their respective lengths and dimensions.

Furthermore, the high ratio of minimum to maximum weight ($w_{min}/w_{max} > (p-1)/p$) makes these codes ideal for secret sharing schemes. In such schemes, the "access structure" (the set of participants who can reconstruct the secret) is determined by the weights of the codewords; a high ratio ensures that the access structure is "nice" or democratic.

Conclusion

By generalizing existing construction techniques and applying rigorous algebraic analysis, this paper provides new families of linear codes with desirable weight properties. The results not only advance theoretical coding theory but also offer practical parameters for secure communication systems. Future research may explore higher-degree forms or different function classes, such as bent functions, to further expand the repertoire of optimal linear codes.

Summary updated

Abstract

Linear codes with few weights have been widely studied due to their applications in secret sharing, authentication codes, association schemes and strongly regular graphs. In this paper, we further construct several classes of new two-weight and three-weight linear codes from defining sets and determine their weight distributions by applications of the theory of quadratic forms and Weil sums over finite fields. Some of the linear codes obtained are optimal or almost optimal with respect to the Griesmer bound. This paper generalizes some results in~\cite{Jian2019,LiYueFu2016}.
BibTeX
@misc{zheng2019several,
  author = {Dabin Zheng and Zhao Qing and Xiaoqiang Wang},
  title = {{Several classes of two-weight and three-weight linear codes.}},
  year = {2019},
  eprint = {1911.03879},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.03879},
}

Loading related content...

Figure