Error-Correction Capability of Column-Weight-Three LDPC Codes
Authors:
- 21 April 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 55 (5) , 2055-2061
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 ges 5 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 alpha > 0, exist N such that forall n > N, no code in the ensemble of column-weight-three codes can correct all alphan or fewer errors. The results are extended to the bit flipping algorithms.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On the error correction of regular LDPC codes using the flipping algorithm2007
- LP Decoding Corrects a Constant Fraction of ErrorsIEEE Transactions on Information Theory, 2006
- Using Linear Programming to Decode Binary Linear CodesIEEE Transactions on Information Theory, 2005
- An Introduction to Low-Density Parity-Check Codes2002
- Expander graph arguments for message-passing algorithmsIEEE Transactions on Information Theory, 2001
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Expander codesIEEE Transactions on Information Theory, 1996
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981
- Low-Density Parity-Check Codes1963