Source-linked AI summary
Solutions to Three Conjectures and an Open Problem on Binary BCH Codes
Xiaoqiang Wang, Jiawei He, Boru Yi, Dabin Zheng
TL;DR
The paper tackles unresolved exact minimum distances and an open existence problem for binary BCH codes. It constructs codewords meeting BCH bounds, determines a harder family’s distance in several cases, and obtains qualified answers for the open problem.
Problem
Exact minimum distances of binary BCH codes remain difficult to determine, despite BCH lower bounds and known defining sets and dimensions.
Method
The paper constructs codewords attaining BCH lower bounds using finite-field subgroups, roots of unity, irreducible polynomials, and lifting arguments.
Results
The three conjectures are settled; the harder family has minimum distance 5 for several infinite classes of s, and Open Problem 8.4 receives affirmative first-two-family answers plus a qualified third-family result.
Takeaways & Limitations
The paper settles the conjectures considered and extends exact-distance and existence analysis to additional binary BCH-code families.
Abstract
from arXiv · showhide
BCH codes are among the most important classes of cyclic codes and have played a central role in coding theory and its applications. One of the fundamental problems in the study of BCH codes is to determine their exact minimum distances, which directly govern their error-correcting capability. Although the BCH bound provides a general lower bound, determining the exact minimum distance is often difficult, and many parameter families remain unresolved. In this paper, we investigate three conjectures and an open problem on binary BCH codes proposed by Chen, Xie, and Ding in \cite{Chen59}. We settle these conjectures on the exact minimum distances of three families of binary BCH codes by constructing codewords attaining the BCH bound. Beyond these conjectures, we further study the more difficult family codes and determine its minimum distance for some cases. We further study Open Problem 8.4: affirmative answers are obtained for the first two length families, while for the third family a sufficient condition is established and a counterexample shows that the unrestricted assertion does not hold in general.
I. INTRODUCTION
The paper addresses unresolved exact minimum-distance questions for binary BCH codes by settling three conjectures, extending analysis to a harder family, and studying Open Problem 8.4.
- I. INTRODUCTION: The arithmetic structure of BCH-code length influences cyclotomic cosets, defining sets, and code parameters.The introduction places this observation in the context of prior work on primitive, antiprimitive, and other special-length BCH codes.
- I. INTRODUCTION: Exact minimum distances of BCH codes can remain undetermined even when defining sets and dimensions are known.The BCH bound supplies a lower bound, but attaining it requires constructing a codeword with the corresponding weight.
- I. INTRODUCTION: The paper settles three conjectures on binary BCH-code minimum distances by constructing codewords that attain the corresponding BCH lower bounds.The proofs use finite-field subgroups and constructions involving roots of unity, irreducible polynomials, or lifting from primitive BCH codes.
- I. INTRODUCTION: The study also determines the minimum distance of C(2,2^2s+2^s+1,5,1) for several infinite families of s.This family is described as more difficult than C(2,2^2s+2^s+1,3,1), and the results use explicit constructions over finite fields and polynomials.
- I. INTRODUCTION: For Open Problem 8.4, the paper gives affirmative answers for the first two length families and a sufficient condition plus a counterexample for the third.The affirmative results combine a cyclotomic-coset estimate with the BCH bound; the unrestricted assertion fails for all admissible pairs in general.
II. PRELIMINARIES
The preliminaries specify that the paper works with powers of 2 and, unless otherwise stated, binary codes.
- II. PRELIMINARIES: Throughout the paper, q is a power of 2 and Fq denotes the finite field with q elements.
- II. PRELIMINARIES: Unless otherwise stated, all codes considered are binary.
A. Cyclotomic cosets and factorization of xn −1
The section defines q-cyclotomic cosets and connects them to BCH-code factorization, defining sets, dimensions, and coset-size estimates.
- A. Cyclotomic cosets and factorization of x^n −1: The q-cyclotomic coset containing i consists of the residues iq^j mod n generated by repeated multiplication by q.Its cardinality is the smallest positive period returning iq^j to i modulo n, and its smallest element is the coset leader.
- A. Cyclotomic cosets and factorization of x^n −1: Distinct q-cyclotomic cosets partition Z_n, and every coset has cardinality at most m=ord_n(q).
- A. Cyclotomic cosets and factorization of x^n −1: A primitive n-th root of unity β is obtained from a primitive element α of F_q^m via β=α^((q^m−1)/n).The minimal polynomial of β^i over F_q is then used in the factorization framework.
- A. Cyclotomic cosets and factorization of x^n −1: For a cyclic code, the defining set is a union of q-cyclotomic cosets, so deg g(x)=|T(C)| and dim(C)=n−|T(C)|.In the binary case, C_2i=C_i, an identity used repeatedly later.
B. BCH codes and the BCH bound
The paper defines BCH codes as cyclic codes specified through generator polynomials and defining sets, with narrow-sense and primitive cases identified by b and n.
- BCH codes C(q,n,δ,b) are cyclic codes defined using a generator polynomial for parameters δ and b.
- When b = 1, a BCH code is called narrow-sense; when n = q^m − 1, it is called primitive.
- The BCH bound supplies the lower-bound framework used throughout the paper.
- For δ = 3, C(2,2^m−1,3,1) is a binary Hamming code with generator polynomial m_1(x).
- For δ = 5, C(2,2^m−1,5,1) has generator polynomial m_1(x)m_3(x).
III. THREE MINIMUM DISTANCE CONJECTURES FOR BINARY BCH CODES
The paper addresses three binary BCH-code families whose exact minimum distances had not been fully determined and settles the associated conjectures.
- Three binary BCH-code families previously lacked fully determined minimum distances.
- The paper settles three conjectures by determining the corresponding codes’ minimum distances.
A. The family n = (22s + 1)(2s −1)
For the family n = (2^(2s) + 1)(2^s − 1), the paper constructs weight-5 codewords and proves minimum distance 5 for every s ≥ 2, confirming the conjecture uniformly.
- Five pairwise distinct field elements satisfy the additive conditions needed to construct a weight-5 codeword.
- For s ≥ 2, C(2,n,5,1) has parameters [n, n − 8s, 5] when n = (2^(2s) + 1)(2^s − 1).
- The BCH bound gives the lower bound, while the constructed codeword gives the matching upper bound.
- The resulting equality is d(C(2,n,5,1)) = 5.
- The construction covers all residue classes of s modulo 4, including the previously unresolved case s ≡ 2 (mod 4).
B. The family n = 22s + 2s + 1
For the family n = 2^(2s) + 2^s + 1, the paper constructs low-weight codewords to establish exact distances for the stated BCH families and confirms the associated conjecture across all s.
- An irreducible cubic over F_q yields three distinct elements whose sum is zero, producing a weight-3 codeword.
- For s ≥ 2, C(2,n,3,1) has parameters [n, n − 3s, 3] with n = 2^(2s) + 2^s + 1.
- Theorem 12 completely confirms Conjecture 5.3, including the cases previously left open for odd s.
- The constructed codeword gives d(C(2,n,3,1)) ≤ 3, while the BCH bound supplies the matching lower bound.
- For the more involved C(2,n,5,1) family, the paper constructs five distinct elements under the conditions s ≡ 2 or 4 (mod 6), or 5 | s with 15 ∤ s.
- Under these constructions, C(2,n,5,1) has parameters [n, n − 6s, 5].
C. The family n = (4s −1)/3
For the family n = (4s −1)/3, the paper settles Conjecture 6.9 by proving a degree-six polynomial is irreducible with roots of multiplicative order 21, then constructing weight-five codewords.
- Polynomial construction: The polynomial h(X) is irreducible because it has no irreducible factor of degree at most 3, while deg h(X) = 6.
- Polynomial construction: Every root θ of h(X) has multiplicative order exactly 21.
- Codeword construction: The elements 1, θ, θ6, θ8, and θ18 are pairwise distinct and satisfy x + y + z + u + v = 0.
- Codeword construction: C(2,n,5,1) has parameters [n, n −4s, 5] for s ≥2, so the construction attains minimum distance 5.
IV. OPEN PROBLEM ON BINARY BCH CODES
The paper studies Open Problem 8.4 by deriving a general construction and analyzing three length families. It obtains affirmative answers for the first two families, while the third requires a condition and has counterexamples without it.
- Open Problem 8.4 asks whether suitable integers δ and b exist for BCH codes across three length families.
- General construction: The paper begins with a general construction based on defining sets, binary cyclotomic cosets, and the BCH bound.
- Length families: For n = (2^2s + 1)(2^s −1) and n = 2^2s + 2^s + 1, the proof verifies the required inequalities and completes the affirmative cases.
- Counterexample: The counterexample (s, λ) = (18, 13797) gives n = 19 and demonstrates failure of the unrestricted assertion.
- Length families: For the third family, an affirmative answer holds under a suitable condition on n and s, but not for all admissible pairs (s, λ).
V. CONCLUSION
The paper settles three exact minimum-distance conjectures for binary BCH codes, extends analysis to a more difficult family, and clarifies Open Problem 8.4. It constructs codewords attaining the BCH bound, proves distance 5 for several infinite classes, and finds both affirmative cases and a counterexample for the open problem.
- The three conjectures on exact minimum distances of binary BCH code families are completely settled.
- The BCH lower bound is attained in each conjectured family by explicitly constructing a codeword with the corresponding minimum weight.
- The paper investigates a more difficult BCH code whose minimum-distance problem exceeds those in the original conjectures.
- For several infinite classes of s, the more difficult code has minimum distance 5.
- Open Problem 8.4 has affirmative answers for the first two length families, but its unrestricted statement is false in general because of a counterexample.