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:

Thanks in advance!

  • 2
    $\begingroup$ Andy, coincidentally, I also came across this issue about a year ago and after a brief amount of searching, concluded that the question was open. So, I'm also curious if an answer's known. $\endgroup$
    – arnab
    Apr 12, 2011 at 23:45
  • 2
    $\begingroup$ This ECCC Report just came out. I haven't checked, but I expect it also gives $\Theta(N \log N)$ circuit. $\endgroup$ Apr 16, 2011 at 18:15
  • $\begingroup$ Is $O(N)$ decoding achievable in the AWGN model or the binary model? $\endgroup$
    – Turbo
    Sep 20, 2013 at 14:00
  • $\begingroup$ Good binary codes which are completely linear time ($O(N)$) encodable and decodable and achieve an error rate $2^{-N}$ where $N$ is block length of the code probably requires some fundamentally new idea. The best so far is along the lines of theorem $1$ in arxiv.org/pdf/1304.4321v2.pdf. Lets see if someone improves the $2^{-N^{0.49}}$ to $2^{-N^{1-\mu}}$ in there in $N^{1+\epsilon}$ encoding and decoding time which I believe should be possible (even with $\mu=0$). However, bringing $\epsilon$ to $0$ may need more than a few tricks. $\endgroup$
    – Turbo
    Dec 4, 2013 at 19:58
  • $\begingroup$ Have a look at Expander codes. These codes achieve linear time coding and decoding. The linearity is w.r.t to the size of the codeword. But I am not sure if they can be decoded using linear circuits. $\endgroup$ Apr 28, 2014 at 11:28

1 Answer 1


You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.