DocumentCode
1316405
Title
Linear-time encodable and decodable error-correcting codes
Author
Spielman, Daniel A.
Author_Institution
Dept. of Math., MIT, Cambridge, MA, USA
Volume
42
Issue
6
fYear
1996
fDate
11/1/1996 12:00:00 AM
Firstpage
1723
Lastpage
1731
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;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.556668
Filename
556668
Link To Document