Improved low-density parity-check codes using irregular graphs
Top Cited Papers
- 1 February 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 47 (2) , 585-598
- https://doi.org/10.1109/18.910576
Abstract
We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.Keywords
This publication has 15 references indexed in Scilit:
- Expander graph arguments for message-passing algorithmsIEEE Transactions on Information Theory, 2001
- Design of capacity-approaching irregular low-density parity-check codesIEEE Transactions on Information Theory, 2001
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Efficient erasure correcting codesIEEE Transactions on Information Theory, 2001
- Good error-correcting codes based on very sparse matricesIEEE Transactions on Information Theory, 1999
- Iterative decoding of compound codes by probability propagation in graphical modelsIEEE Journal on Selected Areas in Communications, 1998
- Expander codesIEEE Transactions on Information Theory, 1996
- Linear-time encodable and decodable error-correcting codesIEEE Transactions on Information Theory, 1996
- Near Shannon limit performance of low density paritycheck codesElectronics Letters, 1996
- Codes and iterative decoding on general graphsEuropean Transactions on Telecommunications, 1995