Abstract

Background & Objective: BCH codes represent an important class of cyclic error-correcting codes, their minimum distances are known only for some cases and remains an open NP-Hard problem in coding theory, especially for large lengths. This paper presents an efficient scheme ZFSMP (Zimmermann Fragments Special Multiplier Permutation) to find the true value of the minimum distance for many large BCH codes. The proposed method consists of searching a codeword having the minimum weight by Zimmermann algorithm in the subcodes fixed by Fragments special multiplier permutation. ZFSMP is validated on all BCH codes of length up to 255 for which it gives the exact value of the minimum distance already known. For BCH codes of length 511, the comparison of ZFSMP with Augot Newton's identities and other heuristic methods prove its quality for giving more accurate results in very short time.

Conclusion: By exploiting the efficiency and the quickness of ZFSMP, the true minimum distances and consequently the error correcting capability of many BCH codes of length 1023, 2047, 4095, and 8191 are determined.

Keywords: Minimum distance, minimum weight, BCH codes, designed distance, Automorphism group, Multiplier, Simulated Annealing, metropolis algorithm, genetic algorithms, Ant Colony Optimization, hill-climbing, tabu search, Canteaut-chabaud algorithm, Newton’s identities, Zimmermann algorithm.

Graphical Abstract