Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm-part II

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

doi:10.1109/TIT.2010.2046203

Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm-part II

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

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

12 Scopus citations

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-weightthree LDPC code with Tanner graph of girth g ≥ 10 can correct all error patterns with up to (g/2-1) errors in at most g/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girth g le; 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.

Original language	English (US)
Article number	2046203
Pages (from-to)	2626-2639
Number of pages	14
Journal	IEEE Transactions on Information Theory
Volume	56
Issue number	6
DOIs	https://doi.org/10.1109/TIT.2010.2046203
State	Published - Jun 2010

Keywords

Error floor
Gallager A algorithm
Girth
Low-density parity-check (LDPC) codes
Trapping sets

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2010.2046203

Cite this

@article{f9cb93c3e6e841fbabfe05c163e9f542,

title = "Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm-part II",

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-weightthree LDPC code with Tanner graph of girth g ≥ 10 can correct all error patterns with up to (g/2-1) errors in at most g/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girth g le; 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.",

keywords = "Error floor, Gallager A algorithm, Girth, Low-density parity-check (LDPC) codes, Trapping sets",

author = "Chilappagari, {Shashi Kiran} and Nguyen, {Dung Viet} and Bane Vasic and Marcellin, {Michael W.}",

note = "Funding Information: Manuscript received July 22, 2008; revised May 08, 2009. Current version published May 19, 2010. This work was supported in part by the NSF under Grant CCF-0634969, IHCS-0725405, ITR-0325979, and in part by the INSIC-EHDR program. The work of S. K. Chilappagari was performed when he was with the Department of Electrical and Computer Engineering, University of Arizona, Tucson. The material in this paper was presented in part at the IEEE Information Theory Workshop (ITW), Porto, Portugal, May 5–9, 2008.",

year = "2010",

month = jun,

doi = "10.1109/TIT.2010.2046203",

language = "English (US)",

volume = "56",

pages = "2626--2639",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

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

number = "6",

}

TY - JOUR

T1 - Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm-part II

AU - Chilappagari, Shashi Kiran

AU - Nguyen, Dung Viet

AU - Vasic, Bane

AU - Marcellin, Michael W.

N1 - Funding Information: Manuscript received July 22, 2008; revised May 08, 2009. Current version published May 19, 2010. This work was supported in part by the NSF under Grant CCF-0634969, IHCS-0725405, ITR-0325979, and in part by the INSIC-EHDR program. The work of S. K. Chilappagari was performed when he was with the Department of Electrical and Computer Engineering, University of Arizona, Tucson. The material in this paper was presented in part at the IEEE Information Theory Workshop (ITW), Porto, Portugal, May 5–9, 2008.

PY - 2010/6

Y1 - 2010/6

N2 - 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-weightthree LDPC code with Tanner graph of girth g ≥ 10 can correct all error patterns with up to (g/2-1) errors in at most g/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girth g le; 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.

AB - 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-weightthree LDPC code with Tanner graph of girth g ≥ 10 can correct all error patterns with up to (g/2-1) errors in at most g/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girth g le; 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.

KW - Error floor

KW - Gallager A algorithm

KW - Girth

KW - Low-density parity-check (LDPC) codes

KW - Trapping sets

UR - http://www.scopus.com/inward/record.url?scp=77957556478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957556478&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2046203

DO - 10.1109/TIT.2010.2046203

M3 - Article

AN - SCOPUS:77957556478

SN - 0018-9448

VL - 56

SP - 2626

EP - 2639

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 6

M1 - 2046203

ER -

Error correction capability of column-weight-three LDPC codes under the Gallager A algorithm-part II

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this