Analysis And Optimization For LDPC Codes Based On The Error-prone Substructures

Low density parity check (LDPC) codes are a class of error correction codeswhich could approach the Shannon Limit. Due to its superior error correctionperformance and low complexity decoding algorithms, LDPC codes have attracted agreat amount of interest and have been applied in many fields and standards. However,with the increase of the Signal-to-Noise Ratio (SNR), LDPC codes often exhibit anerror floor phenomenon, which limits the further application of LDPC codes. In orderto investigate the error floor phenomenon of LDPC codes better, this paper focuses onthe frame error rate (FER) estimation method for LDPC codes in the high SNRregion.This thesis analyzes several error-prone substructures which lead to the errorfloor of LDPC codes and focuses on an efficient exhaustive search algorithm based onthe branch and bound principle for finding the small fully absorbing sets of LDPCcodes. The characteristic of this algorithm is formulating a integer programmingproblem to decide the minimum size of fully absorbing sets under given constraintsand solving this problem using the brand and cut algorithm which improves theefficiency of the algorithm. This algorithm is independent of the channel type and thedecoding algorithms, and thus is applicable to any LDPC code. During the research, aprogram for this algorithm is developed which provides an analysis tool for ultra lowerror frame rate.Based on the small fully absorbing sets, an importance sampling (IS) method forestimating the FER of LDPC codes is presented in this thesis. In the proposed method,the dominant trapping sets or absorbing sets are replaced by exhaustive fullyabsorbing sets, and then the mean translation importance sampling method is appliedto small fully absorbing sets to estimate the FER. Simulation results show that,compared to Monte Carlo simulation, the proposed method can reduce the simulationtime efficiently without sacrificing the simulation accuracy.