On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes
Name:
On_Trapping_Sets_and_Guarantee ...
Size:
519.8Kb
Format:
PDF
Description:
Final Accepted Manuscript
Affiliation
Department of Electrical and Computer Engineering, The University of ArizonaIssue Date
2010-04Keywords
Bit flipping algorithmserror correction capability
fixed sets
generalized low-density parity-check (LDPC) codes
low-density parity-check (LDPC) codes
trapping sets
Metadata
Show full item recordCitation
S. K. Chilappagari, D. V. Nguyen, B. Vasic and M. W. Marcellin, "On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes," in IEEE Transactions on Information Theory, vol. 56, no. 4, pp. 1600-1611, April 2010, doi: 10.1109/TIT.2010.2040962.Rights
© 2010 IEEE.Collection Information
This item from the UA Faculty Publications collection is made available by the University of Arizona with support from the University of Arizona Libraries. If you have questions, please contact us at repository@u.library.arizona.edu.Abstract
The relation between the girth and the guaranteed error correction capability of ¿ -left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least 3 ¿/4 is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.ISSN
0018-9448EISSN
1557-9654Version
Final accepted manuscriptae974a485f413a2113503eed53cd6c53
10.1109/tit.2010.2040962