Research On The Improved Belief Propagation Decoding Algorithm Of Polar Codes

Polar codes introduced by Arikan in 2009 are the first code family that has been proven to achieve the symmetric capacity of any given binary-input discrete memoryless channels. Due to the good capacity-achieving performance and the structural property,it is very important to research polar codes,which will be widely used in the future digital communication.As a fully parallel decoding algorithm,belief propagation(BP) decoding has a high throughput,however,there are some problems in the existing BP decoding.Because of frozen bits existing in decoding factor graph, these information is not fully utilized in the process of the present BP decoding. Besides the maximum number of iterations in the BP decoding algorithm is 60 times, which makes the decoding suffer from latency and energy dissipation. Therefore, to solve the two problems,this paper proposes a simplified BP decoding algorithm and a fast BP decoding algorithm.On the one hand,we propose a simplified BP decoding algorithm for the factor graph of polar codes.First, the characteristic of polar codes factor graph is analyzed. According to the situation of existing frozen nodes, the decoding processing unit is divided into four different types.Then the simplified iteration formulas is given for the three kinds of processing units with frozen nodes.The simplified iteration formula without logarithm,exponent,multiplication or division operations, only involves addition operations. By using the simplified BP decoding,the logarithm,exponent,multiplication and division operator numbers can be reduced by 28.7%~31.4%. Furthermore, the simulation results show that the simplified BP decoding algorithm does reduce the computational complexity without loss of bit error performance.On the other hand, a fast BP decoding algorithm based on the early stopping iteration is proposed for the large number of iterations in the BP decoding algorithm. First, five different types of data frames are studied through a lot of simulations. The fast convergence of the correct frame only needs less iteration numbers to corrcet all information bits and the reliability can reach a stable value. With the increase of the signal to noise ratio, the ratio of the correct frame rate is increasing.Then, a method isgiven to determine whether the decoding iteration is terminated according to the reliability of the information. Based on the early stopping iteration, the fast BP decoding algorithm is proposed, and the implementation steps of the fast decoding algorithm are listed in detail. Compared with the original BP decoding algorithm, the fast BP decoding algorithm based on the early stopping iteration can significantly reduce the number of decoding iterations.The effect is more obvious in high SNR, and the number of iterations can be reduced by 83.33% when the SNR is 3d B. The simulation results show that the fast BP decoding algorithm can greatly decrease the number of iterations and speed up the decoding, and solve the problem of decoding delay.