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 Transactions on Information Theory

Error Floor Approximation for LDPC Codes in the AWGN Channel

Brian K. Butler, Paul H. Siegel

Published Oct 17, 2014• 72 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2014.2363832

Related papers

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 (LDPC) codes with variable nodes of constant degree in the additive white Gaussian noise (AWGN) channel. Specifically, we focus on the performance of the sum-product algorithm (SPA) decoder formulated in the log-likelihood ratio (LLR) domain. We hypothesize that several published error floor levels are due to the manner in which decoder implementations handled the LLRs at high SNRs. We employ an LLR-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of trapping sets (or near-codewords) that are the dominant cause of the reported error floors. We develop a refined linear model, based on the work of Sun and others, that accurately predicts error floors caused by elementary tapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.

arXiv:1202.2826•Feb 13, 2012•3 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 variable-regular Low Density Parity Check (LDPC) codes in the Additive White Gaussian Noise (AWGN) channel. Specifically, we focus on the Sum-Product Algorithm (SPA) decoder in the log-domain at high SNRs. We hypothesize that several published error floor levels are due to numerical saturation within their decoders when handling high SNRs. We take care to develop a log-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of near-codewords / trapping sets that dominate the reported error floors. J. Sun, in his Ph.D. thesis, used a linear system model to show that error floors due to elementary trapping sets don't exist under certain conditions, assuming that the SPA decoder is non-saturating [1]. We develop a refined linear model which we find to be capable of predicting the error floors caused by elementary trapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2011•26 citations

A Semi Linear State Space Model for Error Floor Estimation of LDPC Codes Over the AWGN Channel

Ali Farsiabi, Amir H. Banihashemi

In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed by Richardson for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.

IEEE Transactions on Communications•Oct 6, 2022•1 citation

A Semi Linear State Space Model for Error Floor Estimation of LDPC codes over the AWGN Channel

Ali Farsiabi, Amir H. Banihashemi

In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate such behavior at around the operating point of zero. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•0 citations

Error Floor Estimation of LDPC Decoders — A Code Independent Approach to Measuring the Harmfulness of Trapping Sets

Ali Farsiabi, Amir H. Banihashemi

The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set (TS) structure to the error floor of low-density parity-check (LDPC) codes. In this paper, we provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages. Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS. We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor. Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel. The proposed technique can be viewed as the local application of importance sampling (IS) to the message-passing algorithm over the subgraph induced by the TS in the code's Tanner graph. In the message-passing process, to account for the effect of the rest of the Tanner graph, density evolution along with a simple correlation model is used to generate the messages coming into the TS from the rest of the Tanner graph. Extensive simulations demonstrate that the proposed technique can accurately estimate the error floor of LDPC codes over both additive white Gaussian noise (AWGN) channel and binary symmetric channel (BSC), for a variety of iterative decoding algorithms and quantization schemes.

IEEE Transactions on Communications•Feb 20, 2020•15 citations

Will the real error floor please stand up?

Xiaojie Zhang, Paul H. Siegel

In this paper we continue our study of the influence of message saturation and quantization on the error-rate performance of iterative, message-passing decoders for low-density parity-check (LDPC) codes. We extend our previous analytical results for the min-sum algorithm (MSA) and its variants to the sum-product algorithm (SPA), demonstrating the significant impact of message saturation on the appearance and location of error floors. Simulation results for selected LDPC codes on the binary symmetric channel (BSC) and the additive white Gaussian noise channel (AWGNC) confirm that the benefits of a quasiuniform quantization scheme, already observed in the context of MSA decoding, apply also to SPA-based decoding.

International Conference on Signal Processing and Communications (SPCOM)•Jul 1, 2012•8 citations
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.
This paper addresses the prediction of error floors of low-density parity-check (LDPC) codes with variable nodes of constant degree in the additive white Gaussian noise (AWGN) channel. Specifically, we focus on the performance of the sum-product algorithm (SPA) decoder formulated in the log-likelihood ratio (LLR) domain. We hypothesize that several published error floor levels are due to the manner in which decoder implementations handled the LLRs at high SNRs. We employ an LLR-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of trapping sets (or near-codewords) that are the dominant cause of the reported error floors. We develop a refined linear model, based on the work of Sun and others, that accurately predicts error floors caused by elementary tapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.
This paper addresses the prediction of error floors of variable-regular Low Density Parity Check (LDPC) codes in the Additive White Gaussian Noise (AWGN) channel. Specifically, we focus on the Sum-Product Algorithm (SPA) decoder in the log-domain at high SNRs. We hypothesize that several published error floor levels are due to numerical saturation within their decoders when handling high SNRs. We take care to develop a log-domain SPA decoder that does not saturate near-certain messages and find the error rates of our decoder to be lower by at least several orders of magnitude. We study the behavior of near-codewords / trapping sets that dominate the reported error floors. J. Sun, in his Ph.D. thesis, used a linear system model to show that error floors due to elementary trapping sets don't exist under certain conditions, assuming that the SPA decoder is non-saturating [1]. We develop a refined linear model which we find to be capable of predicting the error floors caused by elementary trapping sets for saturating decoders. Performance results of several codes at several levels of decoder saturation are presented.
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed by Richardson for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate such behavior at around the operating point of zero. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model.
The linear state-space model is a well-known code-independent method to estimate the contribution of a trapping set (TS) structure to the error floor of low-density parity-check (LDPC) codes. In this paper, we provide an in-depth analysis of this method by incorporating a more accurate model for the incoming messages to the TS structure that takes into account the randomness and the correlation among such messages. Based on this analysis, we demonstrate that both randomness and correlation result in the over-estimation of the failure probability of the TS. We then propose an alternate code-independent technique for the error floor estimation of iterative LDPC decoders that can accurately estimate the contribution of different TS structures in the error floor. Compared to the linear state-space model, the proposed method is not only more accurate, but also more general, in that, it is applicable to any saturating iterative message-passing decoder, symmetrically quantized or unquantized, over any memoryless binary-input output-symmetric channel. The proposed technique can be viewed as the local application of importance sampling (IS) to the message-passing algorithm over the subgraph induced by the TS in the code's Tanner graph. In the message-passing process, to account for the effect of the rest of the Tanner graph, density evolution along with a simple correlation model is used to generate the messages coming into the TS from the rest of the Tanner graph. Extensive simulations demonstrate that the proposed technique can accurately estimate the error floor of LDPC codes over both additive white Gaussian noise (AWGN) channel and binary symmetric channel (BSC), for a variety of iterative decoding algorithms and quantization schemes.
In this paper we continue our study of the influence of message saturation and quantization on the error-rate performance of iterative, message-passing decoders for low-density parity-check (LDPC) codes. We extend our previous analytical results for the min-sum algorithm (MSA) and its variants to the sum-product algorithm (SPA), demonstrating the significant impact of message saturation on the appearance and location of error floors. Simulation results for selected LDPC codes on the binary symmetric channel (BSC) and the additive white Gaussian noise channel (AWGNC) confirm that the benefits of a quasiuniform quantization scheme, already observed in the context of MSA decoding, apply also to SPA-based decoding.