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

Mediterranean Conference on Embedded Computing (MECO)

Importance Sampling Based Software Kit for LLR BP Decoding Simulation

Evgeny A. Likhobabin, Igor Volkov, Konstantin Zavertkin, Aleksei Ovinnikov, Vladimir V. Vityazev

Published Jun 1, 2019• 0 citations
Publisher

Abstract

This paper outlines a method for estimation of an error floor parameters for different LDPC codes based on importance sampling technique. The traditional approach to such estimations is based on Monte Carlo technique and has high computational complexity, especially for near-optimal decoding algorithms such as logarithmic-likelihood ratio belief propagation algorithm. It was shown that the proposed method allows to significantly reduce the computational cost required for an estimation of frame error probability in the high SNR region. Results of error floor estimation are presented for three LDPC codes: Margulis (2640, 1320), two quasi cyclic codes QC (22200, 5550) and QC (22200, 7400).

DOI
10.1109/meco.2019.8760172

Related papers

Predicting error floors of structured LDPC codes: deterministic bounds and estimates

Lara Dolecek, P. Lee, Zhengya Zhang +3 more

The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10-30. By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.

IEEE Journal on Selected Areas in Communications•Jul 29, 2009•94 citations

Error floors in LDPC codes: Fast simulation, bounds and hardware emulation

Pamela Lee, Lara Dolecek, Zhengya Zhang +3 more

Abstract — The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding, is known to approach Shannon limits in the asymptotic limit of large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a method, based on importance sampling and high SNR asymptotics as applied to suitably defined absorbing structures within the LDPC code, to predict error floors. Our results are in very close agreement with hardware-based experimental results, and moreover extend the prediction of the error probability to even lower regions. We compute both importance sampling estimates of error probabilities and deterministic estimates that are guaranteed to lower bound the error probability in the high SNR regime. I.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•12 citations

Error Floor Approximation for LDPC Codes in the AWGN Channel

Brian K. Butler, Paul H. Siegel

This paper addresses the prediction of error floors of low-density parity-check codes transmitted over the additive white Gaussian noise channel. Using a linear state-space model to estimate the behavior of the sum-product algorithm (SPA) decoder in the vicinity of trapping sets (TSs), we study the performance of the SPA decoder in the log-likelihood ratio (LLR) domain as a function of the LLR saturation level. When applied to several widely studied codes, the model accurately predicts a significant decrease in the error floor as the saturation level is allowed to increase. For nonsaturating decoders, however, we find that the state-space model breaks down after a small number of iterations due to the strong correlation of LLR messages. We then revisit Richardson's importance-sampling methodology for estimating error floors due to TSs when those floors are too low for Monte Carlo simulation. We propose modifications that account for the behavior of a nonsaturating decoder and present the resulting error floor estimates for the Margulis code. These estimates are much lower, significantly steeper, and more sensitive to iteration count than those previously reported.

IEEE Transactions on Information Theory•Oct 17, 2014•72 citations

Construction of LDPC Codes Using Cole's Modified Importance Sampling Method

Vasiliy S. Usatyuk, Егоров Сергей Иванович

Purpose of researchis a modification of Cole's importance sampling method for finding trapping sets in an LDPC code to speed up their search.Methods.Cole proposed a method for searching for trapping sets in an LDPC code by using a Monte Carlo method that causes the decoding algorithm to fail at nodes potentially contained in trapping sets. His method makes it possible to accelerate the study of the efficiency of medium-length LDPC codes in the region of large SNRs. The modified method uses the properties of automorphisms of Tanner graphs, which make it possible to exclude a significant number of symbolic nodes from the enumeration. The modified method also provides for an ordered enumeration over subgraphs containing cycles.Results.The proposed method made it possible to speed up the search for trapping sets in Mackay's PEG(1008, 504) LDPC code by 5027 times compared to the Velasquez-Subramani method, and 43 times faster compared to the original Cole method. In the case of (2640, 1320) LDPC Margulis code, the proposed method is 28 times faster than the Velasquez-Subramani quasi-cyclic method and 134 times faster than the original Cole method.Conclusion.The result of experimental studies showed the possibility of using the developed method to improve the connectivity spectrum, increase the code distance of QC-LDPC codes. This made it possible to reduce the probability of a bit error at the decoder output by orders of magnitude at high signal-to-noise ratios in the AWGN channel.

Proceedings of Southwest State University•Apr 14, 2023•5 citations

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

A General Method for Finding Low Error Rates of LDPC Codes

Chad A. Cole, Stephen G. Wilson, E.K. Hall +1 more

