<p>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}).</p>

<hr>

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

CC BY-SA 3.0
2014-06-11T01:16:05.890Z
2014-06-11T01:16:05.890Z
Ari Trachtenberg
<p>I'm looking for error-correcting codes of the following type:</p>

<ul>
<li><p>binary codes with constant rate, </p></li>
<li><p>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.</p></li>
</ul>

<p>Some background: </p>

<ul>
<li><p>Spielman, in <a href="http://tinyurl.com/3ebfd28">Linear-Time Encodable and Decodable Error-Correcting Codes</a>, gave codes decodable in $O(N)$ time in the <em>logarithmic-cost RAM model</em>, and also decodable by $O(N \log N)$-sized circuits.</p></li>
<li><p>Guruswami and Indyk gave an improved construction in <a href="http://tinyurl.com/3gnjeov">Linear Time Encodable/Decodable Codes with Near-Optimal Rate</a>.  They don't analyze the resulting circuit complexity, although I believe it is also $\Theta(N \log N)$.</p></li>
</ul>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2011-04-12T23:45:24.280Z
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.
arnab
CC BY-SA 3.0
2011-04-16T18:15:11.353Z
This [ECCC Report](http://eccc.hpi-web.de/report/2011/058/) just came out. I haven't checked, but I expect it also gives $\Theta(N \log N)$ circuit.
Peter Shor 
CC BY-SA 3.0
2013-09-20T14:00:13.610Z
Is $O(N)$ decoding achievable in the AWGN model or the binary model?
Turbo
CC BY-SA 3.0
2013-12-04T19:58:30.613Z
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 http://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.
Turbo
CC BY-SA 3.0
2014-04-28T11:28:56.297Z
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.
Vivek Bagaria
<co.combinatorics><it.information-theory><coding-theory>
Good codes decodable by linear-sized circuits?
Andy Drucker
# Good codes decodable by linear-sized circuits?

(Asked by: username_0 on 2011-04-10)

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](http://tinyurl.com/3ebfd28), 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](http://tinyurl.com/3gnjeov). They don't analyze the resulting circuit complexity, although I believe it is also $\Theta(N \log N)$.

Thanks in advance!

**Tags:** co.combinatorics, it.information-theory, coding-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: This [ECCC Report](http://eccc.hpi-web.de/report/2011/058/) just came out. I haven't checked, but I expect it also gives $\Theta(N \log N)$ circuit.  
> **username_3**: Is $O(N)$ decoding achievable in the AWGN model or the binary model?  
> **username_3**: 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 http://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.  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2014-06-11. Score: 2

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>


---

