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

Allerton Conference on Communication, Control, and Computing

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

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

Published Sep 1, 2008• 7 citations
Publisher

Abstract

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.

DOI
10.1109/allerton.2008.4797702

Related papers

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

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

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

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.

•Jan 1, 2008•36 citations

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

Error Correction Capability of Column-Weight-Three LDPC Codes Under the Gallager A Algorithm—Part II

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

The relation between the girth and the error correction capability of column-weight-three LDPC codes under the Gallager A algorithm is investigated. It is shown that a column-weight-three LDPC code with Tanner graph of girthg¿ 10 can correct all error patterns with up to(g/2-1) errors in at mostg/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girthg¿ 8, it is shown that girth alone cannot guarantee correction of all error patterns with up to(g/2-1) errors under the Gallager A algorithm. Sufficient conditions to correct(g/2-1) errors are then established by studying trapping sets.

IEEE Transactions on Information Theory•May 27, 2010•20 citations

Guaranteed error correction capability of codes on graphs

Shashi Kiran Chilappagari, Bane V. Vasic, Michael W. Marcellin

The guaranteed error correction capability of left regular LDPC codes under different hard decision decision algorithms is investigated. A summary of recent results relating the column weight and girth of the Tanner graph to the guaranteed error correction capability is provided. The intuition behind expander based arguments and their potential to derive new results for column-weight-three codes is provided.

Information Theory and Applications Workshop (ITA)•Feb 1, 2009•6 citations

Error Correction Capability of Column-Weight-Three LDPC Codes

Shashi Kiran Chilappagari, Bane V. Vasic

In this paper, we investigate the error correction capability of column-weight-three LDPC codes when decoded using the Gallager A algorithm. We prove that the necessary condition for a code to correct $k \geq 5$ errors is to avoid cycles of length up to $2k$ in its Tanner graph. As a consequence of this result, we show that given any $α>0, \exists N $ such that $\forall n>N$, no code in the ensemble of column-weight-three codes can correct all $αn$ or fewer errors. We extend these results to the bit flipping algorithm.

arXiv:0710.3427•Oct 18, 2007•1 citation
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.
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.
The relation between the girth and the error correction capability of column-weight-three LDPC codes under the Gallager A algorithm is investigated. It is shown that a column-weight-three LDPC code with Tanner graph of girthg¿ 10 can correct all error patterns with up to(g/2-1) errors in at mostg/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girthg¿ 8, it is shown that girth alone cannot guarantee correction of all error patterns with up to(g/2-1) errors under the Gallager A algorithm. Sufficient conditions to correct(g/2-1) errors are then established by studying trapping sets.
In this paper, we investigate the error correction capability of column-weight-three LDPC codes when decoded using the Gallager A algorithm. We prove that the necessary condition for a code to correct k≥5k \geq 5k≥5 errors is to avoid cycles of length up to 2k2k2k in its Tanner graph. As a consequence of this result, we show that given any $α>0, \exists N $ such that ∀n>N\forall n>N∀n>N, no code in the ensemble of column-weight-three codes can correct all αnαnαn or fewer errors. We extend these results to the bit flipping algorithm.