27
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 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
    Commented 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$
    – Peter Shor
    Commented Apr 16, 2011 at 18:15
  • $\begingroup$ Is $O(N)$ decoding achievable in the AWGN model or the binary model? $\endgroup$
    – Turbo
    Commented 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
    Commented 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$
    – Vivek Bagaria
    Commented Apr 28, 2014 at 11:28

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

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.