Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Importance Sampling for Tanner Trees

B. Xia, W.E. Ryan

Published Jun 1, 2005• 11 citations
Publisher

Abstract

This correspondence presents an importance sampling (IS) simulation scheme for the soft iterative decoding on loop-free multiple-layer trees. It is shown that this scheme is asymptotically efficient in that, for an arbitrary tree and a given estimation precision, the required number of samples is inversely proportional to the noise standard deviation. This work has its application in the simulation of low-density parity-check (LDPC) codes.

DOI
10.1109/tit.2005.847748

Related papers

Importance sampling for loop-free decoding trees with application to low-density parity-check codes

B. Xia, W.E. Ryan

An importance sampling scheme for the decoding of loop-free decoding trees is proposed. It is shown that this scheme is asymptotically efficient and that, for an arbitrary tree and a given estimation precision, the number of simulation runs needed is inversely proportional to the standard deviation of the channel noise. This work has its application to the decoding of low-density parity-check codes.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•2 citations

Importance sampling for LDPC codes and turbo-coded CDMA

Bo Xia

Low-density parity-check (LDPC) codes have shown capacity-approaching performance with soft iterative decoding algorithms. Simulating LDPC codes at very low error rates normally takes an unacceptably long time. We consider importance sampling (IS) schemes for the error rate estimation of LDPC codes, with the goal of dramatically reducing the necessary simulation time. In IS simulations, the sample distribution is biased to emphasize the occurrence of error events and efficiency can be achieved with properly biased sample distributions. For LDPC codes, we propose an IS scheme that overcomes a difficulty in traditional IS designs that require codebook information. This scheme is capable of estimating both codeword and bit error rates. As an example, IS gains on the order of 105 are observed at a bit error rate (BER) of 10-15 for a (96, 48) code. We also present an importance sampling scheme for the decoding of loop-free multiple-layer trees. This scheme is asymptotically efficient in that, for an arbitrary tree and a given estimation precision, the required number of simulations is inversely proportional to the noise standard deviation. The motivation of this study is to shed light on an asymptotically efficient IS design for LDPC code simulations. For an example depth-3 regular tree, we show that only 2400 simulation runs are needed to achieve a 10% estimation precision at a BER of 10-75. Similar promising results are also shown for a length-9 rate-1/3 regular code after being converted to a decoding tree. Finally, we consider a convolutionally coded CDMA system with iterative multiuser detection and decoding. In contrast to previous work in this area, a differential encoder is inserted to effect an interleaver gain. We view the CDMA channel as a periodically time-varying ISI channel. The receiver jointly decodes the differential encoders and the CDMA channel with a combined trellis, and shares soft output information with the convolutional decoders in an iterative (turbo) fashion. Dramatic gains over conventional convolutionally coded systems are demonstrated via simulation. We also show that there exists an optimal code rate under a bandwidth constraint. The performance and optimal code rates are also demonstrated via density evolution analysis.

•Jan 1, 2004•0 citations

On importance sampling for iteratively decoded linear block codes

Nuo Wang, Rajan Srinivasan

We introduce an importance sampling (IS) scheme for fast performance evaluation of the linear block codes with message-passing decoding. This novel scheme overcomes the existing difficulties in IS to some extent when code length is large and requires codebook information. Experiments show very high IS gains for iteratively decoded linear block codes such as single parity-check (SPC) codes and block product codes, as well as low density parity-check (LDPC) codes. We also provide a scheme based on our IS method to find the minimum Hamming distance and pick up those codewords which are very useful when calculating asymptotic performance.

International Conference on Communications, Circuits and Systems•Aug 16, 2005•4 citations

Minimum-Variance Importance Sampling Estimator for Fast Simulation of Linear Block Codes over Binary Erasure Channels

Jinzhe Pan, Wai Ho Mow

In this paper, the problem of efficiently evaluating the error performance of linear block codes over binary erasure channels (BECs) is considered. We propose a novel importance sampling (IS) estimator by deriving the optimal IS distribution of the erasure pattern size. Consequently, a corresponding iterative algorithm for fast simulation purpose is proposed. The effectiveness of the proposed IS algorithm compared to Monte Carlo simulation is demonstrated in estimating the block erasure rate of low-density parity-check codes, and IS gains of almost ten orders of magnitude is achieved.

World Conference on Computing and Communication Technologies (WCCCT)•Jan 1, 2021•1 citation

Low BER performance estimation of LDPC codes via application of importance sampling to trapping sets

E. Cavus, Chuck Haymes, Babak Daneshrad

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). 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.

IEEE Transactions on Communications•Jul 1, 2009•53 citations

Evaluation of the Low Error-Rate Performance of LDPC Codes over Rayleigh Fading Channels Using Importance Sampling

Seok-Ki Ahn, Kyeongcheol Yang, Dongsoo Har

