A Highly Efficient Importance Sampling Method for LDPC Codes Using Trapping Sets

We introduce an Importance Sampling (IS) method that successfully simulates the performance of Low density Parity Check (LDPC) Codes in an AWGN channel at very low bit error rates (BERs). The proposed technique is independent of block size of a given LDPC code and attains significant simulation gains. By effectively finding and biasing bit node combinations that are the dominant sources of error events, called trapping sets, the developed technique provokes more frequent decoder failures. Consequently, fewer simulation runs and higher simulation gains are achieved. The proposed method consists of two steps. In the first step, a novel trapping search algorithm is used to identify all trapping sets and then, the trapping sets are classified based on the total number of bits involved in each trap. In the second step, IS is applied to only one trapping set from each class and the total BER is estimated by adding the BER contribution of each class. Regardless of the block size of an LDPC code, only a few dominant trapping set classes cause decoder failures at low BER regions. Therefore, the proposed technique allows the performance evaluation for any size LDPC code at very low BER regions with remarkable simulation gains in the order of 1014 at BER of 10-20.