Expander Codes
Authors:
Michael Sipser
and
Daniel A. Spielman.
Bibliographic Information:
Appeared in IEEE Transactions on Information Theory,
1996, Vol 42, No 6, pp. 1710-1722.
An extended abstract appeared
in the
Proceedings of the 35th Annual IEEE Conference
on Foundations of Computer Science, 1994, pp. 566-576.
Abstract
We present a new class of asymptotically good, linear error-correcting
codes based upon expander graphs. These codes have linear time sequential
decoding algorithms, logarithmic time parallel decoding algorithms with a
linear number of processors, and are simple to understand. We present
both randomized and explicit constructions for some of these codes.
Experimental results demonstrate the extremely good performance of the
randomly chosen codes.
You can download this paper as
Postscript,
compressed Postscript, or
PDF.
Daniel A. Spielman
Last modified: Fri Aug 24 19:07:34 2001