Research On The Improved Belief Propagation Decoding Algorithm Of Polar Codes

Polar codes proposed by E.Arikan can achieve the symmetric capacity I(W) of any given binary-input discrete memoryless channel (B-DMC) W with low encoding and decoding complexities. It has draw a lot of attention by its breakthrough in wireless communication systems.BP is a fully parallel decoding algorithm with high throughput. For polar codes, the itera-tive process of BP can not been terminated in advance as the polar codes doesn't parity check matrix. Both the polar codes and the low density parity check codes are all graph codes, so their BP decoding is very similar. The BP algorithm in LDPC decoding has the following characteristics:First, many variable nodes achieve high confidence after very few iterations in the process of BP decoding of LDPC codes. For these nodes, it is impossble to change their signs or polarities with extra iterations. Second, as the BP decoding tends to converge, the differences between the message before and after an update become zero. According to the difference between message before and after an update on information node, the author proposed three improved BP decoding strategies based on the early termination iteration.There are three parameters denoting the change of varible, namely, mean, variance and mean square deviation. According to these three parameters, the author propose three improved BP decoding algorithms based on mean, variance and mean square deviation respectively. These improved BP decoding algorithms can terminate the process of decoding early. The bits in the polar codes are classified into frozen bits and information bits, where the frozen bits are known and the information bits are random. In the process of BP decoding, the author need to calculate the variance and mean square deviation of likelihood ratio of the information bits in three successive iterations in order to determine whether the information bits converge or not. Simulation results show that the two improved decoding algorithms can reduce the number of iterations without performance loss basically. The improved algorithm based on mean square deviation has to calculate the square root, therefore, it is slightly worse than the algorithm based on variance. In the third improved algorithm,we can determine whether the information bit converges or not according to the mean value of the change of the two adjacent likelihood ratio of information bit in three successive iterations. Simulation results show that the third improved algorithm reduces the number of iterations greatly without performance loss basically. From the perspective of complexity, the third improved algorithm based on the average of likelihood ratio is relatively simple in all three improved algorithms.