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 International Symposium on Information Theory (ISIT)

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

Ali Farsiabi, Amir H. Banihashemi

Published Jun 26, 2022• 0 citations
Publisher

Abstract

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.

DOI
10.1109/isit50566.2022.9834504

Related papers

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

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

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

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

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 Analysis of LDPC Column Layered Decoders

Ali Farsiabi, Amir H. Banihashemi

In this letter, we analyze the error floor of column layered decoders, also known as shuffled decoders, for low-density parity-check (LDPC) codes under saturating sum-product algorithm (SPA). To estimate the error floor, we evaluate the failure rate of different trapping sets (TSs) that contribute to the frame error rate in the error floor region. For each such TS, we model the dynamics of SPA in the vicinity of the TS by a linear state-space model that incorporates the information of the layered message-passing schedule. Consequently, the model parameters and the failure rate of the TS change as a result of the change in the order by which the messages of different layers are updated. This, in turn, causes the error floor of the code to change as a function of scheduling. Based on the proposed analysis, we then devise an efficient search algorithm to find a schedule that minimizes the error floor. Simulation results are presented to verify the accuracy of the proposed error floor estimation technique.

arXiv:2107.11479•IEEE Communications Letters•Dec 21, 2021•3 citations
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.
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.
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 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.
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.
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.
In this letter, we analyze the error floor of column layered decoders, also known as shuffled decoders, for low-density parity-check (LDPC) codes under saturating sum-product algorithm (SPA). To estimate the error floor, we evaluate the failure rate of different trapping sets (TSs) that contribute to the frame error rate in the error floor region. For each such TS, we model the dynamics of SPA in the vicinity of the TS by a linear state-space model that incorporates the information of the layered message-passing schedule. Consequently, the model parameters and the failure rate of the TS change as a result of the change in the order by which the messages of different layers are updated. This, in turn, causes the error floor of the code to change as a function of scheduling. Based on the proposed analysis, we then devise an efficient search algorithm to find a schedule that minimizes the error floor. Simulation results are presented to verify the accuracy of the proposed error floor estimation technique.