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.
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