An Improved A~* Decoding Algorithm With List Decoding

Compared to the hard decision decoding algorithm,soft decisions can use more extra information,enabling the algorithm to make more accurate decisions.Even with the same idea used in the method,soft decision decoding has more coding gains,so soft decision decoding has been widely studied and used.This paper first introduces the channel coding theory and describes two main problems in this field.The first problem is how to construct progressively good codewords with infinite length;the second problem is how to achieve maximum likelihood decoding under certain complexity constraints.The current research hotspot is to find some quasi-optimal decoding methods.These quasi-optimal decoding algorithms have performance close to maximum likelihood decoding and simple engineering implementation.Secondly,this paper introduces the development process of soft decision decoding.The soft decision decoding algorithm has a higher computational complexity in the case of guaranteeing a lower bit error probability.Therefore,some intelligent techniques can be used in the decoding process to increase the understanding of the channel,and it is very likely that the computational complexity can be reduced under the premise of obtaining maximum likelihood decoding performance.The A~*algorithm is an intelligent algorithm and is also a maximum likelihood soft decision decoding method.It 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.In order to reduce the computational complexity while ensuring the decoding accuracy,the A~*decoding algorithm is improved.The improved A~*decoding algorithm can be divided into 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;2.take advantage of Hamming distance to reduce the search space.Simulations on the(2,5)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.