The duals of narrow-sense BCH codes with length $\frac{q^m-1}λ$

Xiaoqiang Wang, Chengliang Xiao, Dabin Zheng

TL;DR

This paper provides a significant generalization in coding theory by establishing new lower bounds on the minimum distance for the duals of narrow-sense BCH codes. It also identifies the precise conditions under which a BCH code is "dually-BCH"—meaning both the code and its dual belong to the BCH family—extending previous results to a much broader class of code lengths.

What Problem Does This Paper Address?

Bose-Chaudhuri-Hocquenghem (BCH) codes are a staple of modern digital communication and data storage because they offer a predictable error-correction capability and efficient decoding algorithms. While the properties of BCH codes themselves are well-documented, their dual codes (the set of all vectors orthogonal to the codewords) remain somewhat mysterious.

Understanding the dual of a code is crucial for several reasons: it helps in determining the code's weight distribution, understanding its performance under certain decoding schemes, and constructing new codes with specific properties. A particularly difficult challenge is determining the minimum distance of these dual codes—a key metric for their error-correction strength. Furthermore, it is rare for the dual of a BCH code to also be a BCH code. This paper tackles the gap in knowledge regarding these "dually-BCH" properties and provides tighter bounds for the minimum distance of duals for codes of length $n = \frac{q^m-1}{\lambda}$.

Methods

The authors employ a rigorous algebraic approach rooted in the theory of cyclic codes over finite fields ($\mathbb{F}_q$). Their primary tools include:

  • $q$-Cyclotomic Cosets: They analyze how integers modulo $n$ are grouped under multiplication by $q$. The structure of these cosets determines the "defining set" of the code.
  • $q$-adic Expansions: By representing integers in base $q$ and studying their properties (like circular shifts and consecutive zeros), the authors can estimate the size of the largest sequence of consecutive elements in the dual code's defining set.
  • BCH Bound: They apply the classical BCH bound to the newly discovered properties of the dual code's defining set to derive lower bounds for the minimum distance.
  • Computational Verification: The authors used Magma, a high-performance software package for algebra and number theory, to calculate the "true" minimum distances for specific code examples, allowing them to verify the tightness of their theoretical bounds.

Datasets

As a theoretical paper in mathematics and coding theory, this work does not use external datasets. Instead, it relies on mathematical proofs and specific parameter sets (values for $q, m, \lambda,$ and $\delta$) to demonstrate results. The "experimental" results mentioned are the exact minimum distances of specific codes computed via the Magma software.

Key Insights and Ideas

  • Generalization via $\lambda$: Previous research focused on specific lengths like $q^m-1$ (primitive) or $\frac{q^m-1}{q-1}$ (projective). By introducing the parameter $\lambda$ (where $\lambda | q-1$ or $\lambda = q^s-1$), the authors unified and extended several years of disparate research into a single framework.
  • The "Dually-BCH" Threshold: A major insight is that for most field sizes ($q > 2$), a narrow-sense BCH code is only dually-BCH if its designed distance $\delta$ is exceptionally large—specifically, larger than the first largest $q$-cyclotomic coset leader $\delta_1$.
  • Tightness of Bounds: The paper demonstrates that for certain parameters, the theoretical lower bounds derived are not just estimates but match the actual minimum distance exactly.
  • Improving on Classics: The authors show that for large designed distances, their new bounds are superior to classical results like the Sidel’nikov bound and the Carlitz-Uchiyama bound.

Key Results

  • Theorem 13 & 24: These provide the core mathematical formulas for the lower bounds of the dual minimum distance ($d^\perp$) for the two different cases of $\lambda$.
  • Theorem 18 & 30: These establish the "if and only if" conditions for a code to be dually-BCH. For example, if $q > 2$ or $s > 1$, the code is dually-BCH if and only if $\delta_1 < \delta \leq n$.
  • Concrete Examples:
    • For a binary code with $m=6, \delta=3, s=1$, the paper predicts a dual minimum distance of 32. Magma confirmed the true distance is exactly 32.
  • For $m=6, \delta=15$, the bound predicts 8, which was also confirmed as the true distance.

Limitations and Future Work

  • Tightness in All Cases: While the bounds are "good" and often tight, the authors acknowledge that they may not be tight for every possible combination of $q, m,$ and $\lambda$.
  • Coset Leader Complexity: Determining the exact values of the first and second largest $q$-cyclotomic coset leaders for a general $\lambda$ remains a difficult open problem (as noted in Remark 33).
  • Narrow-Sense Restriction: This study focuses on "narrow-sense" BCH codes (where the defining set starts at 1). Extending these dual properties to "non-narrow-sense" BCH codes remains a potential path for future research.

Summary updated

Abstract

BCH codes are an interesting class of cyclic codes due to their efficient encoding and decoding algorithms. In the past sixty years, a lot of progress on the study of BCH codes has been made, but little is known about the properties of their duals. Recently, in order to study the duals of BCH codes and the lower bounds on their minimum distances, a new concept called dually-BCH code was proposed by authors in \cite{GDL21}. In this paper, the lower bounds on the minimum distances of the duals of narrow-sense BCH codes with length $\frac{q^m-1}λ$ over $\mathbb{F}_q$ are developed, where $λ$ is a positive integer satisfying $λ\, |\, q-1$, or $λ=q^s-1$ and $s\, |\,m$. In addition, the sufficient and necessary conditions in terms of the designed distances for these codes being dually-BCH codes are presented. Many considered codes in \cite{GDL21} and \cite{Wang23} are the special cases of the codes showed in this paper. Our lower bounds on the minimum distances of the duals of BCH codes include the bounds stated in \cite{GDL21} as a special case. Several examples show that the lower bounds are good in some cases.
BibTeX
@misc{wang2023duals,
  author = {Xiaoqiang Wang and Chengliang Xiao and Dabin Zheng},
  title = {{The duals of narrow-sense BCH codes with length $\textbackslash\{\}frac\{q^m-1\}λ$}},
  year = {2023},
  eprint = {2312.05474},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.05474},
}

Loading related content...

Figure