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.


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