Research On LDPC Decoding Algorithm Based On Linear Programming

Low-density parity-check (LDPC) is a kind of capacity-achieving modern codingtechnology, and has become one of the most attractive fields in channel coding. Due tothe advantages of LDPC codes, such as low complexity of decoding and strongerror-detection capacity, it has received a lot of attention in recent years. LDPC codeshave been used in wireless communications, deep space communications, optical fibercommunications, media storage and other fields.This paper focuses on the decoding of LDPC codes, especially on linearprogramming and pseudo-codeword search algorithm. Some results are obtained andsummarized as follow:1. LDPC codes and its Tanner graphs are introduced. Two important constructionmethods are briefly illuminated. The belief propagation decoding algorithm for the BECchannel and the maximum likelihood decoding algorithm for the discrete memorylesssymmetric channel are analyzed in detail.2. The basic principle of decoding algorithm based on the linear programmingoptimization technique is thoroughly analyzed. A decoding algorithm of LDPC codesbased on LP relaxation is given. Simulation results over the AGWN channel show thatLP decoding algorithm has the similar performance with the BP decoding algorithm.3. Pseudocodeword is a very important factor that influences the performance ofLP decoding of LDPC codes. An efficient pseudocodeword search algorithm as well asits implement is given in this paper. Simulation results show that the algorithm performswell for the search of pseudocodewords.