Several Families of Irreducible Constacyclic and Cyclic Codes

Zhonghua Sun, Xiaoqiang Wang, Cunsheng Ding

TL;DR

This paper provides a comprehensive characterization of several new families of irreducible constacyclic codes, settling their weight distributions and the parameters of their dual codes. By using these constacyclic codes as a mathematical "bridge," the authors also construct two new families of irreducible cyclic codes with high minimum distances, filling significant gaps in the existing coding theory literature.

What Problem Does This Paper Address?

In the world of digital communication, error-correcting codes (ECC) ensure that data remains intact despite noise. Cyclic codes are a popular choice because their algebraic structure allows for efficient encoding and decoding. However, cyclic codes have limitations; for instance, certain optimal codes (like specific MDS or Hamming codes) cannot be represented in a cyclic form under certain conditions.

Constacyclic codes are a broader generalization of cyclic codes. While they offer more flexibility and can represent a wider variety of optimal codes, they are much harder to analyze. Specifically, determining the weight distribution—the frequency of codewords with a specific number of non-zero elements—is a notoriously difficult problem. Previous research often relied on "Gaussian periods," which are computationally infeasible to evaluate for most cases. This paper aims to bypass these hurdles to settle the parameters for several important families of these codes.

Methods

The authors employ a sophisticated algebraic approach centered on the trace representation of codes over finite fields. The key methodological innovation is the introduction of three "associated" linear codes ($Exp_1, Exp_2,$ and $Exp_3$) for any given irreducible constacyclic code $C$.

By establishing the relationships between these four codes, the authors can translate difficult questions about constacyclic codes into more manageable problems involving cyclic codes. They use:

  • Cyclotomic Cosets: To study the factorization of polynomials that define the codes.
  • Pless Power Moments: To calculate the weight distributions of the dual codes.
  • Permutation Equivalence: Proving that certain new codes are essentially the same as well-known structures like quadratic-residue codes, which allows them to inherit desirable properties like high minimum distance.

Datasets

As a theoretical paper in mathematics and coding theory, no external datasets were used. Instead, the authors used the Magma software package to compute algebraic examples and verify their theoretical results. These examples (such as those in Tables 1 and 2) compare the newly constructed codes against the best-known linear codes maintained at codetables.de.

Key Insights and Ideas

  • The "Bridge" Concept: The most significant insight is using constacyclic codes as a bridge. The authors show that studying a constacyclic code can reveal the parameters of two different cyclic codes of different lengths, effectively expanding the toolkit for code construction.
  • Superiority over Cyclic Codes: The paper highlights that constacyclic codes can achieve what cyclic codes cannot. For example, they can be monomially equivalent to the optimal Simplex and Hamming codes even when no cyclic code can satisfy those parameters.
  • Square-Root Bounds: The authors successfully prove "square-root" bounds for their new cyclic families (e.g., $d \geq \sqrt{n}+1$). In coding theory, a minimum distance that scales with the square root of the block length is often a sign of a very high-quality, "dense" code.

Key Results

The paper settles the parameters for several families of codes, with the most notable results being:

  • New Cyclic Families: The construction of two specific families of irreducible cyclic codes:
  • $[2n, (n-1)/2, d \geq 2(\sqrt{n}+1)]$
    1. $[(q-1)n, (n-1)/2, d \geq (q-1)(\sqrt{n}+1)]$
  • Weight Distributions: The authors provide exact weight enumerators for several families, identifying them as one-weight, two-weight, or three-weight codes.
  • Optimality: Many of the constructed codes are shown to be distance-optimal or dimension-optimal, meaning no better code can exist with those specific parameters according to the Sphere Packing or Griesmer bounds.

Limitations and Future Work

The primary limitation is that the results are restricted to specific algebraic conditions—namely, when the length $n$ is a prime and the "order" of the field follows specific patterns (e.g., $ord_n(q) = (n-1)/2$).

The authors acknowledge that evaluating Gaussian periods remains a "hard problem" in number theory. Consequently, while this paper makes significant progress for specific families, a universal method for determining the weight distribution of all irreducible constacyclic codes remains out of reach. They invite the community to build on their "bridge" method to explore more general classes of irreducible codes.

Summary updated

Abstract

In this paper, several families of irreducible constacyclic codes over finite fields and their duals are studied. The weight distributions of these irreducible constacyclic codes and the parameters of their duals are settled. Several families of irreducible constacyclic codes with a few weights and several families of optimal constacyclic codes are constructed. As by-products, a family of $[2n, (n-1)/2, d \geq 2(\sqrt{n}+1)]$ irreducible cyclic codes over $\gf(q)$ and a family of $[(q-1)n, (n-1)/2, d \geq (q-1)(\sqrt{n}+1)]$ irreducible cyclic codes over $\gf(q)$ are presented, where $n$ is a prime such that $\ord_n(q)=(n-1)/2$. The results in this paper complement earlier works on irreducible constacyclic and cyclic codes over finite fields.
BibTeX
@misc{sun2022several,
  author = {Zhonghua Sun and Xiaoqiang Wang and Cunsheng Ding},
  title = {{Several Families of Irreducible Constacyclic and Cyclic Codes}},
  year = {2022},
  eprint = {2207.01864},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.01864},
}

Loading related content...

Figure