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 Information Theory Workshop (ITW)

A New Importance Sampling Algorithm for Fast Simulation of Linear Block Codes over BSCs

Jinzhe Pan, Wai Ho Mow

Published Aug 1, 2019• 4 citations
Publisher

Abstract

In this paper, we propose an Importance Sampling (IS) scheme for fast simulation of linear block codes over binary symmetric channels (BSCs). By re-formulating the IS problem into the one-dimensional Hamming weight space, we propose a novel IS estimator and derive the optimal IS distribution which will minimize the variance of the estimator. Consequently, a corresponding iterative algorithm is proposed. The effectiveness of the proposed IS algorithm compared to the state-of-the-art IS algorithm is demonstrated in the word error rate simulation of both LDPC and Polar codes.

DOI
10.1109/itw44776.2019.8989120

Related papers

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

Sub-optimal importance sampling for fast simulation of linear block codes over BSC channels

Gianmarco Romano, Antonio Drago, Domenico Ciuonzo

Estimation of very low word-error probability of hard-decoded linear block codes can be performed through Monte-Carlo simulation. The computational complexity of the standard method however increases as the probability of error to be estimated decreases. In this paper we propose a general algorithm for fast estimation of probability of error of linear block codes on BSC channels based on the importance sampling and the cross-entropy method for rare-events that can be employed for any hard-decision decoder. When optimal decoding is used the algorithm reduces to a single simulation run that can estimate, with a given accuracy, performances for a whole range of sufficiently high signal-to-noise ratios.

International Symposium on Wireless Communication Systems•Nov 1, 2011•6 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

New performance evaluation methods for block codes over memoryless channels with efficiency analysis

Jinzhe Pan

With the development of communication technology, modern communication networks need to achieve ultra-high reliability to meet practical demands. Forward error correction coding has been widely used in real-world communication systems for providing reliable data transmission over noisy channels. In this thesis, we investigate the efficient performance evaluation methods for block codes over memoryless channels. Performance bounds are powerful tools to provide insights on the error performance of the coded systems. In many practical scenarios where performance bounds are not applicable (e.g., due to the unavailability of the relevant coding parameters under a given decoder), the Monte Carlo simulation is still popular despite its inefficiency, especially in the low error probability regime. As a variance-reduction technique, importance sampling (IS) can significantly reduce the sample size needed for reliable estimation. We firstly examine the problem of efficient performance evaluation of linear block codes over binary symmetric channels (BSCs). Contrary to the conventional wisdom, we prove that for BSCs, all bounds based on Gallager’s first bounding technique, including the famous union bound, are not asymptotically tight for all possible choices of the Gallager region. By proposing the so-called input demodulated-output weight enumerating function (IDWEF) of a code, asymptotically tight maximum-likelihood decoding upper and lower bounds for BSCs are derived. For the cases that coding parameters are absent or suboptimal decoders are applied, we propose an efficient IS estimator by deriving the optimal IS distribution of the Hamming weight of the error vector. In addition, the asymptotic percentage saving of the proposed IS estimator over the state-of-the-art IS estimator is characterized in terms of the sample size. Its accuracy in predicting the efficiency of the proposed IS estimator is verified by extensive computer simulation. We further examine the IS estimator design and efficiency analysis problems for the additive white generalized Gaussian noise (AWGGN) channel. The generalized Gaussian distribution is an effective model to describe real-world systems with impulsive noise. It can be specialized to the Laplace and Gaussian distributions depending on the choices of the decay rates of the heavy tail. By deriving the optimal IS distribution on the one-dimensional space mapped from the observation space, we present a general framework for designing IS estimators for linear block codes over a memoryless continuous channel. We apply the framework to the AWGGN channel and propose a noise-magnitude-domain IS (NM-IS) estimator. As an efficiency measure, the asymptotic IS gain of the proposed estimator is derived in a multiple integral as the signal-to-noise ratio (SNR) tends to infinity. Specifically, we reduce the gains of both Laplace and Gaussian noise cases to a one-dimensional integral. In addition, by limiting the use of the union bound to an L1-norm sphere with an optimized radius, we derive the sphere bound for the additive white Laplace noise channel. Simulation results show the efficiency of the proposed IS estimator in terms of the sample size and verify the accuracy of the prediction of the derived IS gain. Besides, we specialize the proposed framework to further improve the efficiency of the IS simulation based on the side information of the modulation. For the AWGGN channel with binary phase-shift keying (BPSK) modulation, we propose an enhanced NM-IS estimator, which outperforms the NM-IS estimator in efficiency. For the additive white Gaussian noise channel with M-PSK modulation, we propose an angular domain IS estimator and provide its efficiency analysis in terms of the asymptotic IS gain. Furthermore, in the performance evaluation of communication systems, it is often seen that researchers are more interested in the required SNR at a target error probability Pe than the other way around. The conventional solution to this Pe-targeted SNR estimation problem involves interpolation of simulated error probabilities at multiple handpicked SNRs for estimating the required SNR at the target error probability. We propose a Pe-targeted iterative IS estimator that solves the problem algorithmically. The proposed method can achieve the same efficiency (in terms of sample size) as estimating the error probability at the required SNR and allow the confidence interval of the SNR estimate to be obtained.

