LINEAR-TIME ENCODABLE AND DECODABLE ERROR-CORRECTING CODES

Authors
SPIELMAN DA
Citation
Da. Spielman, LINEAR-TIME ENCODABLE AND DECODABLE ERROR-CORRECTING CODES, IEEE transactions on information theory, 42(6), 1996, pp. 1723-1731
Citations number
25
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
42
Issue
6
Year of publication
1996
Part
1
Pages
1723 - 1731
Database
ISI
SICI code
0018-9448(1996)42:6<1723:LEADEC>2.0.ZU;2-8
Abstract
We present a new class of asymptotically good, linear error-correcting codes. These codes can be both encoded and decoded in linear time. Th ey can also be encoded by logarithmic-depth circuits of linear size an d decoded by logarithmic depth circuits of size O(n log n). We present both randomized and explicit constructions of these codes.