IEEE International Symposium on Information Theory (ISIT)

Estimating LDPC codeword error rates via importance sampling

Bo Xia, W.E. Ryan

Published Dec 23, 2004• 11 citations

Abstract

This paper proposes an importance sampling design for the codeword error rate estimation of low-density parity-check codes. An error set partitioning method is introduced to reduce the error boundary complexity and to improve the simulation efficiency. This is a follow-up to the work in (B. Xia et al., 2003).

DOI: 10.1109/isit.2004.1365513

Related papers

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 CommunicationsJul 1, 200953 citations

Fast BER estimation of LDPC codes

Takakazu Sakai, Koji Shibata

In this paper, we propose an estimation method of a very low bit error rate (HER) of low-density parity-check (LDPC) codes. No analytical tool is available to evaluate performance of LDPC codes, and traditional Monte Carlo simulation methods can not estimate low HER of LDPC codes due to the limitation of time. Cole et al, show a fast frame error rate simulation method of LDPC codes by applying importance sampling (IS). At first, we extend Cole et aI.'s method to the HER estimation of LDPC codes. Since the simulation time of the HER evaluation version of the Cole et aI.'s method is proportional to the number of total dominant trapping sets used in the simulation, we should appropriately choose the dominant trapping sets to reduce the simulation time. To avoid the difficulty, we propose another simulation method, which selects a dominant trapping set as proportional to its upper bound. Additionally, we show some numerical examples to demonstrate the effectiveness of the proposed method. When we evaluate HER of 10−16, the simulation time of the proposed method is reduced to 1/6.6 of that of the HER evaluation version of the Cole et al.'s method under the condition of the same accuracy of the estimator.

Apr 15, 20105 citations

A study on quick simulation for estimation of low FER of LDPC codes

Takakazu Sakai, Koji Shibata

This study shows a new design method of a simulation probability density function (PDF) for a fast frame error rate (FER) evaluation of low-density parity-check (LDPC) codes. It is difficult to evaluate a very low FER of LDPC codes by Monte Carlo simulation methods since it has excellent performance under iterative decoding. Cole et al. proposed a three-step estimation method of the low FER of LDPC codes of moderate block length. By applying the importance sampling method, which is one of the fast simulation methods, the simulation time of the error performance of LDPC codes can be reduced. Another simulation PDF, which can treat more dominant trapping sets (TS) than Cole et al.'s method, is proposed. The selection of the dominant TS as proportional to its probability reduces the number of simulation runs without deteriorating the accuracy of the estimator. Unbiased estimator is given as well as that that of the Cole et al.'s method. Some numerical examples are shown to demonstrate the effectiveness of the proposed method. The simulation time for an LDPC code of length 504 is reduced to 1/10 when we evaluate FER of around 10-14.

IEEE Malaysia International Conference on Communications (MICC)Dec 1, 20093 citations

Importance sampling for LDPC codes based on optimal simulation probability density function

Takakazu Sakai, Koji Shibata

This paper shows a fast simulation method of low-density parity-check (LDPC) codes by using importance sampling (IS). In IS, the design of the simulation probability density function (PDF) plays a very important role to reduce the simulation time. We derive the optimal simulation PDF, which can reduce the variance of the estimator to zero. Since the optimal simulation PDF includes true error probability, it can not be utilized in the practical simulation. The simulation PDF which approximates the optimal simulation PDF is proposed. In addition, we show some numerical examples to show the effectiveness of the proposed simulation method.

International Symposium on Information Theory and its ApplicationsOct 1, 20101 citation

Error Floor Estimation of QC-LDPC Coded Modulation With Importance Sampling

Mingyang Zhu, Ming Jiang, Chunming Zhao

This letter presents a low-complexity error floors estimation method for bit-interleaved coded modulation with quasi-cyclic low-density parity-check (LDPC) codes. Using surrogate bit-channels (SBCs) as hypothetic equivalent channels, the importance sampling method based on the stable trapping sets is applied to evaluate the error floors. It is shown that the error floors of bit-interleaved coded modulation systems can be effectively estimated, and the presented method is appropriate for various types of modulators and interleavers.

IEEE Communications LettersSep 4, 20206 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, 20040 citations