•Jan 1, 2022•0 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 Applications•Oct 1, 2010•1 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, 2004•0 citations
In this paper, we propose an Importance Sampling (IS) scheme for fast simulation of linear block codes over binary symmetric channels (BSCs). By re-formulating the IS problem into the one-dimensional Hamming weight space, we propose a novel IS estimator and derive the optimal IS distribution which will minimize the variance of the estimator. Consequently, a corresponding iterative algorithm is proposed. The effectiveness of the proposed IS algorithm compared to the state-of-the-art IS algorithm is demonstrated in the word error rate simulation of both LDPC and Polar codes.
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.
Estimation of very low word-error probability of hard-decoded linear block codes can be performed through Monte-Carlo simulation. The computational complexity of the standard method however increases as the probability of error to be estimated decreases. In this paper we propose a general algorithm for fast estimation of probability of error of linear block codes on BSC channels based on the importance sampling and the cross-entropy method for rare-events that can be employed for any hard-decision decoder. When optimal decoding is used the algorithm reduces to a single simulation run that can estimate, with a given accuracy, performances for a whole range of sufficiently high signal-to-noise ratios.
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.
With the development of communication technology, modern communication networks need to achieve ultra-high reliability to meet practical demands. Forward error correction coding has been widely used in real-world communication systems for providing reliable data transmission over noisy channels. In this thesis, we investigate the efficient performance evaluation methods for block codes over memoryless channels. Performance bounds are powerful tools to provide insights on the error performance of the coded systems. In many practical scenarios where performance bounds are not applicable (e.g., due to the unavailability of the relevant coding parameters under a given decoder), the Monte Carlo simulation is still popular despite its inefficiency, especially in the low error probability regime. As a variance-reduction technique, importance sampling (IS) can significantly reduce the sample size needed for reliable estimation. We firstly examine the problem of efficient performance evaluation of linear block codes over binary symmetric channels (BSCs). Contrary to the conventional wisdom, we prove that for BSCs, all bounds based on Gallager’s first bounding technique, including the famous union bound, are not asymptotically tight for all possible choices of the Gallager region. By proposing the so-called input demodulated-output weight enumerating function (IDWEF) of a code, asymptotically tight maximum-likelihood decoding upper and lower bounds for BSCs are derived. For the cases that coding parameters are absent or suboptimal decoders are applied, we propose an efficient IS estimator by deriving the optimal IS distribution of the Hamming weight of the error vector. In addition, the asymptotic percentage saving of the proposed IS estimator over the state-of-the-art IS estimator is characterized in terms of the sample size. Its accuracy in predicting the efficiency of the proposed IS estimator is verified by extensive computer simulation. We further examine the IS estimator design and efficiency analysis problems for the additive white generalized Gaussian noise (AWGGN) channel. The generalized Gaussian distribution is an effective model to describe real-world systems with impulsive noise. It can be specialized to the Laplace and Gaussian distributions depending on the choices of the decay rates of the heavy tail. By deriving the optimal IS distribution on the one-dimensional space mapped from the observation space, we present a general framework for designing IS estimators for linear block codes over a memoryless continuous channel. We apply the framework to the AWGGN channel and propose a noise-magnitude-domain IS (NM-IS) estimator. As an efficiency measure, the asymptotic IS gain of the proposed estimator is derived in a multiple integral as the signal-to-noise ratio (SNR) tends to infinity. Specifically, we reduce the gains of both Laplace and Gaussian noise cases to a one-dimensional integral. In addition, by limiting the use of the union bound to an L1-norm sphere with an optimized radius, we derive the sphere bound for the additive white Laplace noise channel. Simulation results show the efficiency of the proposed IS estimator in terms of the sample size and verify the accuracy of the prediction of the derived IS gain. Besides, we specialize the proposed framework to further improve the efficiency of the IS simulation based on the side information of the modulation. For the AWGGN channel with binary phase-shift keying (BPSK) modulation, we propose an enhanced NM-IS estimator, which outperforms the NM-IS estimator in efficiency. For the additive white Gaussian noise channel with M-PSK modulation, we propose an angular domain IS estimator and provide its efficiency analysis in terms of the asymptotic IS gain. Furthermore, in the performance evaluation of communication systems, it is often seen that researchers are more interested in the required SNR at a target error probability Pe than the other way around. The conventional solution to this Pe-targeted SNR estimation problem involves interpolation of simulated error probabilities at multiple handpicked SNRs for estimating the required SNR at the target error probability. We propose a Pe-targeted iterative IS estimator that solves the problem algorithmically. The proposed method can achieve the same efficiency (in terms of sample size) as estimating the error probability at the required SNR and allow the confidence interval of the SNR estimate to be obtained.
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.
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.