In this paper we propose a novel importance sampling (IS) scheme to estimate the low error-rate performance of low-density parity-check (LDPC) codes over Rayleigh fading channels. The proposed scheme exploits the structural weakness of LDPC codes due to trapping sets (TSs). The Rayleigh fading distribution on the bits belonging to a TS is biased by parameter scaling (PS), while the noise distribution on them is biased via mean translation (MT) according to their fading coefficients. The biases in PS and MT are determined so that the variance of the proposed IS estimator is minimized. The proposed IS scheme is compared with the Monte Carlo (MC) simulator and other IS schemes modified from the conventional IS scheme employed for performance estimation of LDPC codes over an AWGN channel. Numerical results show that it provides much more accurate performance than other IS schemes. Furthermore, the proposed IS estimator is even more efficient than the MC estimator and other IS estimators from the viewpoint of the number of required simulation runs.

IEEE Transactions on Communications•Jun 1, 2013•14 citations
This correspondence presents an importance sampling (IS) simulation scheme for the soft iterative decoding on loop-free multiple-layer trees. It is shown that this scheme is asymptotically efficient in that, for an arbitrary tree and a given estimation precision, the required number of samples is inversely proportional to the noise standard deviation. This work has its application in the simulation of low-density parity-check (LDPC) codes.
Low-density parity-check (LDPC) codes have shown capacity-approaching performance with soft iterative decoding algorithms. Simulating LDPC codes at very low error rates normally takes an unacceptably long time. We consider importance sampling (IS) schemes for the error rate estimation of LDPC codes, with the goal of dramatically reducing the necessary simulation time. In IS simulations, the sample distribution is biased to emphasize the occurrence of error events and efficiency can be achieved with properly biased sample distributions. For LDPC codes, we propose an IS scheme that overcomes a difficulty in traditional IS designs that require codebook information. This scheme is capable of estimating both codeword and bit error rates. As an example, IS gains on the order of 105 are observed at a bit error rate (BER) of 10-15 for a (96, 48) code. We also present an importance sampling scheme for the decoding of loop-free multiple-layer trees. This scheme is asymptotically efficient in that, for an arbitrary tree and a given estimation precision, the required number of simulations is inversely proportional to the noise standard deviation. The motivation of this study is to shed light on an asymptotically efficient IS design for LDPC code simulations. For an example depth-3 regular tree, we show that only 2400 simulation runs are needed to achieve a 10% estimation precision at a BER of 10-75. Similar promising results are also shown for a length-9 rate-1/3 regular code after being converted to a decoding tree. Finally, we consider a convolutionally coded CDMA system with iterative multiuser detection and decoding. In contrast to previous work in this area, a differential encoder is inserted to effect an interleaver gain. We view the CDMA channel as a periodically time-varying ISI channel. The receiver jointly decodes the differential encoders and the CDMA channel with a combined trellis, and shares soft output information with the convolutional decoders in an iterative (turbo) fashion. Dramatic gains over conventional convolutionally coded systems are demonstrated via simulation. We also show that there exists an optimal code rate under a bandwidth constraint. The performance and optimal code rates are also demonstrated via density evolution analysis.
We introduce an importance sampling (IS) scheme for fast performance evaluation of the linear block codes with message-passing decoding. This novel scheme overcomes the existing difficulties in IS to some extent when code length is large and requires codebook information. Experiments show very high IS gains for iteratively decoded linear block codes such as single parity-check (SPC) codes and block product codes, as well as low density parity-check (LDPC) codes. We also provide a scheme based on our IS method to find the minimum Hamming distance and pick up those codewords which are very useful when calculating asymptotic performance.
In this paper, the problem of efficiently evaluating the error performance of linear block codes over binary erasure channels (BECs) is considered. We propose a novel importance sampling (IS) estimator by deriving the optimal IS distribution of the erasure pattern size. Consequently, a corresponding iterative algorithm for fast simulation purpose is proposed. The effectiveness of the proposed IS algorithm compared to Monte Carlo simulation is demonstrated in estimating the block erasure rate of low-density parity-check codes, and IS gains of almost ten orders of magnitude is achieved.
In this paper we propose a novel importance sampling (IS) scheme to estimate the low error-rate performance of low-density parity-check (LDPC) codes over Rayleigh fading channels. The proposed scheme exploits the structural weakness of LDPC codes due to trapping sets (TSs). The Rayleigh fading distribution on the bits belonging to a TS is biased by parameter scaling (PS), while the noise distribution on them is biased via mean translation (MT) according to their fading coefficients. The biases in PS and MT are determined so that the variance of the proposed IS estimator is minimized. The proposed IS scheme is compared with the Monte Carlo (MC) simulator and other IS schemes modified from the conventional IS scheme employed for performance estimation of LDPC codes over an AWGN channel. Numerical results show that it provides much more accurate performance than other IS schemes. Furthermore, the proposed IS estimator is even more efficient than the MC estimator and other IS estimators from the viewpoint of the number of required simulation runs.