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!

$\endgroup$
  • 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 '11 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 Apr 16 '11 at 18:15
  • $\begingroup$ Is $O(N)$ decoding achievable in the AWGN model or the binary model? $\endgroup$ – T.... Sep 20 '13 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$ – T.... Dec 4 '13 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 Apr 28 '14 at 11:28
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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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