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

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 $\mathbb{P}(Z_n\le z)$, where $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 $W$, for $R<I(W)$ we have ${\lim }_{n\to \infty }\mathbb{P}(Z_n\le 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)$ we have ${\lim }_{n\to \infty }\mathbb{P}(Z_n\ge 1-2^{-2^{\frac{n}{2}+\sqrt{n}\frac{Q^{-1}(\frac{R}{1-I(W)})}{2}+o(\sqrt{n})}})=R$, where $Q(x)$ is the probability that a standard normal random variable will obtain a value larger than $x$. As a result, if we denote by ${\mathbb{P}}_e^{\text{SC}}(n,R)$ the probability of error using polar codes of block-length $N=2^n$ and rate $R<I(W)$ under successive cancellation decoding, then $\log (-\log ({\mathbb{P}}_e^{\text{SC}}(n,R)))$ scales as $\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 ({\mathbb{P}}_e^{\text{MAP}}(n,R)))$.

Submitted to ISIT 2010

Cited by in corpus (2)

• On the Error Performance of Systematic Polar Codes
• On Finite-Length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated Design