On the Number of Errors Correctable with Codes on Graphs
Authors:
- 20 January 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 57 (2) , 910-919
Abstract
We study ensembles of codes on graphs (generalized low-density parity-check, or LDPC codes) constructed from random graphs and fixed local constrained codes, and their extension to codes on hypergraphs. It is known that the average minimum distance of codes in these ensembles grows linearly with the code length. We show that these codes can correct a linearly growing number of errors under simple iterative decoding algorithms. In particular, we show that this property extends to codes constructed by parallel concatenation of Hamming codes and other codes with small minimum distance. Previously known results that proved this property for graph codes relied on graph expansion and required the choice of local codes with large distance relative to their length.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Low-complexity error correction of Hamming-code-based LDPC codesProblems of Information Transmission, 2009
- On the Error Correction of Regular LDPC Codes Using the Flipping AlgorithmIEEE Transactions on Information Theory, 2008
- Performance of Iterative Algebraic Decoding of Codes Defined on Graphs: An Initial Investigation2007
- Distance properties of expander codesIEEE Transactions on Information Theory, 2005
- On codes from hypergraphsEuropean Journal of Combinatorics, 2004
- Generalized low density (Tanner) codes2003
- On expander codesIEEE Transactions on Information Theory, 2001
- On generalized low-density parity-check codes based on Hamming component codesIEEE Communications Letters, 1999
- Expander codesIEEE Transactions on Information Theory, 1996
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981