An Improved A* Decoding Algorithm With List Decoding

Comparing with hard decision decoding algorithms, soft decoding has a lower probability of bit error but a higher computational complexity. As a maximum-likelihood soft decoding method, the A* algorithm is the most basic and widely used to minimize bit error probability. However, its average computational complexity strongly depends on a seed codeword and a heuristic function utilized during the decoding process. To efficiently reduce the computational complexity while maintaining the decoding accuracy theoretically and practically, this paper proposes an improved A* decoding algorithm consisting of two phases. The first phase applies the greedy list decoding to the linear block code to obtain a seed codeword. According to the seed, the second phase applies the improved A* algorithm to obtain the final decoding output. The heuristic function used in the A* algorithm is modified in two aspects: 1) use more information of partial decoded symbols to improve the accuracy of the function and 2) take advantage of Hamming distance to reduce the search space. Simulations on the RM(5, 2) Reed-Muller codes and [128, 64] binary extended BCH code show that this improved A* algorithm is more efficient in average decoding complexity than many other algorithms while maintaining the decoding accuracy.