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)))$.

arXiv commentSubmitted to ISIT 2010

Cited by in corpus (7)

• A Split-Reduced Successive Cancellation List Decoder for Polar Codes
• Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization
• Relaxed Polar Codes
• On the Error Performance of Systematic Polar Codes
• Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices
• Improved Bounds on the Finite Length Scaling of Polar Codes
• On Finite-Length Performance of Polar Codes: Stopping Sets, Error Floor, and Concatenated Design