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.
Abstract
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