Good codes decodable by linear-sized circuits? I'm looking for error-correcting codes of the following type:


binary codes with constant rate, 
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of size $O(N)$, where $N$ is the encoding length.


Some background: 


Spielman, in Linear-Time Encodable and Decodable Error-Correcting Codes, gave codes decodable in $O(N)$ time in the logarithmic-cost RAM model, and also decodable by $O(N \log N)$-sized circuits.
Guruswami and Indyk gave an improved construction in Linear Time Encodable/Decodable Codes with Near-Optimal Rate.  They don't analyze the resulting circuit complexity, although I believe it is also $\Theta(N \log N)$.


Thanks in advance!
You should look at Tornado codes {1}, which, for any $R$ and $\epsilon&gt;0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of bits in time proportional to $n \ln \frac{1}{\epsilon}$ (see Theorem 1 in {1}).



{1} Luby, Michael G., et al. "Practical loss-resilient codes." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 1997:  http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf