Efficient Algorithms for Constructing Minimum-Weight Codewords in Some Extended Binary BCH Codes
share
We present O(m^3) algorithms for specifying the support of minimum-weight words of extended binary BCH codes of length n=2^m and designed distance d(m,s,i):=2^m-1-s-2^m-1-i-s for some values of m,i,s, where m may grow to infinity. The support is specified as the sum of two sets: a set of 2^2i-1-2^i-1 elements, and a subspace of dimension m-2i-s, specified by a basis. In some detail, for designed distance 6· 2^j, we have a deterministic algorithm for even m≥ 4, and a probabilistic algorithm with success probability 1-O(2^-m) for odd m>4. For designed distance 28· 2^j, we have a probabilistic algorithm with success probability ≥ 1/3-O(2^-m/2) for even m≥ 6. Finally, for designed distance 120· 2^j, we have a deterministic algorithm for m≥ 8 divisible by 4. We also present a construction via Gold functions when 2i|m. Our construction builds on results of Kasami and Lin (IEEE T-IT, 1972), who proved that for extended binary BCH codes of designed distance d(m,s,i), the minimum distance equals the designed distance. Their proof makes use of a non-constructive result of Berlekamp (Inform. Contrl., 1970), 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 argument of Berlekamp by a low-complexity algorithm. In one aspect, we extends the results of Grigorescu and Kaufman (IEEE T-IT, 2012), who presented explicit minimum-weight words for designed distance 6 (and hence also for designed distance 6· 2^j, by a well-known “up-conversion theorem”), as we cover more cases of the minimum distance. However, the minimum-weight words we construct are not affine generators for designed distance >6.
READ FULL TEXT