Efficient Algorithms for Constructing Minimum-Weight Codewords in Some Extended Binary BCH Codes

Amit Berman, Yaron Shany, Itzhak Tamo

Abstract: This paper introduces efficient $O(m^3)$ algorithms for the explicit construction of minimum-weight codewords in several classes of extended binary Bose–Chaudhuri–Hocquenghem (BCH) codes. By transforming non-constructive existence proofs into concrete systems of multilinear equations, we provide a practical methodology for generating the specific error patterns that define a code's fundamental limits. These constructions are critical for stress-testing decoders and for applications in property testing.

1. Introduction

Bose–Chaudhuri–Hocquenghem (BCH) codes are fundamental to digital communications and storage systems, such as SSDs, due to their robust multi-error correction capabilities. However, two persistent challenges have historically limited their analysis: determining the exact minimum distance for arbitrary parameters and explicitly constructing codewords that achieve this minimum weight. While classical proofs by researchers such as Kasami, Lin, and Berlekamp established the existence of these codewords, they relied on non-constructive counting arguments. This work bridges the gap by providing a recipe for explicit construction.

2. Methodology

Our approach replaces traditional non-constructive arguments with a low-complexity algorithmic framework based on several key pillars:

  • System of Multilinear Equations: We demonstrate that finding a minimum-weight codeword is equivalent to solving a system of $i-1$ multilinear equations in $2i$ variables.
  • The "Flip" Insight: Rather than searching for a Boolean function within a fixed basis, we fix a specific quadratic Boolean function (related to the Reed-Muller subcode) and search for a basis that satisfies the BCH code's requirements.
  • Conversion Theorems: We utilize "down-conversion" and "up-conversion" theorems to mathematically transform known codewords between codes with different parameters (length or distance).
  • Gold Functions: For cases where the field dimension $m$ is a multiple of $2i$, we use Gold functions—a special class of polynomials—to specify the codeword support directly.

3. Key Results

The proposed algorithms operate in $O(m^3)$ time, where $n=2^m$ is the code length. This efficiency is significant as $m$ is logarithmic relative to the code length. The output is a compact representation of the codeword support, allowing even massive-weight codewords to be described using only $O(m)$ information.

Summary of explicit constructions for minimum-weight codewords across various parameters.

As shown in the table above, the framework provides deterministic solutions for many cases (e.g., even $m$) and probabilistic algorithms with high success rates ($1 - O(2^{-m})$) for more difficult parameters. Notably, this framework generalizes previous specific results, such as the weight-6 constructions by Grigorescu and Kaufman.

4. Discussion and Future Work

While this work provides broad coverage for several designed distances, it is not exhaustive. Heuristic gaps remain for certain parameters, such as the $i=3$ case with odd $m$, where a rigorous success probability is still an open problem. Furthermore, the constructed codewords do not necessarily serve as affine generators for the entire code at higher weights. Future research will explore higher-degree Boolean functions to address these limitations and extend the framework to more complex BCH code structures.

Summary updated

BibTeX
@article{berman2024efficient,
  author = {Amit Berman and Yaron Shany and Itzhak Tamo},
  title = {{Efficient Algorithms for Constructing Minimum-Weight Codewords in Some Extended Binary BCH Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  doi = {10.1109/tit.2024.3465218},
}
Figure