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

Information technology newsletter

Advances of the error-floor study of LDPC codes

Jiwen Zeng

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

Low-density parity check(LDPC)codes are known to perform very well under iterative decoding.However,these codes often exhibit an error floor phenomenon in the high signal-to-noise(SNR)region.This paper provides a comprehensive description of the cause of the error floor phenomenon of LDPC codes.It presents a detailed description of the trapping sets,describes the methods to estimate and reduce the error floor of LDPC codes.Finally,it proposes the future development of the error floor of LDPC codes.

Related papers

Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

Dung Viet Nguyen

Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

•Jan 1, 2012•1 citation

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

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

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

LDPC Code Density Evolution in the Error Floor Region

Brian K. Butler, Paul H. Siegel

This short paper explores density evolution (DE) for low-density parity-check (LDPC) codes at signal-to-noise-ratios (SNRs) that are significantly above the decoding threshold. The focus is on the additive white Gaussian noise channel and LDPC codes in which the variable nodes have regular degree. Prior work, using DE, produced results in the error floor region which were asymptotic in the belief-propagation decoder's log-likelihood ratio (LLR) values. We develop expressions which closely approximate the LLR growth behavior at moderate LLR magnitudes. We then produce bounds on the mean extrinsic check-node LLR values required, as a function of SNR, such that the growth rate of the LLRs exceeds that of a particular trapping set's internal LLRs such that its error floor contribution may be eliminated. We find that our predictions for the mean LLRs to be accurate in the error floor region, but the predictions for the LLR variance to be lacking beyond several initial iterations.

arXiv:1409.5783•Sep 19, 2014•1 citation

Construction of Irregular LDPC Codes by Quasi-Cyclic Extension

Jinghu Chen, R. Michael Tanner, Juntan Zhang +1 more

In this correspondence, we propose an approach to construct irregular low-density parity-check (LDPC) codes based on quasi-cyclic extension. When decoded iteratively, the constructed irregular LDPC codes exhibit a relatively low error floor in the high signal-to-noise ratio (SNR) region and are subject to relatively few undetected errors. The LDPC codes constructed based on the proposed scheme remain efficiently encodable

IEEE Transactions on Information Theory•Apr 1, 2007•35 citations
Low-density parity check(LDPC)codes are known to perform very well under iterative decoding.However,these codes often exhibit an error floor phenomenon in the high signal-to-noise(SNR)region.This paper provides a comprehensive description of the cause of the error floor phenomenon of LDPC codes.It presents a detailed description of the trapping sets,describes the methods to estimate and reduce the error floor of LDPC codes.Finally,it proposes the future development of the error floor of LDPC codes.
Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.
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.
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.
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.
This short paper explores density evolution (DE) for low-density parity-check (LDPC) codes at signal-to-noise-ratios (SNRs) that are significantly above the decoding threshold. The focus is on the additive white Gaussian noise channel and LDPC codes in which the variable nodes have regular degree. Prior work, using DE, produced results in the error floor region which were asymptotic in the belief-propagation decoder's log-likelihood ratio (LLR) values. We develop expressions which closely approximate the LLR growth behavior at moderate LLR magnitudes. We then produce bounds on the mean extrinsic check-node LLR values required, as a function of SNR, such that the growth rate of the LLRs exceeds that of a particular trapping set's internal LLRs such that its error floor contribution may be eliminated. We find that our predictions for the mean LLRs to be accurate in the error floor region, but the predictions for the LLR variance to be lacking beyond several initial iterations.