How Many Weights Can a Cyclic Code Have?

Minjia Shi, Xiaoxiao Li, Alessandro Neri, Patrick SoléIEEE Trans. Information Theory 2020 · DOI

TL;DR

This paper investigates the maximum number of distinct nonzero weights a cyclic code can possess, introducing new upper and lower bounds for this quantity. The research also delves into specific types of cyclic codes, such as irreducible and strongly cyclic codes, and provides an algorithm for computing these bounds, offering insights into the structure and properties of these important error-correcting codes.

What Problem Does This Paper Address?

The paper tackles the question of how many different "nonzero weights" a cyclic code can have. In coding theory, the weight of a codeword is the number of its non-zero entries, and the weight distribution of a code is crucial for understanding its error-detecting and error-correcting capabilities. While previous work has explored the maximum number of weights for general linear codes, this paper focuses specifically on cyclic codes, a well-structured subclass of linear codes with applications in areas like data storage and communication. The core problem is to determine the function $\Gamma(k, q)$, which represents the largest number of nonzero weights a $k$-dimensional cyclic code over the finite field $\mathbb{F}_q$ can have. Understanding this function helps in designing codes with specific weight properties and in analyzing their performance.

Methods

The authors employ a combination of combinatorial arguments and algebraic techniques. They derive upper bounds on the number of weights by analyzing the "cycle structure" of cyclic codes and by utilizing weight concentration theorems. A key distinction is made between general cyclic codes and "strongly cyclic codes" (where nonzero codewords have a period equal to the code length), for which tighter upper bounds are established. The paper also introduces an algorithm to compute $\Gamma(k, q)$ for smaller values of $k$ and $q$. Furthermore, the research leverages results from the theory of Gaussian periods and character sums, and includes detailed analyses of specific code families like Reed-Muller and Hamming codes.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects of coding theory and does not involve empirical datasets.

Key Insights and Ideas

  • Distinction between Cyclic and Strongly Cyclic Codes: The paper highlights that "strongly cyclic" codes (a subclass of cyclic codes) exhibit different behavior regarding the number of weights, allowing for tighter upper bounds. This suggests that the specific structural properties of a code can significantly influence its weight spectrum.
  • Algorithmic Approach: The development of an algorithm to compute $\Gamma(k, q)$ is a significant contribution, enabling the exploration of this function for practical parameter values.
  • Connection to Other Code Families: The analysis of Reed-Muller and Hamming codes provides concrete examples and lower bounds, demonstrating the practical relevance of the theoretical findings. The paper reveals specific weight structures for these codes, which are of independent interest.
  • Asymptotic Behavior: The study of the asymptotic behavior of the number of weights as code length increases provides insights into the long-term properties of these codes.

Key Results

  • Upper Bounds: The paper provides new upper bounds for $\Gamma(k, q)$ and $\Gamma^o(k, q)$ (for strongly cyclic codes), which are shown to be particularly sharp for irreducible cyclic codes.
  • Lower Bounds: Lower bounds are derived using special codes and the covering radius of dual codes.
  • Algorithm: An algorithm is sketched for computing $\Gamma(k, q)$.
  • Specific Code Families: The number of weights in certain infinite families of Reed-Muller codes (binary and $q$-ary) and the $q$-ary Hamming code are determined. For example, the $q$-ary Hamming code ($H_q(r)$) is shown to have weights $\{0, 3, \dots, N\}$ where $N$ is the code length, with specific exceptions for small parameters.

Limitations and Future Work

  • Weak Lower Bounds: The paper acknowledges that the derived lower bounds are generally weak, often being linear in $k$, while upper bounds can be exponential. A major open problem is to find sharper lower bounds.
  • Extending Bounds: The authors express a desire to extend the exponential lower bounds on $\Gamma(k, q)$ to a wider range of parameters and fields.
  • Pattern Finding: Investigating local maxima of $n \to \Gamma(n, k, q)$ for large $n$ is suggested as a way to potentially uncover patterns and guide future research.
  • Computational Exploration: The paper proposes an effort to generate a table of $\Gamma(k, q)$ for modest values of $kq$ (e.g., $kq \le 100$) to aid in understanding.

Summary updated

BibTeX
@article{shi2020how,
  author = {Minjia Shi and Xiaoxiao Li and Alessandro Neri and Patrick Solé},
  title = {{How Many Weights Can a Cyclic Code Have?}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  doi = {10.1109/tit.2019.2946660},
}
Figure