<p>As far as I know, people conjecture that for Polar codes and any fixed DMBSC (discrete memoryless binary symmetric channel), $\log M \leq nC - O(n^{1-c})$ for some absolute constant $c &gt; 0$ and vanishing error probability should be possible (or in other words, in order to be $\epsilon$ close to capacity, only a polynomially large $n$ in $1/\epsilon$ would suffice. However, there is no rigorous published proof available at this point. There are rumors about an upcoming proof, but that's not official yet.</p>

CC BY-SA 3.0
2013-03-21T02:49:12.590Z
Thanks a lot. So do I assume correctly that for other families of codes even less is known?
Marco Tomamichel
CC BY-SA 3.0
2013-03-21T14:51:01.790Z
In terms of provable finite length guarantees for general memoryless channels, yes. Except for Forney/Justesen's concatenated codes which are capacity achieving but are known to require $n = exp(1/\epsilon)$ to be $\epsilon$-close to capacity.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-04-12T02:17:00.700Z
*Update*. The rumored result "Polar Codes: Speed of polarization and polynomial gap to capacity" by Guruswami and Xia is now available, which hopefully answers your question: http://eccc.hpi-web.de/report/2013/050/
Mahdi Cheraghchi
CC BY-SA 3.0
2013-05-04T06:52:59.477Z
@MCH: That was fast :) Maybe you should update your answer rather than append a comment to it?
J.y B.y
CC BY-SA 3.0
2013-03-20T15:30:35.790Z
2013-03-20T17:09:10.983Z
2013-03-20T17:09:10.983Z
Mahdi Cheraghchi
<p>In channel coding, it is known (e.g. <a href="http://people.lids.mit.edu/yp/homepage/data/thesis.pdf" rel="nofollow">Yury Polyanskiy's thesis</a>, and the arxiv article <a href="http://arxiv.org/abs/1212.3689" rel="nofollow">A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels</a>) that certain codes, for example polar codes, can reach the Shannon limit for large enough block lengths $n$. However, for finite $n$, the best theoretically possible codes are known to satisfy</p>

<p>$$\log M \leq n C - \sqrt{n V}\, \Phi^{-1}(1-ε) + \frac{1}{2} \log n + O(1),$$</p>

<p>where $M$ is the size of the code, $C$ the capacity of the channel, $V$ the dispersion of the channel, and $ε$ the required (average or maximum) error.</p>

<p>Is it known how Polar codes (or any other codes) compare to this fundamental bound? The bound can be achieved using random codes, but I was wondering if there are any efficient codes that come close.</p>

CC BY-SA 3.0
2013-03-28T09:30:08.873Z
Could you give references for each statement "it is known"? This way your question could, in addition to reach specialists of the field, also teach something to non-specialists of the field finding your question through search engines.
J.y B.y
CC BY-SA 3.0
2013-05-04T03:00:12.453Z
Thanks, @Jeremy. The reference for the fact that polar codes reach capacity is given in the comments of the answer below. A good reference for the bound on the logarithm of the code size is Yuri Polyanskiy's PhD thesis, which he provides on his [homepage](http://people.lids.mit.edu/yp/homepage/). We also did some work on this, showing that the logarithmic term does not exceed $\frac{1}{2} \log n$ for arbitrary discrete memoryless channels. This is on the [arxiv](http://arxiv.org/abs/1212.3689).
Marco Tomamichel
CC BY-SA 3.0
2013-05-04T06:53:34.587Z
Thanks! I added the links in the question for better clarity.
J.y B.y
<it.information-theory>
Can Polar Codes (or any other efficient codes) reach the second order capacity?
Marco Tomamichel
# Can Polar Codes (or any other efficient codes) reach the second order capacity?

(Asked by: username_0 on 2013-03-20)

In channel coding, it is known (e.g. [Yury Polyanskiy's thesis](http://people.lids.mit.edu/yp/homepage/data/thesis.pdf), and the arxiv article [A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels](http://arxiv.org/abs/1212.3689)) that certain codes, for example polar codes, can reach the Shannon limit for large enough block lengths $n$. However, for finite $n$, the best theoretically possible codes are known to satisfy

$$\log M \leq n C - \sqrt{n V}\, \Phi^{-1}(1-ε) + \frac{1}{2} \log n + O(1),$$

where $M$ is the size of the code, $C$ the capacity of the channel, $V$ the dispersion of the channel, and $ε$ the required (average or maximum) error.

Is it known how Polar codes (or any other codes) compare to this fundamental bound? The bound can be achieved using random codes, but I was wondering if there are any efficient codes that come close.

**Tags:** it.information-theory
> **Comments:**
> **username_1**: Could you give references for each statement "it is known"? This way your question could, in addition to reach specialists of the field, also teach something to non-specialists of the field finding your question through search engines.  
> **username_0**: Thanks, @Jeremy. The reference for the fact that polar codes reach capacity is given in the comments of the answer below. A good reference for the bound on the logarithm of the code size is Yuri Polyanskiy's PhD thesis, which he provides on his [homepage](http://people.lids.mit.edu/yp/homepage/). We also did some work on this, showing that the logarithmic term does not exceed $\frac{1}{2} \log n$ for arbitrary discrete memoryless channels. This is on the [arxiv](http://arxiv.org/abs/1212.3689).  
> **username_1**: Thanks! I added the links in the question for better clarity.  

---

## 1 answers

### Answer by username_2 on 2013-03-20. Score: 7 | Accepted answer

As far as I know, people conjecture that for Polar codes and any fixed DMBSC (discrete memoryless binary symmetric channel), $\log M \leq nC - O(n^{1-c})$ for some absolute constant $c > 0$ and vanishing error probability should be possible (or in other words, in order to be $\epsilon$ close to capacity, only a polynomially large $n$ in $1/\epsilon$ would suffice. However, there is no rigorous published proof available at this point. There are rumors about an upcoming proof, but that's not official yet.

> **Comments:**
> **username_0**: Thanks a lot. So do I assume correctly that for other families of codes even less is known?  
> **username_2**: In terms of provable finite length guarantees for general memoryless channels, yes. Except for Forney/Justesen's concatenated codes which are capacity achieving but are known to require $n = exp(1/\epsilon)$ to be $\epsilon$-close to capacity.  
> **username_2**: *Update*. The rumored result "Polar Codes: Speed of polarization and polynomial gap to capacity" by Guruswami and Xia is now available, which hopefully answers your question: http://eccc.hpi-web.de/report/2013/050/  
> **username_1**: @MCH: That was fast :) Maybe you should update your answer rather than append a comment to it?  

---

