Two Classes of Constacyclic Codes with Variable Parameters

Cunsheng Ding, Zhonghua Sun, Xiaoqiang Wang

TL;DR

This paper introduces two new families of constacyclic codes—a generalization of cyclic codes—constructed by leveraging the properties of cyclic codes over finite fields. The authors demonstrate that these new classes not only possess flexible parameters but also contain several "optimal" linear codes that meet or exceed the performance of traditional cyclic codes.

What Problem Does This Paper Address?

In the world of error-correcting codes, cyclic codes are the gold standard for practical use because their rich algebraic structure allows for very efficient encoding and decoding. However, cyclic codes have a limitation: they don't exist for every possible combination of length ($n$), dimension ($k$), and minimum distance ($d$).

Constacyclic codes are a broader family that includes cyclic codes as a special case. They offer a "best of both worlds" scenario: they maintain a strong algebraic structure (making them easier to implement in hardware/software) but provide more flexibility in their parameters. The challenge addressed here is the systematic construction of new constacyclic codes that are "optimal"—meaning they have the highest possible minimum distance for a given length and dimension—and understanding how their parameters behave as variables change.

Methods

The authors employ a "lifting" strategy. They start with well-understood cyclic codes of length $N = q^m - 1$ and use a general construction to derive constacyclic codes of a shorter length $n = (q^m - 1)/r$, where $r$ is a divisor of $q-1$.

The paper defines two specific classes based on different mathematical motivations:

  1. Class 1 (Dilix-motivated): These are constructed using defining sets based on the Hamming weight of $q$-adic expansions of integers. This approach is inspired by "punctured Dilix codes."
  2. Class 2 (Reed-Muller-motivated): These use defining sets based on the $q$-weight of integers, drawing inspiration from generalized Reed-Muller codes.

To analyze these codes, the authors use advanced tools from algebraic coding theory, including trace representations, cyclotomic cosets, and the BCH bound for constacyclic codes to prove lower limits on the codes' error-correcting capabilities.

Datasets

As a theoretical mathematics and coding theory paper, this work does not use traditional "datasets." Instead, the authors use the Magma software package to compute specific examples. These examples are then compared against established benchmarks in the field, such as:

  • The Griesmer Bound: A fundamental lower bound on the length of a linear code.
  • Grassl’s Tables: A well-known online database of the best-known linear codes for various parameters.

Key Insights and Ideas

  • Monomial Equivalence: A major "aha" moment is the proof that these new constacyclic families contain codes that are monomially equivalent to famous codes like Hamming codes and Simplex codes. This is significant because it shows these classic, high-performance codes can be represented in a constacyclic form even when a cyclic form might not exist for those specific parameters.
  • Algebraic Superiority: The authors highlight that for certain parameters $[n, k, d]$, a cyclic code may not even exist, but a $\lambda$-constacyclic code does. This justifies the study of constacyclic codes as a way to fill the gaps in the "parameter space" of efficient codes.
  • Distance Optimality: By carefully choosing the "defining set" (the roots of the generator polynomial), the authors identified specific instances that are distance-optimal, meaning no other linear code with the same length and dimension can have a better minimum distance.

Key Results

  • Optimal Codes: The paper identifies numerous specific optimal codes. For instance, Example 28 describes a $[40, 36, 3]$ code that is a "perfect code," and Example 66 identifies a new class of self-dual codes.
  • Hamming/Simplex Links: Corollary 20 explicitly proves that certain members of these families are equivalent to Hamming and Simplex codes, providing a new way to construct these essential tools.
  • General Bounds: The authors provide concrete mathematical formulas for the dimension and lower bounds for the minimum distance for both classes, allowing engineers to predict performance before construction.

Limitations and Future Work

  • Exact Distance Determination: While the authors provide strong lower bounds for the minimum distance ($d$), calculating the exact value for all variable parameters remains difficult. They explicitly list several Open Problems (e.g., Open Problems 26, 27, and 51) inviting the community to refine these bounds.
  • Automorphism Groups: The full symmetry (automorphism group) of these codes is only partially understood. Determining these groups for all cases is a suggested path for future research, as it could lead to even more efficient decoding algorithms.
  • Decoding Algorithms: While the paper focuses on construction and parameters, the development of specific, high-speed decoding algorithms tailored to these two new classes is a logical next step for practical application.

Summary updated

Abstract

Constacyclic codes over finite fields are a family of linear codes and contain cyclic codes as a subclass. Constacyclic codes are related to many areas of mathematics and outperform cyclic codes in several aspects. Hence, constacyclic codes are of theoretical importance. On the other hand, constacyclic codes are important in practice, as they have rich algebraic structures and may have efficient decoding algorithms. In this paper, two classes of constacyclic codes are constructed using a general construction of constacyclic codes with cyclic codes. The first class of constacyclic codes is motivated by the punctured Dilix cyclic codes and the second class is motivated by the punctured generalised Reed-Muller codes. The two classes of constacyclic codes contain optimal linear codes. The parameters of the two classes of constacyclic codes are analysed and some open problems are presented in this paper.
BibTeX
@misc{ding2022two,
  author = {Cunsheng Ding and Zhonghua Sun and Xiaoqiang Wang},
  title = {{Two Classes of Constacyclic Codes with Variable Parameters}},
  year = {2022},
  eprint = {2208.05664},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.05664},
}
Figure