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.


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