Error-correction capability of column-weight-three LDPC codes

Shashi Kiran Chilappagari; Bane Vasic

doi:10.1109/TIT.2009.2015990

Error-correction capability of column-weight-three LDPC codes

Shashi Kiran Chilappagari
, Bane Vasic

Research output: Contribution to journal › Article › peer-review

33 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	2055-2061
Number of pages	7
Journal	IEEE Transactions on Information Theory
Volume	55
Issue number	5
DOIs	https://doi.org/10.1109/TIT.2009.2015990
State	Published - 2009

Keywords

Error-correction capability
Gallager A algorithm
Low-density parity-check (LDPC) codes
Tanner graph
Trapping sets

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2009.2015990

Cite this

@article{85c50738e4d24737935f73f75b4f3663,

title = "Error-correction capability of column-weight-three LDPC codes",

abstract = "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.",

keywords = "Error-correction capability, Gallager A algorithm, Low-density parity-check (LDPC) codes, Tanner graph, Trapping sets",

author = "Chilappagari, \{Shashi Kiran\} and Bane Vasic",

note = "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",

year = "2009",

doi = "10.1109/TIT.2009.2015990",

language = "English (US)",

volume = "55",

pages = "2055--2061",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

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 - https://www.scopus.com/pages/publications/65749115017

UR - https://www.scopus.com/pages/publications/65749115017#tab=citedBy

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 -

Error-correction capability of column-weight-three LDPC codes

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this