The $q$-ary antiprimitive BCH codes

Hongwei Zhu, Minjia Shi, Xiaoqiang Wang, Tor Helleseth

Abstract

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper.

Introduction

Bose-Chaudhuri-Hocquenghem (BCH) codes represent a cornerstone of algebraic coding theory, primarily due to their rigorous mathematical structure which facilitates efficient error-correction. While "primitive" BCH codes—those with length $n = q^m - 1$—have been extensively studied and deployed, "antiprimitive" BCH codes (where $n = q^m + 1$) present a more complex landscape. Despite their potential, the difficulty in determining their exact dimension ($k$) and minimum distance ($d$) has historically limited their application. This research provides a comprehensive analysis of these codes, establishing new bounds and identifying several families of optimal linear codes.

Mathematical Framework and Methodology

The study of antiprimitive BCH codes requires a deep dive into the properties of finite fields $\mathbb{F}_q$. The authors focus on the generator polynomial of these codes, which is defined by the roots in an extension field.

Coset Leader Analysis

A fundamental challenge in determining the dimension of a cyclic code is identifying the size of the cyclotomic cosets. This paper establishes a necessary and sufficient condition for identifying "coset leaders" modulo $q^m + 1$. By precisely counting these leaders, the researchers can determine the exact dimension of the resulting BCH codes, a task that is often computationally prohibitive for large $m$.

Elementary Symmetric Polynomials (ESPs)

To move beyond the standard BCH bound—which often underestimates the minimum distance—the authors utilize Elementary Symmetric Polynomials. By analyzing the symmetry of the code's roots, they derive tighter lower bounds for the minimum distance. This approach allows for the identification of codes that are "Maximum Distance Separable" (MDS) or "Almost Maximum Distance Separable" (AMDS), representing the theoretical limits of error-correction efficiency.

Key Results and Optimality

The theoretical findings were validated against the "Table of Best Known Linear Codes" (maintained at codetables.de). The results demonstrate that antiprimitive BCH codes are not merely theoretical constructs but are among the most efficient codes known.

Optimal Code Identification

Several new families of optimal codes were identified over fields such as $\mathbb{F}_4, \mathbb{F}_8$, and $\mathbb{F}_9$. For example, the authors proved that a specific code over $\mathbb{F}_4$ with length 17 and dimension 4 possesses a minimum distance of 12, matching the best-known parameters in existing databases. These findings suggest that antiprimitive BCH codes are highly competitive for practical applications.

Solving Long-standing Conjectures

The paper makes significant strides in solving open problems in the field. Specifically, it partially resolves Conjecture 23 from a 2017 study concerning ternary ($q=3$) BCH codes. The authors proved that for certain cases where $m$ is odd, the minimum distance is exactly 8, providing clarity to a previously speculative area of coding theory.

Security and Hardware Implementation

Beyond error correction, this research highlights the Linear Complementary Dual (LCD) property of antiprimitive BCH codes. LCD codes are of particular interest to the cryptography community because they provide inherent resistance against side-channel attacks (SCA) and fault-injection attacks. The fact that antiprimitive BCH codes naturally possess this property makes them ideal candidates for secure hardware implementations in resource-constrained environments.

Conclusion and Future Directions

This work advances the understanding of $q$-ary antiprimitive BCH codes by providing sharper bounds and proving the optimality of various code families. However, challenges remain. The authors note that for ternary codes where the length parameter $l$ is a multiple of 8 ($l \equiv 0 \pmod 8$), the minimum distance remains difficult to characterize. Future research is encouraged to explore these specific modular patterns and to extend the computational verification as $m$ increases, pushing the boundaries of what is possible in algebraic coding theory.

Summary updated

Abstract

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper.
BibTeX
@misc{zhu2021q,
  author = {Hongwei Zhu and Minjia Shi and Xiaoqiang Wang and Tor Helleseth},
  title = {{The $q$-ary antiprimitive BCH codes}},
  year = {2021},
  eprint = {2109.13803},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.13803},
}

Loading related content...

Figure