This paper outlines a three-step procedure for determining the low bit error rate performance curve of a wide class of LDPC codes of moderate length. The traditional method to estimate code performance in the higher SNR region is to use a sum of the contributions of the most dominant error events to the probability of error. These dominant error events will be both code and decoder dependent, consisting of low-weight codewords as well as non-codeword events if ML decoding is not used. For even moderate length codes, it is not feasible to find all of these dominant error events with a brute force search. The proposed method provides a convenient way to evaluate very low bit error rate performance of an LDPC code without requiring knowledge of the complete error event weight spectrum or resorting to a Monte Carlo simulation. This new method can be applied to various types of decoding such as the full belief propagation version of the message passing algorithm or the commonly used min-sum approximation to belief propagation. The proposed method allows one to efficiently see error performance at bit error rates that were previously out of reach of Monte Carlo methods. This result will provide a solid foundation for the analysis and design of LDPC codes and decoders that are required to provide a guaranteed very low bit error rate performance at certain SNRs.

arXiv:cs/0605051•May 11, 2006•102 citations
This paper outlines a method for estimation of an error floor parameters for different LDPC codes based on importance sampling technique. The traditional approach to such estimations is based on Monte Carlo technique and has high computational complexity, especially for near-optimal decoding algorithms such as logarithmic-likelihood ratio belief propagation algorithm. It was shown that the proposed method allows to significantly reduce the computational cost required for an estimation of frame error probability in the high SNR region. Results of error floor estimation are presented for three LDPC codes: Margulis (2640, 1320), two quasi cyclic codes QC (22200, 5550) and QC (22200, 7400).
The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10-30. By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.
Abstract — The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding, is known to approach Shannon limits in the asymptotic limit of large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a method, based on importance sampling and high SNR asymptotics as applied to suitably defined absorbing structures within the LDPC code, to predict error floors. Our results are in very close agreement with hardware-based experimental results, and moreover extend the prediction of the error probability to even lower regions. We compute both importance sampling estimates of error probabilities and deterministic estimates that are guaranteed to lower bound the error probability in the high SNR regime. I.
This paper addresses the prediction of error floors of low-density parity-check codes transmitted over the additive white Gaussian noise channel. Using a linear state-space model to estimate the behavior of the sum-product algorithm (SPA) decoder in the vicinity of trapping sets (TSs), we study the performance of the SPA decoder in the log-likelihood ratio (LLR) domain as a function of the LLR saturation level. When applied to several widely studied codes, the model accurately predicts a significant decrease in the error floor as the saturation level is allowed to increase. For nonsaturating decoders, however, we find that the state-space model breaks down after a small number of iterations due to the strong correlation of LLR messages. We then revisit Richardson's importance-sampling methodology for estimating error floors due to TSs when those floors are too low for Monte Carlo simulation. We propose modifications that account for the behavior of a nonsaturating decoder and present the resulting error floor estimates for the Margulis code. These estimates are much lower, significantly steeper, and more sensitive to iteration count than those previously reported.
Purpose of researchis a modification of Cole's importance sampling method for finding trapping sets in an LDPC code to speed up their search.Methods.Cole proposed a method for searching for trapping sets in an LDPC code by using a Monte Carlo method that causes the decoding algorithm to fail at nodes potentially contained in trapping sets. His method makes it possible to accelerate the study of the efficiency of medium-length LDPC codes in the region of large SNRs. The modified method uses the properties of automorphisms of Tanner graphs, which make it possible to exclude a significant number of symbolic nodes from the enumeration. The modified method also provides for an ordered enumeration over subgraphs containing cycles.Results.The proposed method made it possible to speed up the search for trapping sets in Mackay's PEG(1008, 504) LDPC code by 5027 times compared to the Velasquez-Subramani method, and 43 times faster compared to the original Cole method. In the case of (2640, 1320) LDPC Margulis code, the proposed method is 28 times faster than the Velasquez-Subramani quasi-cyclic method and 134 times faster than the original Cole method.Conclusion.The result of experimental studies showed the possibility of using the developed method to improve the connectivity spectrum, increase the code distance of QC-LDPC codes. This made it possible to reduce the probability of a bit error at the decoder output by orders of magnitude at high signal-to-noise ratios in the AWGN channel.
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.
This paper outlines a three-step procedure for determining the low bit error rate performance curve of a wide class of LDPC codes of moderate length. The traditional method to estimate code performance in the higher SNR region is to use a sum of the contributions of the most dominant error events to the probability of error. These dominant error events will be both code and decoder dependent, consisting of low-weight codewords as well as non-codeword events if ML decoding is not used. For even moderate length codes, it is not feasible to find all of these dominant error events with a brute force search. The proposed method provides a convenient way to evaluate very low bit error rate performance of an LDPC code without requiring knowledge of the complete error event weight spectrum or resorting to a Monte Carlo simulation. This new method can be applied to various types of decoding such as the full belief propagation version of the message passing algorithm or the commonly used min-sum approximation to belief propagation. The proposed method allows one to efficiently see error performance at bit error rates that were previously out of reach of Monte Carlo methods. This result will provide a solid foundation for the analysis and design of LDPC codes and decoders that are required to provide a guaranteed very low bit error rate performance at certain SNRs.