A Two-Stage Soft-Decision Decoding Algorithm for BCH Codes

In this paper, we propose a two-stage soft-decision decoding (SDD) algorithm for BCH codes. At the first stage, we search for test error patterns (TEPs) according to the reliabilities of the received bits by using the flipping pattern tree (FPT) algorithm or the ordered reliability bits (ORB) technique, with a bounded number of searches. At the second stage, traditional algebraic hard-decision decoding (HDD), say, Berlekamp-Massey (BM) algorithm, is performed for these TEPs to find codewords. The proposed algorithm, referred to as FPT-BM algorithm or ORB-BM algorithm, can achieve near-optimal performance with a significantly small number of searches (dozens to hundreds). This enables efficient parallel implementation, ensuring low decoding latency and high throughput. To justify the sufficiency of the small number of searches, we provide qualitative reasoning and quantitative evaluation (using saddlepoint approximation) to show that the transmitted codeword under the proposed FPT-BM decoding strategy is reached much earlier in the search list than that under the single stage decoding (FPT-only). To analyze the performance, we calculate the upper bound on the performance gap between the proposed algorithm and maximum likelihood (ML) decoding based on the saddlepoint approximation, showing that the proposed algorithm can effectively approach the ML lower bound for high rate BCH codes. To reduce computational complexity, we introduce a filtering criterion, where the algebraic hard-decision decoding (BM decoding) is performed only for those candidates satisfying a sufficient number of parity-check equations. To determine the key parameters, we provide an intuitive criterion for the threshold in the filtering step based on the statistical analysis and a quantitative criterion for the maximum list size based on the upper bound on the performance gap to ML decoding. Numerical results demonstrate that: 1) By introducing the filtering criterion, the proposed FPT-BM algorithm effectively reduces the number of BM calls by half, with negligible performance loss, and outperforms the Chase-BM algorithm under the same filtering criterion; 2) The proposed decoding algorithm outperforms single stage decoding (FPT only) under limited search sizes; 3) For high rate BCH codes, the proposed decoding algorithm can approach the finite-length capacity, while for medium rate regions, the proposed decoding algorithm also exhibits better performance over FPT-only and BM-only decoding algorithms.