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.

By: Enver Cavus; Charles Haymes

Published in: RC23472 in 2004


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .