Research On Linear Programming Deeoding Algorithms Of LDPC Codes

Low-Density Parity-Check (LDPC) code is a kind of error-correction code whose performance is very close to Shannon Limit. As an approximation of maximum-likelihood (ML) decoding, linear programming (LP) decoding has the ML certificate property, which makes it easier to analyse than traditional iterative decoding algorithms. Then it is significant to study LP decoding algorithms of LDPC codes.In this thesis, LP decoding algorithms of LDPCs are investigated. The contents mainly include processes of building up the initial LP decoding models and research on improved LP decoding algorithms. The major works and innovations are as follows:(1) Two models of original LP decoding are introduced. The relationship between LP decoding and fractional distance is explained and conditions for successful decoding are summarized. Simulations are carried out on two kinds of LDPC codes with the same rate and length. After the comparison of BP decoding with MS decoding, the conclusions are gave.(2) Three improved LP decoding algorithms such as Adaptive LP decoding (ALP), Multistage LP decoding (MLP) and the tighter relaxation LP decoding are studied in detail. Two presented methods of searching redundant parity check cuts for the tigher relaxation LP decoding are introduced. Simulations about the three improved decoding algorithms are carried out.(3) It is random to select nodes with fractional value from current solution to correct by initial MLP decoding method, which results to an unsatisfied decocing efficiency. A modified MLP decoding algorithm is proposed based on a criterion, which aims at generating valid set consisting of variable nodes with the maximum average uncertainty. All of the possible settings obtained by a specific method are added to the LP problem as new constraints respectively to get a group of LP problems. The modified MLP decoding performs better than the original MLP under the same simulation environment, and the average efficiency is improved consequently. (4) Adaptive methods are applied in the MLP decoding and an adaptive MLP (AMLP) decoding is presented. AMLP decoding can achieve the same performances with much lower complexities compared with MLP decoding. Therefore, a balance between the decoding complexities and performances is obtained by AMLP decoding.(5) The parity check equations are transformed from GF(2) to real number field and an integral programming equaled to the ML decoding is described. Then a LP decoding model for LP decoding is got by relaxing the integral problem based on separation algorithms. An algorithm for constructing valid cuts is presented for the new decoding model at the base of elementary transformation on the parity check matrix. Valid cuts at current fractional solution can be obtained directly by this algorithm and therefore the efficiency will be enhanced. This decoding model based on separation algorithm has a better performance than the original LP decoding model.