Linear-time encodable and decodable error-correcting
codes
Author:
Daniel A. Spielman.
Bibliographic Information:
Appeared in IEEE Transactions on Information Theory,
1996, Vol 42, No 6, pp. 1723-1732.
An extended abstract appeared
in the
Proceedings of the
27th Annual ACM
Symposium on the
Theory of Computing.
Abstract
We present a class of asymptotically good
error-correcting codes that can be both
encoded and decoded in linear sequential time
and logarithmic parallel time with a linear
number of processors.
We present both randomized and explicit constructions
of these codes.
You can download this paper as
Postscript,
compressed Postscript, or
PDF.
Daniel A. Spielman
Last modified: Fri Aug 24 14:00:42 2001