Linear-Time Encodable

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(n log n). We present both randomized and explicit constructions of these codes. Index Terms- Asymptotically good error-correcting code, linear-time, expander graph, superconcentrators