Research On Mixed Integer Programs Of ADMM Decoding For LDPC Codes

Low-Density Parity-Check(LDPC)codes are a class of good codes with coding efficiency close to Shannon's limit.It was proposed by Gallager in 1962.LDPC codes using the sparseness of the check matrix can perform effective decoding even when the code length is long.The decoding complexity of LDPC codes only increases linearly with the code length.Therefore,LDPC codes are widely used in wireless communication,digital storage and deep space communication systems,which can effectively improve the reliability of the system.The maximum likelihood decoding of LDPC codes can be reduced to the integer programming problem,which is a NP complete problem.By relaxing the optimization problem of maximum likelihood decoding into linear programming,researchers have proposed a linear programming decoding algorithm for LDPC codes.Compared with the traditional simplex method,using the Alternating Direction Method of Multipliers(ADMM)to solve the linear programming decoding problem of LDPC codes is more efficient.However,the iterative steps of the existing ADMM decoding algorithms are derived based on the linear programming decoding problem.In this thesis,the ADMM solution framework is used to directly derive the specific iterative steps of the integer programming decoding problem of LDPC codes.And an ADMM decoding algorithm for LDPC codes based on mixed integer programming(ADMM-MIP)is proposed.The ADMM-MIP decoding algorithm is studied in detail from two different perspectives:improving decoding error correction performance and accelerating decoding speed.The main work is as follows:1.Aiming at the maximum likelihood decoding of LDPC codes,an ADMM decoding algorithm based on mixed integer programming is proposed.Aiming at the problem of complicated Euclidean projection operation in ADMM-MIP decoding,this thesis uses an approximate line segment projection algorithm to replace the original Euclidean projection,which can effectively accelerate the decoding speed.The simulation results for different LDPC codes show that the performance of ADMM-MIP decoding is comparable to that of classic ADMM penalty decoders,but the complexity of ADMM penalty decoders in selecting parameters can be avoided.2.An ADMM-MIP decoding algorithm based on flooding scheduling for LDPC codes is analyzed,and an ADMM-MIP decoding algorithm based on horizontal scheduling is proposed from a layered perspective.Compared with the original flooding scheduling algorithm,this algorithm accelerates the convergence speed of the decoding algorithm,and can significantly improve the performance of the decoding algorithm in the case of fewer iterations.3.Aiming at the possible error floor problem of the ADMM-MIP decoding algorithm,a post processing method was proposed to improve the decoding performance of LDPC codes.The core idea of the method is that after the original ADMM-MIP decoding algorithm fails to decode,the check matrix and hard decision are used to calculate the number of nodes with unsatisfactory check constraints,change its corresponding log-likelihood ratio vector,and then perform ADMM-MIP decoding again.Simulation results show that the proposed post-processing method can significantly improve the performance of the ADMM-MIP decoding algorithm.