7
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot. So do I assume correctly that for other families of codes even less is known? $\endgroup$ – Marco Tomamichel Mar 21 '13 at 2:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Mahdi Cheraghchi Mar 21 '13 at 14:51
  • 3
    $\begingroup$ 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: eccc.hpi-web.de/report/2013/050 $\endgroup$ – Mahdi Cheraghchi Apr 12 '13 at 2:17
  • $\begingroup$ @MCH: That was fast :) Maybe you should update your answer rather than append a comment to it? $\endgroup$ – Jeremy May 4 '13 at 6:52

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.