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.