Iterative decoding of LDPC codes: some bounds and properties

David Burshtein and Gadi Miller

Physica A: Statistical Mechanics and its Applications, 2001, vol. 302, issue 1, 35-43

Abstract: We consider iterative message passing algorithms for decoding low-density parity-check codes, when applied to an arbitrary binary-input symmetric-output channel, and review some bounds and properties of these algorithms that we recently derived. We show that expander graph arguments may be used to prove that message passing algorithms can correct a linear number of erroneous messages. The implication of this result is that when the block length is sufficiently large, once a message passing algorithm has corrected a sufficiently large fraction of the errors, it will eventually correct all errors. The results hold for various message passing algorithms, including Gallager's hard decision and soft decision (with clipping) decoding algorithms. We also discuss some other properties of the iterative algorithm, such as the gap between maximum likelihood and iterative decoding as the connectivity of the parity-check matrix increases.

Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437101004381
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:302:y:2001:i:1:p:35-43

DOI: 10.1016/S0378-4371(01)00438-1

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().