On the scaling of Polar codes: I. The behavior of polarized channels

preprint2010arXivOpen access

Abstract

We consider the asymptotic behavior of the polarization process for polar codes when the blocklength tends to infinity. In particular, we study the problem of asymptotic analysis of the cumulative distribution P(Zn≤z)\mathbb{P}(Z_n \leq z), where Zn=Z(Wn)Z_n=Z(W_n) is the Bhattacharyya process, and its dependence to the rate of transmission R. We show that for a BMS channel WW, for R<I(W)R < I(W) we have lim⁡n→∞P(Zn≤2−2n2+nQ−1(RI(W))2+o(n))=R\lim_{n \to \infty} \mathbb{P} (Z_n \leq 2^{-2^{\frac{n}{2}+\sqrt{n} \frac{Q^{-1}(\frac{R}{I(W)})}{2} +o(\sqrt{n})}}) = R and for R<1−I(W)R<1- I(W) we have lim⁡n→∞P(Zn≥1−2−2n2+nQ−1(R1−I(W))2+o(n))=R\lim_{n \to \infty} \mathbb{P} (Z_n \geq 1-2^{-2^{\frac{n}{2}+ \sqrt{n} \frac{Q^{-1}(\frac{R}{1-I(W)})}{2} +o(\sqrt{n})}}) = R, where Q(x)Q(x) is the probability that a standard normal random variable will obtain a value larger than xx. As a result, if we denote by PeSC(n,R)\mathbb{P}_e ^{\text{SC}}(n,R) the probability of error using polar codes of block-length N=2nN=2^n and rate R<I(W)R<I(W) under successive cancellation decoding, then log⁡(−log⁡(PeSC(n,R)))\log(-\log(\mathbb{P}_e ^{\text{SC}}(n,R))) scales as n2+nQ−1(RI(W))2+o(n)\frac{n}{2}+\sqrt{n}\frac{Q^{-1}(\frac{R}{I(W)})}{2}+ o(\sqrt{n}). We also prove that the same result holds for the block error probability using the MAP decoder, i.e., for log⁡(−log⁡(PeMAP(n,R)))\log(-\log(\mathbb{P}_e ^{\text{MAP}}(n,R))).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.