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

We consider the asymptotic behavior of the polarization process for polar codes when the blocklength tends to infinity. In particular, we study the asymptotics of the cumulative distribution P(Z(n) <= z), where Z(n) = Z(W-n) is the Bhattacharyya process, and its dependence on the rate of transmission R. We show that for a BMS channel W, for R < I(W) we have lim(n ->infinity) P(Z(n) <= 2(-2n/2+root nQ-1(RI(W))/2+o(root n))/2) =R and for R < 1 - I(W) we have lim(n ->infinity) P(Z(n) >= 1 - 2(-2n/2+root nQ-1/(R1-I(W))/2+o(root n)) = R, where Q(x) is the probability that a standard normal random variable exceeds x. As a result, if we denote by P-e(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(P-e(SC)(n, R))) scales as n/2 +root n(Q-1)(RI(W))/2 + o(root n). We also prove that the same result holds for the block error probability using the MAP decoder, i. e., for log(-log(P-e(MAP)(n, R))).

Published in:
2010 IEEE International Symposium on Information Theory, 874-878
Presented at:
2010 IEEE International Symposium on Information Theory - ISIT, Austin, TX, USA, 13-18 06 2010

 Record created 2010-08-31, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)