Efficient heuristic search algorithms for soft-decision decoding of linear block codes

Efficient new algorithms are presented for maximum-likelihood and suboptimal soft-decision decoding algorithms for linear block codes. The first algorithm, MA*, improves the efficiency of the A* decoding algorithm [14], conducting heuristic search through a code tree while exploiting code-specific properties. The second algorithm, H*, reduces search space by successively estimating the cost of the minimum-cost codeword with a fixed value at each of the most reliable and linearly independent components of the received message. The third algorithm, Directed Search, finds the codeword closest to the received vector by exploring a continuous search space. The strengths of these three algorithms are combined in a hybrid algorithm, applied to the (128, 64), the (256, 131), and the (256, 139) binary-extended Bose-Chaudhuri-Hocquenghem (BCH) codes. Simulation results show that this hybrid algorithm can efficiently decode the (128, 64) code for any signal-to-noise ratio, with near-optimal performance. Previously, no practical decoder could have decoded this code with such a performance for all ranges of signal-to-noise ratio.