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 Transactions on Information Theory

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, Michael W. Marcellin

Published May 27, 2010• 20 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2010.2046203

Related papers

Error-Correction Capability of Column-Weight-Three LDPC Codes

Shashi Kiran Chilappagari, Bane Vasic

In this paper, the error-correction capability of column-weight-three low-density parity-check (LDPC) codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to k ges 5 errors is to avoid cycles of length up to 2k in its Tanner graph. As a consequence of this result, it is shown that given any alpha > 0, exist N such that forall n > N, no code in the ensemble of column-weight-three codes can correct all alphan or fewer errors. The results are extended to the bit flipping algorithms.

arXiv:0807.3582•IEEE Transactions on Information Theory•Apr 22, 2009•38 citations

Error Correction Capability of Column-Weight-Three LDPC Codes

Bane Vasic, et al.

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 ≥ 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, ∃N such that ∀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.

•Jan 1, 2007•38 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

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

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 irregular LDPC codes under the Gallager a algorithm

Masakatu Morii, Hiroto Tamiya, Masanori Hirotomo

Many researchers have analyzed the error correction capability of LDPC codes for iterative decoding algorithms. However, it is difficult to show the error correction capability of LDPC codes for iterative decoding algorithms based on belief propagation theoretically. Chilappagari et al. reported the error correction capability of column-weight-three regular LDPC codes under the Gallager A algorithm since the behavior of the iterative decoding algorithm is easily analyzed. In this paper, we investigate the error correction capability of irregular LDPC codes. We also show relations between the decoding failures and 2-cycles of irregular LDPC codes under the Gallager A algorithm.

International Symposium on Information Theory and its Applications•Oct 1, 2016•2 citations
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, the error-correction capability of column-weight-three low-density parity-check (LDPC) codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to k ges 5 errors is to avoid cycles of length up to 2k in its Tanner graph. As a consequence of this result, it is shown that given any alpha > 0, exist N such that forall n > N, no code in the ensemble of column-weight-three codes can correct all alphan or fewer errors. The results are extended to the bit flipping algorithms.
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 ≥ 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, ∃N such that ∀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.
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.
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.
Many researchers have analyzed the error correction capability of LDPC codes for iterative decoding algorithms. However, it is difficult to show the error correction capability of LDPC codes for iterative decoding algorithms based on belief propagation theoretically. Chilappagari et al. reported the error correction capability of column-weight-three regular LDPC codes under the Gallager A algorithm since the behavior of the iterative decoding algorithm is easily analyzed. In this paper, we investigate the error correction capability of irregular LDPC codes. We also show relations between the decoding failures and 2-cycles of irregular LDPC codes under the Gallager A algorithm.