Research On Linear Programming Decoding Algorithms For Polar Codes

By a non-constructive method,Shannon proved the existence of error-correcting codes that can achieve the channel capacity limit.Thus,the construction of capacity-achieving codes has become the main research goal in the coding field.In 2009,Arikan proposed a channel coding scheme,called polar codes,which can be constructed explicitly.Polar codes become the first theoretically proved coding technology that can achieve the channel capacity limit.In 2016,polar codes were promoted as the standard coding schemes for 5G's control channel in enhance mobile broadband(e MBB)scenario at the 3rd Generation Partnership Project(3GPP)meeting.This decision further promoted the development of polar codes.In this thesis,the linear programming decoding algorithms of polar codes are investigated in detail.The main research of this thesis is summarized as follows:1.The channel polarization principle of polar codes is analyzed in detail and the channel polarization effect is studied by computer simulation.The construction method of polar codes over binary erasure channel(BEC)and Gaussian approximation method over additive Gaussian white noise(AWGN)channel are outlined.In addition,the successive cancellation(SC)decoding algorithm and the linear programming(LP)decoding algorithm are expounded for polar codes.2.Based on a thorough analysis of LP decoding for polar codes,an improved LP decoding algorithm for polar codes is designed with the help of factor graph transformation.Simulation results showed that the designed decoding algorithm has better decoding performance when compared with the SC and LP decoding algorithms over BEC.3.Because the parity-check matrix of cyclic redundancy check(CRC)codes has high density,it is not beneficial for iterative decoding.By making the parity-check matrix sparse,belief propagation(BP)and alternating direction method of multipliers(ADMM)decoding algorithms are used for decoding CRC codes.Simulation results show that CRC codes not only can detect errors efficiently,but also can correct a certain amount of errors.4.CRC-aided successive cancellation list(CA-SCL)algorithm can improve the decoding performance of polar codes.In general,CA-SCL algorithm is designed by using the error-detecting ability instead of error-correction ability of CRC codes.In this thesis,based on the error-correction ability of CRC codes,CRC-aided ADMM decoding algorithm of polar codes is proposed over BEC.Simulation results showed that the proposed algorithm can improve the decoding performance of polar codes when compared to the traditional LP decoding algorithm.