Study On Decoding Algorithms For Polar Codes Based On Optimization Theory

Polar codes are the first class of channel coding technique that have been proved to reach the Shannon limit.Due to the low complexity of coding and decoding,polar codes have become a research hotspot in the field of channel coding in recent years.At the 3GPP conference in 2016,polar codes were proposed to be the coding scheme for the control channel in the 5G enhanced mobile broadband(e MBB)scenario.In the future,the reliable and efficient decoding schemes are very important for the communication systems.Therefore,it is of great significance to study efficient decoding algorithm of polar codes.Generally,the decoding problem of polar codes can be regarded as an optimization problem.However,solving this problem from the viewpoint of optimization theory and methods has not attracted much attention.This paper aims to study the decoding algorithm of polar codes based on the optimization theory,establish the optimization model for the decoding problem,and solve the decoding problem by using optimization methods.The main contents are summarized as follows:1.The decoding of polar codes can be approximated as a Linear Programming(LP)problem,but the performance of LP decoding under the AWGN channel is poor.An adaptive linear programming(ALP)decoding algorithm for polar codes is provided by determining the parity check constraints of the LP decoding found by the cut search method.Simulation results show that the performance of polar codes under ALP decoding are better compared with LP decoding.2.The reduction method of the factor graph can reduce the number of variables and constraints for the optimization model,and then reduce the complexity of decoding.By making a detailed analysis of the algebraic structure features for the factor graph of polar codes,an improved reduction method of factor graphs is proposed.Simulation results show that the method can further reduce the constrains for the factor graph of polar codes.Meanwhile,ALP decoding algorithm of polar codes based on the factor graph reduction method is designed.Simulation results show that the proposed decoding algorithm can reduce the decoding time of polar codes compared with ALP decoding algorithm.3.For polar codes with long block lengths,the computational complexity of ALP decoding is high.The distributed characteristics of Alternating Direction Method of Multipliers(ADMM)makes it suitable for the fast decoding of polar codes with long block lengths.By investigating the principle of ADMM method,the ADMM penalized decoding algorithm for polar codes is proposed.In particular,the mathematical model of the ADMM decoding problem is established,and the update rules for the corresponding ADMM variables are derived.Simulation results show that the proposed ADMM penalized decoding algorithm can significantly reduce the decoding complexity with some error rate performance degradation compared with the ALP decoding.4.For the time-consuming projection operation involved in the ADMM decoding,an accelerated ADMM penalized decoding algorithm is proposed.Simulation results show that the proposed decoding methods can shorten the decoding time of the ADMM penalized decoding algorithm,while maintaining the same error rate performance.