Everything You Always Wanted to Know About Scaling of Polar Codes (But Were Afraid to Ask)

Consider transmission of a polar code of block length N and rate R over a binary memoryless symmetric channel W with capacity I(W) and Bhattacharyya parameter Z(W) and let $P_e$ be the error probability under successive cancellation decoding. Recall that in the error exponent regime, the channel W and R<I(W) are fixed, while $P_e$ scales roughly as $2^{-\sqrt{N}}$. In the scaling exponent regime, the channel W and $P_e$ are fixed, while the gap to capacity I(W)-R scales as $N^{-1/\mu}$, with $3.579 \le \mu \le 5.702$ for any W.

We develop a unified framework to characterize the relationship between R, N, $P_e$, and W. First, we provide the tighter upper bound $\mu \le 4.714$, valid for any W. Furthermore, when W is a binary erasure channel, we obtain an upper bound approaching very closely the value which was previously derived in a heuristic manner. Secondly, we consider a moderate deviations regime and we study how fast both the gap to capacity I(W)-R and the error probability $P_e$ simultaneously go to 0 as N goes large. Thirdly, we prove that polar codes are not affected by error floors. To do so, we fix a polar code of block length N and rate R, we let the channel W vary, and we show that $P_e$ scales roughly as $Z(W)^{\sqrt{N}}$.

Joint work with S. Hamed Hassani and Ruediger Urbanke. [http://arxiv.org/abs/1501.02444]