A Study On Belief Propagation Decoding Algorithms Of Two Graph Codes

Low-density parity-check(LDPC) codes and Polar codes are called Graph codes because their decoding processes are both based on the factor graphs. In recently years, more and more researchers concern about them due to their excellent performance.In this thesis, we combine theory analysis and simulation to study the belief-propagation(BP) decoding algorithms of LDPC codes and Polar codes. The main work are summarized as follows:First, introducing two graph codes—the basic knowledge about LDPC codes and Polar codes, include how to construct, encode and decode on LDPC codes; then, mainly introducing the belief-propagation algorithm and its improvement algorithms. Finally, presenting the encoding and successive cancellation decoding method of Polar codes.Through the research on BP decoding algorithm, the same as sum-product algorithm, in order to reduce decoding complexity, further to reduce the number of decoding iteration, a modified sum-product algorithm(MSPA) is proposed for the LDPC codes, the decoding process of MSPA compares the differences between before and after the bit information update in the iterative process, then determines when to stop the decoding process until the set value satisfies the condition. Its decoding process includes two steps: First, it needs to determine the accuracy of the difference between before and after the bit information update. Then, repeats the decoding process until satisfies the set accuracy. The simulation results show that the proposed algorithm reduces the decoding iterations under little performance degradation. But MSPA doesn’t work on high SNR, so next we will do some research to solve this problem.In addition, a modified belief-propagation(MBP) algorithm is proposed based on the belief-propagation decoding algorithm for Polar codes. The proposed algorithm makes use of the offsets between left information and right information of frozen bits to determine the threshold of an early termination in the iterative decoding process. The simulation results show that the proposed algorithm significantly reduces the decoding iterations under little performance degradation. How to find the optimal threshold by density evolution or Monte Carlo method are our next work.