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 Conference on Information and Communication Technology Convergence (ICTC)

On the combinatorial substructures of LDPC codes causing error floors in the AWGN channel

Hosung Park, Jong‐Seon No, Beomkyu Shin, Habong Chung

Published Oct 1, 2012• 1 citation
Publisher

Abstract

Finite-length low-density parity-check (LDPC) codes usually suffer from error floors in high signal-to-noise ratio (SNR) region. The error floor in the additive white Gaussian noise (AWGN) channel is known to be caused by trapping sets or absorbing sets. In this paper, we investigate combinatorial properties of trapping sets by using graph-theoretic approach. All non-isomorphic trapping sets are identified by a graph-theoretic tool and a method to distinguish the trapping sets which cannot appear in any protograph-based LDPC codes are proposed. Finally, a measure for estimating the harmfulness of trapping sets is proposed by using the linear system model of trapping sets.

DOI
10.1109/ictc.2012.6387166

Related papers

Absorbing Set Analysis and Design of LDPC Codes from Transversal Designs over the AWGN Channel

Alexander Gruner, Huber, Michael

In this paper we construct low-density parity-check (LDPC) codes from transversal designs with low error-floors over the additive white Gaussian noise (AWGN) channel. The constructed codes are based on transversal designs that arise from sets of mutually orthogonal Latin squares (MOLS) with cyclic structure. For lowering the error-floors, our approach is twofold: First, we give an exhaustive classification of so-called absorbing sets that may occur in the factor graphs of the given codes. These purely combinatorial substructures are known to be the main cause of decoding errors in the error-floor region over the AWGN channel by decoding with the standard sum-product algorithm (SPA). Second, based on this classification, we exploit the specific structure of the presented codes to eliminate the most harmful absorbing sets and derive powerful constraints for the proper choice of code parameters in order to obtain codes with an optimized error-floor performance.

arXiv:1403.4405•Mar 18, 2014•0 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

Causes and dynamics of LDPC error floors on AWGN channels

Shuai Zhang, Christian B. Schlegel

It is well-known that the performance of low-density parity-check codes is compromised by the emergence of an error floor, which is caused by so-called trapping sets. By identifying the dominant trapping sets, this error floor can be estimated analytically using a linear model. In this paper, this linear approach is improved to make the analysis more accurate. Then, guided by the error probability formula, a simple but effective method to improve the code performance in the error floor region is proposed, by introducing a boosting factor to the log-likelihood ratios returned from unsatisfied check nodes during the early decoding stages. It is shown that the effect of the dominant trapping sets can thus be reduced. The dominance of trapping sets can be further reduced by extending the computational range of the LLRs at the decoder. To illustrate these ideas, a short regular LDPC code constructed by Tanner, as well as the IEEE 802.3 LDPC code, are studied.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2011•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 (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

Analysis of Absorbing Sets and Fully Absorbing Sets of Array-Based LDPC Codes

Lara Dolecek, Zhengya Zhang, Venkat Anantharam +2 more

The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class of$C_{p, \gamma}$array-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes for$\gamma = 2,3,4$, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2010•207 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 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
Finite-length low-density parity-check (LDPC) codes usually suffer from error floors in high signal-to-noise ratio (SNR) region. The error floor in the additive white Gaussian noise (AWGN) channel is known to be caused by trapping sets or absorbing sets. In this paper, we investigate combinatorial properties of trapping sets by using graph-theoretic approach. All non-isomorphic trapping sets are identified by a graph-theoretic tool and a method to distinguish the trapping sets which cannot appear in any protograph-based LDPC codes are proposed. Finally, a measure for estimating the harmfulness of trapping sets is proposed by using the linear system model of trapping sets.
In this paper we construct low-density parity-check (LDPC) codes from transversal designs with low error-floors over the additive white Gaussian noise (AWGN) channel. The constructed codes are based on transversal designs that arise from sets of mutually orthogonal Latin squares (MOLS) with cyclic structure. For lowering the error-floors, our approach is twofold: First, we give an exhaustive classification of so-called absorbing sets that may occur in the factor graphs of the given codes. These purely combinatorial substructures are known to be the main cause of decoding errors in the error-floor region over the AWGN channel by decoding with the standard sum-product algorithm (SPA). Second, based on this classification, we exploit the specific structure of the presented codes to eliminate the most harmful absorbing sets and derive powerful constraints for the proper choice of code parameters in order to obtain codes with an optimized error-floor performance.
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.
It is well-known that the performance of low-density parity-check codes is compromised by the emergence of an error floor, which is caused by so-called trapping sets. By identifying the dominant trapping sets, this error floor can be estimated analytically using a linear model. In this paper, this linear approach is improved to make the analysis more accurate. Then, guided by the error probability formula, a simple but effective method to improve the code performance in the error floor region is proposed, by introducing a boosting factor to the log-likelihood ratios returned from unsatisfied check nodes during the early decoding stages. It is shown that the effect of the dominant trapping sets can thus be reduced. The dominance of trapping sets can be further reduced by extending the computational range of the LLRs at the decoder. To illustrate these ideas, a short regular LDPC code constructed by Tanner, as well as the IEEE 802.3 LDPC code, are studied.
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.
The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class ofCp,γC_{p, \gamma}Cp,γ​array-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes forγ=2,3,4\gamma = 2,3,4γ=2,3,4, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.
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.