Daniel A. Spielman.
Appeared in IEEE Transactions on Information Theory,
1996, Vol 42, No 6, pp. 1710-1722.
An extended abstract appeared
Proceedings of the 35th Annual IEEE Conference
on Foundations of Computer Science, 1994, pp. 566-576.
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
compressed Postscript, or
Daniel A. Spielman
Last modified: Fri Aug 24 19:07:34 2001