Characteristic Analysis Of Trapping Set And Application In LDPC Codes

Low-density parity-check(LDPC) codes are linear block codes with low-density parity-check matrices. In contemporary communication systems, LDPC codes have been supposed to be the most promising error correction codes so far which are able to approach to the Shannon limit under all. Error floor phenomenon of LDPC codes with medium length, nevertheless, limits its further application in communication systems with very low BER, such as disk storage and deep space communication, which has gradually gained researchers’ widely attention. The error floor is primarily caused by a node topology graph named trapping set in Tanner graphs. This dissertation investigates trapping sets’ impacts on error floor, focuses on the special structure and proposes algorithms to mitigate error floor from the perspectives of optimizing graph structures as well as improving decoding algorithms, which are outlined in the points below:1. On the basis of understanding of trapping set’s conception and theories, their effects upon decoding performance are analyzed in detail combining the structure characters and the relationships among different kinds of trapping sets are explored.2. Searching methods of trapping sets are deeply investigated in this dissertation. Both conventional iterative simulation method and novel importance sampling method are discussed and verified. Besides, structure relationships between trapping sets and cycles are analyzed and further preceded by attempts about graph-based trapping sets searching methods. A new method for searching short cycles based in the column of parity check matrices is proposed and applied to search the potential trapping sets in parity check matrices combining trapping sets’ specific structure. This three algorithm are proved to be practical and effective in simulation experiments.3. On the basis of trapping sets’ adverse effects on decoding performance of LDPC codes, algorithms are proposed to mitigate error floor. From the perspective of optimizing graph structure, an eliminating algorithm faced to small trapping sets is proposed. It applies the idea of PEG algorithm for reference and uses node substitution methods to change the adjacent conditions of target node, thus damaging the topological structure of pre-eliminate trapping sets. From the perspective of improving decoding algorithm, based on the comprehensive understanding of belief propagation decoding mechanism, a message-erasure decoding algorithm based on specific nodes in trapping sets is also proposed. This algorithm improves the self-correction ability by choosing proper variable nodes which meet certain requirements in trapping sets and resetting their intrinsic messages. It is illustrated in simulation results that these two algorithms both can mitigate error floor effectively.