TY - JOUR
T1 - Error-correction capability of column-weight-three LDPC codes
AU - Chilappagari, Shashi Kiran
AU - Vasic, Bane
N1 - Funding Information:
Manuscript received October 18, 2007; revised October 27, 2008. Current version published April 22, 2009. This work was supported by the National Science Foundation (NSF) under Grants CCF-0634969, ITR-0325979, and INSIC-EHDR. The authors are with the Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85721 USA (e-mails: [email protected]. edu; [email protected]). Communicated by T. J. Richardson, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2009.2015990
PY - 2009
Y1 - 2009
N2 - 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 ≥ 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 α > 0, ∃ N such that ∀ n > N, no code in the ensemble of column-weight-three codes can correct all αn or fewer errors. The results are extended to the bit flipping algorithms.
AB - 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 ≥ 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 α > 0, ∃ N such that ∀ n > N, no code in the ensemble of column-weight-three codes can correct all αn or fewer errors. The results are extended to the bit flipping algorithms.
KW - Error-correction capability
KW - Gallager A algorithm
KW - Low-density parity-check (LDPC) codes
KW - Tanner graph
KW - Trapping sets
UR - http://www.scopus.com/inward/record.url?scp=65749115017&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=65749115017&partnerID=8YFLogxK
U2 - 10.1109/TIT.2009.2015990
DO - 10.1109/TIT.2009.2015990
M3 - Article
AN - SCOPUS:65749115017
SN - 0018-9448
VL - 55
SP - 2055
EP - 2061
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 5
ER -