Title :
Linear-time encodable and decodable error-correcting codes
Author :
Spielman, Daniel A.
Author_Institution :
Dept. of Math., MIT, Cambridge, MA, USA
fDate :
11/1/1996 12:00:00 AM
Abstract :
We present a new class of asymptotically good, linear error-correcting codes. These codes can be both encoded and decoded in linear time. They can also be encoded by logarithmic-depth circuits of linear size and decoded by logarithmic depth circuits of size O(nlogn). We present both randomized and explicit constructions of these codes
Keywords :
decoding; error correction codes; graph theory; linear codes; asymptotically good linear error-correcting codes; explicit constructions; linear-time decodable error-correcting codes; linear-time encodable error-correcting codes; logarithmic-depth circuits; randomized constructions; Circuits; Computational modeling; Costs; Decoding; Encoding; Error correction codes; Graph theory; Mathematics; Military computing; Polynomials;
Journal_Title :
Information Theory, IEEE Transactions on
