Improved Low-Density Parity-Check Codes Using Irregular Graphs

Authors: Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, and Daniel A. Spielman.

Bibliographic Information: Appeared in IEEE Transactions on Information Theory, 47(2), pp. 585-598, Feb. 2001.

Abstract

We construct new families of error-correcting codes based on Gallager's low density parity check codes. We improve on Gallager's results by introducing irregular parity check matrices. Demonstrating that irregular structure can improve performance is a key point of our work.

We consider irregular codes under both belief propagation and hard decision decoding, obtaining improvements over previous results for both types of decoding. For belief propagation, we report experimental results of irregular codes on both binary symmetric channels and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16,000 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.

We also study hard decision decoding, even though it does not perform as well as belief propagation, because it gives insight into the design of parity check codes. In particular, for hard decision decoding, we demonstrate how to prove performance guarantees for irregular parity check codes, extending the original work by Gallager. We also provide efficient methods for finding good irregular structures for hard decision decoding algorithms. Our rigorous analysis and our methodology for constructing good irregular codes constitute our other key contributions.


You can download this paper as Postscript, compressed Postscript, or PDF.
Daniel A. Spielman
Last modified: Fri Aug 24 15:48:20 2001