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 Symposium on Information Theory and its Applications

Error correction capability of irregular LDPC codes under the Gallager a algorithm

Masakatu Morii, Hiroto Tamiya, Masanori Hirotomo

Published Oct 1, 2016• 2 citations
OpenAlex

Abstract

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.

Related papers

Further Results on the Error Correction Capability of Irregular LDPC Codes under the Gallager A Algorithm

Masanori Hirotomo, Hiroto Tamiya, Masakatu Mori

In this paper, we investigate the error correction capability of irregular LDPC codes. We have shown relationships between the decoding failure and the structures of the Tanner graph of irregular LDPC codes under the Gallager A algorithm. In this analysis, we focused on the structures of connecting degree-two variable nodes, called 2-cycle. In this paper, we present new structures of the subgraph which induces the decoding failure of irregular LDPC codes under the Gallager A algorithm. Furthermore, we analyze relationships between the newly found structures of subgraph and the decoding failure of irregular LDPC codes.

International Symposium on Information Theory and its Applications•Oct 1, 2018•0 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

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

Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm

Pavel S. Rybin

This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.

Journal of Communications Technology and Electronics•Dec 1, 2016•2 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

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
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.
In this paper, we investigate the error correction capability of irregular LDPC codes. We have shown relationships between the decoding failure and the structures of the Tanner graph of irregular LDPC codes under the Gallager A algorithm. In this analysis, we focused on the structures of connecting degree-two variable nodes, called 2-cycle. In this paper, we present new structures of the subgraph which induces the decoding failure of irregular LDPC codes under the Gallager A algorithm. Furthermore, we analyze relationships between the newly found structures of subgraph and the decoding failure of irregular LDPC codes.
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 ≥ 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.
This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.
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.
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.