International Conference on Communications

On importance sampling for linear block codes

Bo Xia, W.E. Ryan

Published Mar 1, 2004• 35 citations

Abstract

We introduce an importance sampling scheme for linear block codes with message-passing decoding. This novel scheme overcomes an existing difficulty in the IS practice that requires codebook information. Experiments show large IS gains for single parity-check codes and short-length block codes. For medium-length block codes, IS gains in the order of 10/sup 3/ and higher are observed at high signal-to-noise ratio.

DOI: 10.1109/icc.2003.1204566

Related papers

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 SystemsAug 16, 20054 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, 20211 citation

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, 20040 citations

An IS Simulation Technique for Very Low BER Performance Evaluation of LDPC Codes

Enver Çavuş, Charles L. 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. 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. For BERs of 10-20, we observed simulation gains on the order of 1014.

International Conference on CommunicationsJun 1, 200623 citations

Fast performance estimation of block codes

Rajan Srinivasan, Nuo Wang

Importance sampling is used in this paper to address the classical yet important problem of performance estimation of block codes. Simulation distributions that comprise discrete- and continuous-mixture probability densities are motivated and used for this application. These mixtures are employed in concert with the so-called g-method, which is a conditional importance sampling technique that more effectively exploits knowledge of underlying input distributions. For performance estimation, the emphasis is on bit by bit maximum a-posteriori probability decoding, but message passing algorithms for certain codes have also been investigated. Considered here are single parity check codes, multidimensional product codes, and briefly, low-density parity-check codes. Several error rate results are presented for these various codes, together with performances of the simulation techniques.

IEEE Transactions on CommunicationsMar 1, 20082 citations

Effective Error Floor Estimation Based on Importance Sampling with the Uniform Distribution

A. Yu. Uglovskii, I. A Mel'nikov, I. A Alekseev +1 more

A key problem of low-density parity-check (LDPC) codes analysis is estimation of an extremely low error floor that occurs at a high level of the signal-to-noise ratio (SNR). The importance sampling (IS) method is a popular approach to address this problem. Existing works typically use a normal sampling probability density function (PDF) with shifted mean, which yields a large variance of the estimate. In contrast, uniform distribution has equally probable samples on the entire range and thus should reduce the variance, but results in a biased estimation. This paper proposes a modified IS approach (IS-U) that allows considering the uniform distribution as a sampling PDF, and shows that this estimation is better than the traditional one. Also, this paper demonstrates that the existing criteria cannot be applied to evaluate the accuracy of the IS-U on the whole SNR range. To address this issue, a new metric is proposed, which uses only the convergence rate and does not depend on the true data.

Проблемы передачи информацииDec 15, 20232 citations