Linear-time encodable and decodable error-correcting codes
Daniel A. Spielman · IEEE Transactions on Information Theory · 1996
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.
Cited by 350 works. doi:10.1109/18.556668
Authors
References
- The Design and Analysis of Computer Algorithms
- The Theory of Error-Correcting Codes
- Eigenvalues and expanders
- Expander codes
- Superconcentrators
- Ramanujan graphs
- Explicit constructions of linear-sized superconcentrators
- Explicit Concentrators from Generalized N -Gons
- Explicit construction of linear sized tolerant networks
- Storage Modification Machines