On the number of errors correctable with codes on graphs

Alexander Barg, Arya Mazumdar

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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.

Original languageEnglish (US)
Article number5695098
Pages (from-to)910-919
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Feb 2011
Externally publishedYes

Bibliographical note

Funding Information:
Manuscript received November 17, 2009; revised July 31, 2010; accepted July 31, 2010. Date of current version January 19, 2011. This work was supported in part by the NSF by grants CCF0830699, CCF0635271, DMS0807411, and CCF0916919. The material in this paper was presented at the 2009 IEEE International Symposium on Information Theory, Seoul, South Korea, July 2009.


  • Graph codes
  • hypergraph codes
  • iterative decoding
  • parallel concatenation of codes


Dive into the research topics of 'On the number of errors correctable with codes on graphs'. Together they form a unique fingerprint.

Cite this