Research On Alternating Direction Method Of Multipliers Based On Linear Programming Decoding

LDPC codes is one of the best channel coding schemes. It is a hot topic in current research and is widely used in various communication fields. Traditional BP algorithm has error floor, which limits the application of LDPC codes in environment with high bit error performance requirement. Because of its low error floor, easy performance analysis realization and maximum likelihood characteristic, LP decoder has become an emerging decoding algorithm. But the high decoding complexity blocks its further development.Hence, this thesis studies LP decoding algorithm and ADMM of LDPC codes, and proposes a ADMM algorithm based on the minimum polytope, which is proved to have lower complexity and higher decoding efficiency than traditional decoding algorithm. The main work of this thesis is as follows:1. Basic concepts and the related knowledge of LDPC codes and LP decoding are introduced. A structured construction method of QC-LDPC code and the principle of BP algorithm are given. Based on the ML decoding algorithm, a relaxation method, a polytope construction method, the characteristics and the complexity analysis of LP decoding are discussed. Through comparing the simulation of bit error performance, a conclusion that LP decoding and BP decoding are similar ML decoding algorithms is given.2. The principle and iterative framework of ADMM is discussed in detail. And analysis of the convergence, termination condition and other characteristics of the algorithm is given. Based on the Feldman LP decoding model, the solution of ADMM is completed. Three models suitable for ADMM framework and the analysis of their complexity are given. Simulation results show that ADMM decoder calling projection algorithm is 10 times faster than traditional LP decoder on decoding efficiency.3. An efficient ADMM decoding algorithm based on the minimum polytope is proposed. The complexity of the model is effectively reduced by using the degree decomposition technique based on check nodes. With reasonable constructed matrix, the designed decoder can realize parallel decoding and can work without calling projection algorithm, which reduce the complexity of the decoder further. Simulation results show that, compared with current algorithm, the algorithm we proposed has significant improvement of the decoding efficiency without reduction of bit error performance.