# Can Polar Codes (or any other efficient codes) reach the second order capacity?

In channel coding, it is known (e.g. Yury Polyanskiy's thesis, and the arxiv article A Tight Upper Bound for the Third-Order Asymptotics of Discrete Memoryless Channels) 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.

• 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. Mar 28 '13 at 9:30
• 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. 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. May 4 '13 at 3:00
• Thanks! I added the links in the question for better clarity. May 4 '13 at 6:53

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.
• 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. Mar 21 '13 at 14:51