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

We present <tex-math notation="LaTeX">O(m³) </tex-math> algorithms for specifying the support of minimum-weight codewords of extended binary BCH codes of length <tex-math notation="LaTeX">n=2ᵐ </tex-math> and designed distance <tex-math notation="LaTeX">d(m,s,i):=2ᵐ⁻¹⁻ˢ-2ᵐ⁻¹⁻ⁱ⁻ˢ </tex-math> for some values of <tex-math notation="LaTeX">$m,i,s$ </tex-math>, where m may grow to infinity. Here, the support is specified as the sum of two sets: a set of <tex-math notation="LaTeX">2²ⁱ⁻¹-2ⁱ⁻¹ </tex-math> elements, and a subspace of dimension <tex-math notation="LaTeX">$m-2i-s$ </tex-math>, specified by a basis. In some detail, for designed distance <tex-math notation="LaTeX">6· 2ʲ </tex-math>, <tex-math notation="LaTeX">j∈ \0,… ,m-4\ </tex-math>, we have a deterministic algorithm for even <tex-math notation="LaTeX">m≥ 4 </tex-math>, and a probabilistic algorithm with success probability <tex-math notation="LaTeX">1-O(2⁻ᵐ) </tex-math> for odd <tex-math notation="LaTeX">m> 4 </tex-math>. For designed distance <tex-math notation="LaTeX">28· 2ʲ </tex-math>, <tex-math notation="LaTeX">j∈ \0,… , m-6\ </tex-math>, we have a probabilistic algorithm with success probability <tex-math notation="LaTeX">≥ 1/3-O(2-m/2) </tex-math> for even <tex-math notation="LaTeX">m≥ 6 </tex-math>. Finally, for designed distance <tex-math notation="LaTeX">120· 2ʲ </tex-math>, <tex-math notation="LaTeX">j∈ \0,… , m-8\ </tex-math>, we have a deterministic algorithm for <tex-math notation="LaTeX">m≥ 8 </tex-math> divisible by 4. We also show how Gold functions can be used to find the support of minimum-weight words for designed distance <tex-math notation="LaTeX">$d(m,s,i)$ </tex-math> (for <tex-math notation="LaTeX">i∈ \0,… , m/2 \ </tex-math>, and <tex-math notation="LaTeX">s≤ m-2i </tex-math>) whenever <tex-math notation="LaTeX">$2i|m$ </tex-math>. Our construction builds on results of Kasami and Lin, who proved that for extended binary BCH codes of designed distance <tex-math notation="LaTeX">$d(m,s,i)$ </tex-math> (for integers <tex-math notation="LaTeX">m≥ 2 </tex-math>, <tex-math notation="LaTeX">0≤ i≤ m/2 </tex-math>, and <tex-math notation="LaTeX">0≤ s≤ m-2i </tex-math>), the minimum distance equals the designed distance. The proof of Kasami and Lin makes use of a non-constructive existence result of Berlekamp, and a constructive “down-conversion theorem” that converts some words in BCH codes to lower-weight words in BCH codes of lower designed distance. Our main contribution is in replacing the non-constructive counting argument of Berlekamp by a low-complexity algorithm. In one aspect, the current paper extends the results of Grigorescu and Kaufman, who presented explicit minimum-weight codewords for extended binary BCH codes of designed distance exactly 6 (and hence also for designed distance <tex-math notation="LaTeX">6· 2ʲ </tex-math>, by a well-known “up-conversion theorem”), as we cover more cases of the minimum distance. In fact, we prove that the codeword constructed by Grigorescu and Kaufman is a special case of the current construction. However, the minimum-weight codewords we construct do not generate the code, and are not affine generators, except, possibly, for a designed distance of 6.