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

On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes

Shashi Kiran Chilappagari, Dung Viet Nguyen, Bane Vasic, Michael W. Marcellin

Published Jan 1, 2008• 36 citations
OpenAlex

Abstract

The relation between the girth and the guaranteed error correction capability of γ-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least 3γ/4 is found based on the Moore bound. An upper bound on the guaranteed error correction capability is established by studying the sizes of smallest possible trapping sets. The results are extended to generalized LDPC codes. It is shown that generalized LDPC codes can correct a linear fraction of errors under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. It is also shown that the bound cannot be improved when γ is even by studying a class of trapping sets. A lower bound on the size of variable node sets which have the required expansion is established.

Related papers

On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes

S.K. Chilappagari, Dung Viet Nguyen, B. Vasic +1 more

The relation between the girth and the guaranteed error correction capability of¿-left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least3 ¿/4is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.

arXiv:0805.2427•IEEE Transactions on Information Theory•Mar 24, 2010•34 citations

On the guaranteed error correction capability of LDPC codes

Shashi Kiran Chilappagari, Dung Viet Nguyen, Bane V. Vasic +1 more

We investigate the relation between the girth and the guaranteed error correction capability of gamma-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms. A lower bound on the number of variable nodes which expand by a factor of at least 3gamma/4 is found based on the Moore bound. An upper bound on the guaranteed correction capability is established by studying the sizes of smallest possible trapping sets.

arXiv:0801.1276•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•5 citations

Girth of the Tanner graph and error correction capability of LDPC codes

Shashi Kiran Chilappagari, Dung Viet Nguyen, Bane V. Vasic +1 more

We investigate the relation between the girth and the guaranteed error correction capability of γ-left regular LDPC codes. For column-weight-three codes, we give upper and lower bounds on the number of errors correctable by the Gallager A algorithm. For higher column weight codes, we find the number of variable nodes which are guaranteed to expand by a factor of at least 3γ/4, hence giving a lower bound on the guaranteed correction capability under the bit flipping (serial and parallel) algorithms. We also establish upper bounds by studying the sizes of smallest possible trapping sets.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2008•7 citations

On the Error Correction of Iterative Bounded Distance Decoding of Generalized LDPC Codes

David Burshtein

Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.

arXiv:2507.12073•IEEE Transactions on Information Theory•Sep 16, 2025•0 citations

Two-Bit Bit Flipping Algorithms for LDPC Codes and Collective Error Correction

Dung Viet Nguyen, Bane V. Vasic

A new class of bit flipping algorithms for low-density parity-check 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.

IEEE Transactions on Communications•Feb 28, 2014•25 citations

On error correction capability of bit-flipping algorithm for LDPC codes

Wen-Yao Chen, Chung-Chin Lu

The error correction capability of bit-flipping decoding algorithm for low density parity-check (LDPC) codes is studied by introducing variable node adjacency (VNA) graphs which are derived from Tanner graphs of LDPC codes. For codes with column weight λ and girth g = 8, it can be shown that error patterns of weight less than or equal to λ - 1 can be corrected. This result implies that the bit-flipping algorithm could decode up to the random error-correcting capability over binary symmetric channel for girth 8 codes whose random error-correcting capability is equal to λ - 1.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•6 citations
The relation between the girth and the guaranteed error correction capability of γ-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least 3γ/4 is found based on the Moore bound. An upper bound on the guaranteed error correction capability is established by studying the sizes of smallest possible trapping sets. The results are extended to generalized LDPC codes. It is shown that generalized LDPC codes can correct a linear fraction of errors under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. It is also shown that the bound cannot be improved when γ is even by studying a class of trapping sets. A lower bound on the size of variable node sets which have the required expansion is established.
The relation between the girth and the guaranteed error correction capability of¿-left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least3 ¿/4is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.
We investigate the relation between the girth and the guaranteed error correction capability of γ-left regular LDPC codes. For column-weight-three codes, we give upper and lower bounds on the number of errors correctable by the Gallager A algorithm. For higher column weight codes, we find the number of variable nodes which are guaranteed to expand by a factor of at least 3γ/4, hence giving a lower bound on the guaranteed correction capability under the bit flipping (serial and parallel) algorithms. We also establish upper bounds by studying the sizes of smallest possible trapping sets.
Consider an ensemble of regular generalized LDPC (GLDPC) codes and assume that the same component code is associated with each parity check node. To decode a GLDPC code from the ensemble, we use the bit flipping bounded distance decoding algorithm, which is an extension of the bit flipping algorithm for LDPC codes. Previous work has shown conditions, under which, for a typical code in the ensemble with blocklength sufficiently large, a positive constant fraction of worst case errors can be corrected. In this work we first show that these requirements can be relaxed for ensembles with small left degrees. While previous work on GLDPC codes has considered expander graph arguments, our analysis formulates a necessary condition that the Tanner graph needs to satisfy for a failure event and then shows that the probability of this event vanishes for a sufficiently large blocklength. We then extend the analysis to random error correction and derive a lower bound on the fraction of random errors that can be corrected asymptotically. We discuss the extension of our results to non-binary GLDPC codes and present numerical examples.
A new class of bit flipping algorithms for low-density parity-check 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.
The error correction capability of bit-flipping decoding algorithm for low density parity-check (LDPC) codes is studied by introducing variable node adjacency (VNA) graphs which are derived from Tanner graphs of LDPC codes. For codes with column weight λ and girth g = 8, it can be shown that error patterns of weight less than or equal to λ - 1 can be corrected. This result implies that the bit-flipping algorithm could decode up to the random error-correcting capability over binary symmetric channel for girth 8 codes whose random error-correcting capability is equal to λ - 1.