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

International Symposium on Information Theory and its Applications

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

Takakazu Sakai, Koji Shibata

Published Oct 1, 2010• 1 citation
Publisher

Abstract

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.

DOI
10.1109/isita.2010.5649219

Related papers

Fast simulation of LDPC codes over additive non-Gaussian noise channel

Takakazu Sakai, Koji Shibata

This paper shows a fast simulation method of low-density parity-check (LDPC) codes over an additive non-Gaussian noise channel. The evaluation of an error performance of LDPC codes is usually executed by using a Monte-Carlo simulation since the theoretical calculation method has not been reported. It is very difficult to evaluate an error performance of LDPC codes with finite block length when the error probability is very low. To solve this problem, some fast simulation methods by using importance sampling (IS) are proposed. However, the conventional methods can not reduce the simulation time of LDPC codes over an additive non-Gaussian noise channel because the simulation probability density function (PDF) used in IS is designed for an additive white Gaussian noise. We propose a new simulation PDF design related to the Chernoff bound to estimate an error performance of LDPC codes over an additive non-Gaussian noise channel. In addition, we show some numerical examples to demonstrate the effectiveness of the proposed simulation method. The simulation time of the proposed method is reduced to about 1/2000 of that of the conventional method when we estimate the frame error rate of 10−10.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•0 citations

Fast Performance Evaluation Method of LDPC Codes

Takakazu Sakai, Koji Shibata

This paper shows a fast estimation method of very low error rate of low-density parity-check (LDPC) codes. No analytical tool is available to evaluate performance of LDPC codes, and the traditional Monte Carlo simulation methods can not estimate the low error rate of LDPC codes due to the limitation of time. To conquer this problem, we propose another simulation method which is based on the optimal simulation probability density function (PDF). The proposed simulation PDF can also avoid the dependency between the simulation time and the number of dominant trapping sets, which is the problem of some fast simulation methods based on the error event simulation method. Additionally, we show some numerical examples to demonstrate the effectiveness of the proposed method. The simulation time of the proposed method is reduced to almost less than 1/10 of that of Cole et al.'s method under the condition of the same accuracy of the estimator.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2011•1 citation

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, 2009•3 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, 2023•2 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, 2010•5 citations

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

A. Yu. Uglovskii, I. A. Melnikov, I. A. Alexeev +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.

Problems of Information Transmission•Dec 1, 2023•8 citations
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.
This paper shows a fast simulation method of low-density parity-check (LDPC) codes over an additive non-Gaussian noise channel. The evaluation of an error performance of LDPC codes is usually executed by using a Monte-Carlo simulation since the theoretical calculation method has not been reported. It is very difficult to evaluate an error performance of LDPC codes with finite block length when the error probability is very low. To solve this problem, some fast simulation methods by using importance sampling (IS) are proposed. However, the conventional methods can not reduce the simulation time of LDPC codes over an additive non-Gaussian noise channel because the simulation probability density function (PDF) used in IS is designed for an additive white Gaussian noise. We propose a new simulation PDF design related to the Chernoff bound to estimate an error performance of LDPC codes over an additive non-Gaussian noise channel. In addition, we show some numerical examples to demonstrate the effectiveness of the proposed simulation method. The simulation time of the proposed method is reduced to about 1/2000 of that of the conventional method when we estimate the frame error rate of 10−10.
This paper shows a fast estimation method of very low error rate of low-density parity-check (LDPC) codes. No analytical tool is available to evaluate performance of LDPC codes, and the traditional Monte Carlo simulation methods can not estimate the low error rate of LDPC codes due to the limitation of time. To conquer this problem, we propose another simulation method which is based on the optimal simulation probability density function (PDF). The proposed simulation PDF can also avoid the dependency between the simulation time and the number of dominant trapping sets, which is the problem of some fast simulation methods based on the error event simulation method. Additionally, we show some numerical examples to demonstrate the effectiveness of the proposed method. The simulation time of the proposed method is reduced to almost less than 1/10 of that of Cole et al.'s method under the condition of the same accuracy of the estimator.
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.
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.
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.
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.