Girth of the tanner graph and error correction capability of LDPC codes

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

doi:10.1109/ALLERTON.2008.4797702

Girth of the tanner graph and error correction capability of LDPC codes

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	46th Annual Allerton Conference on Communication, Control, and Computing
Pages	1238-1245
Number of pages	8
DOIs	https://doi.org/10.1109/ALLERTON.2008.4797702
State	Published - 2008
Event	46th Annual Allerton Conference on Communication, Control, and Computing - Monticello, IL, United States Duration: Sep 24 2008 → Sep 26 2008

Publication series

Name	46th Annual Allerton Conference on Communication, Control, and Computing

Other

Other	46th Annual Allerton Conference on Communication, Control, and Computing
Country/Territory	United States
City	Monticello, IL
Period	9/24/08 → 9/26/08

Keywords

Bit flipping algorithms
Error correction capability
Gallager a algorithm
Low-density parity-check codes

ASJC Scopus subject areas

Computer Networks and Communications
Software
Control and Systems Engineering
Communication

Access to Document

10.1109/ALLERTON.2008.4797702

Cite this

Chilappagari, S. K., Nguyen, D. V., Vasić, B., & Marcellin, M. W. (2008). Girth of the tanner graph and error correction capability of LDPC codes. In 46th Annual Allerton Conference on Communication, Control, and Computing (pp. 1238-1245). Article 4797702 (46th Annual Allerton Conference on Communication, Control, and Computing). https://doi.org/10.1109/ALLERTON.2008.4797702

Girth of the tanner graph and error correction capability of LDPC codes. / Chilappagari, Shashi Kiran; Nguyen, Dung Viet; Vasić, Bane et al.
46th Annual Allerton Conference on Communication, Control, and Computing. 2008. p. 1238-1245 4797702 (46th Annual Allerton Conference on Communication, Control, and Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chilappagari, SK, Nguyen, DV, Vasić, B & Marcellin, MW 2008, Girth of the tanner graph and error correction capability of LDPC codes. in 46th Annual Allerton Conference on Communication, Control, and Computing., 4797702, 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 1238-1245, 46th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, United States, 9/24/08. https://doi.org/10.1109/ALLERTON.2008.4797702

@inproceedings{37364e7267f14916838e04bb29a97516,

title = "Girth of the tanner graph and error correction capability of LDPC codes",

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

keywords = "Bit flipping algorithms, Error correction capability, Gallager a algorithm, Low-density parity-check codes",

author = "Chilappagari, {Shashi Kiran} and Nguyen, {Dung Viet} and Bane Vasi{\'c} and Marcellin, {Michael W.}",

year = "2008",

doi = "10.1109/ALLERTON.2008.4797702",

language = "English (US)",

isbn = "9781424429264",

series = "46th Annual Allerton Conference on Communication, Control, and Computing",

pages = "1238--1245",

booktitle = "46th Annual Allerton Conference on Communication, Control, and Computing",

note = "46th Annual Allerton Conference on Communication, Control, and Computing ; Conference date: 24-09-2008 Through 26-09-2008",

}

TY - GEN

T1 - Girth of the tanner graph and error correction capability of LDPC codes

AU - Chilappagari, Shashi Kiran

AU - Nguyen, Dung Viet

AU - Vasić, Bane

AU - Marcellin, Michael W.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Bit flipping algorithms

KW - Error correction capability

KW - Gallager a algorithm

KW - Low-density parity-check codes

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

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

U2 - 10.1109/ALLERTON.2008.4797702

DO - 10.1109/ALLERTON.2008.4797702

M3 - Conference contribution

AN - SCOPUS:64549086395

SN - 9781424429264

T3 - 46th Annual Allerton Conference on Communication, Control, and Computing

SP - 1238

EP - 1245

BT - 46th Annual Allerton Conference on Communication, Control, and Computing

T2 - 46th Annual Allerton Conference on Communication, Control, and Computing

Y2 - 24 September 2008 through 26 September 2008

ER -

Girth of the tanner graph and error correction capability of LDPC codes

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this