A Maximum-Likelihood Decoding of BCH Codes

This paper presents the maximum-likelihood (ML) decoding of BCH codes, where the test error patterns (TEPs) are generated by the flipping pattern tree (FPT) based on soft weights and the hard-decision decoding algorithm is then applied to identify valid TEPs, with the most likely one selected as the output. We introduce ordered search strategies with earlystopping criteria and prove that the resulting decoder is an ML algorithm without exhaustive search. To determine the maximum number of searches, we propose a simple rule based on the upper bound on the performance gap to ML decoding, which can be efficiently computed using saddlepoint methods. Numerical results show that the proposed algorithm outperforms the Chase-BM algorithm in terms of the average number of searches, thanks to the optimized search order and early termination. They also show that for medium-To-high rate BCH codes, the proposed algorithm approaches the finite-length bound, while for lower rates, it offers significant advantages over both single-stage FPT and BM decoding, despite a gap to the finite-length capacity.