Research And Application On Linear-Programming Decoding Of LPDC Codes Based On Interior-Point Algorithm

Low Density Parity Check (LDPC) code is a kind of channel coding scheme with strong error correction ability, whose performance is very close to Shannon Limit. By relaxing the maximum likelihood (ML) decoding of LDPC codes to a linear programming (LP) problem, LP decoding of LDPC codes can obtain codewords with ML certificate features. For LP decoder of LDPC codes, the number of constraints in LP problem increases exponentially with the degree of the check node. Then it is significant to study how to solve the large-scale LP problem.In this thesis, the algorithms and applications of LP decoding for LDPC codes based on interior-point method are investigated. The contents include modeling of LP decoding, solving methods of LP optimization problem and applications of LP decoding. The major works and innovations are as follows:(1) Basic principles of LDPC codes and convex optimization theory are introduced. Then the process of relaxing the ML decoding problem to a LP optimization problem and construction of LP decoding model are researched in detail from three aspects:LP problem based on codeword polytope, LP problem based on relaxed polytope and LP problem based on projective polytope. The concept of fractional distance and max-fractional distance are studied in order to analysis the performance of the LP decoding. Analysis methods of LP decoding performance according to fractional distance and max-fractional distance are also involved.(2) LP decoding of LDPC codes based on primal-dual interior point (PDIP) algorithm is studied and the computation equations are derived. Karush-Kuhn-Tucker (KKT) optimization condition of LP problem, penalty factor, search direction and step size restriction are included. The decoding algorithm flow is presented at the same time.(3) In order to overcome the disadvantages of PDIP algorithm, predictor-corrector primal-dual interior-point (PCPDIP) algorithm is put forward to LP decoding of LDPC codes. The computation equations are derived in detail. In PCPDIP algorithm, the predictor and corrector steps are obtained by solving the KKT optimization conditions twice. The optimal solution can be found with keeping the searching trace away from the boundary of the feasible region at each iteration. Furthermore, a modification of the penalty factor is developed for the PCPDIP algorithm to accelerate the convergence speed of the algorithm. Simulation results of LDPC decoding demonstrate that the proposed PCPDIP algorithm achieves good bit error rate (BER) performance and good global convergence property with less iteration number and time than PDIP algorithm.(4) A hyperspectral remote sensing image transmission system with LDPC codes as the channel coding is constructed. Error correction performance of LP decoding based on PCPDIP algorithm is studied. In the image transmission system, the lossless compressed image is sent through BIAWGN channel and Rayleigh fading channel after LDPC coding and modulation. After demodulation, decoding and decompression, the image is recovered from the received signal. The system performance is examined through PSNR tables, BER curves and the recovered images. Simulation results show that LDPC codes have very good error correction capability in AWGN channel and Rayleigh channel. In addition, LP decoding based on PCPDIP algorithm can obtain high PSNR and low BER performance in low SNR situation.