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.

Improve this question
$\endgroup$
3
  • $\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$
    – J..y B..y
    Mar 28, 2013 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, 2013 at 3:00
  • $\begingroup$ Thanks! I added the links in the question for better clarity. $\endgroup$
    – J..y B..y
    May 4, 2013 at 6:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks a lot. So do I assume correctly that for other families of codes even less is known? $\endgroup$
    – Marco Tomamichel
    Mar 21, 2013 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, 2013 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, 2013 at 2:17
  • $\begingroup$ @MCH: That was fast :) Maybe you should update your answer rather than append a comment to it? $\endgroup$
    – J..y B..y
    May 4, 2013 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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