Constructing Error-Correcting Codes from Expander Graphs

Author: Daniel A. Spielman

Bibliographic Information: Presented at the 1996 IMA workshop on Emerging Applications of Number Theory. Appeared in IMA volumes in mathematics and its applications, vol 109.


We survey a derivation of asymptotically good error-correcting codes from expander graphs. These codes, called Expander Codes, can be decoded in linear time. We explain how to modify this construction to produce asymptotically good codes that can be encoded as well as decoded in linear time.
You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.
Daniel A. Spielman
Last modified: Sun Aug 26 11:53:48 2001