A rigorous derivation of the scaling exponent for polar codes over BSC(p) utilizing martingale convergence rates and non-asymptotic bounds on the Bhattacharyya process.
Consider a binary-input memoryless output-symmetric channelW. Such a channel has a capacity, call itI(W), and for anyR<I(W)and strictly positive constantPewe know that we can construct a coding scheme that allows transmission at rateRwith an error probability not exceedingPe. Assume now that we let the rateRtend toI(W)and we ask how we have to scale the blocklengthNin order to keep the error probability fixed toPe. We refer to this as the finite-length scaling behavior. This question was addressed by Strassen as well as Polyanskiy, Poor, and Verdu, and the result is thatNmust grow at least as the square of the reciprocal ofI(W)−R. Polar codes are optimal in the sense that they achieve capacity. In this paper, we are asking to what degree they are also optimal in terms of their finite-length behavior. Since the exact scaling behavior depends on the choice of the channel, our objective is to provide scaling laws that hold universally for all binary-input memoryless output-symmetric channels. Our approach is based on analyzing the dynamics of the un-polarized channels. More precisely, we provide bounds on (the exponent of) the number of subchannels whose Bhattacharyya constant falls in a fixed interval[a,b]. Mathematically, this can be stated as bounding the sequence{1/nlogPr(Zn∈[a,b])}n∈N, whereZnis the Bhattacharyya process. We then use these bounds to derive tradeoffs between the rate and the block-length. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of subchannels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given valuePe>0, then the required block-lengthNscales in terms of the rateR<I(W)asN≥α/(I(W)−R)μ, whereαis a positive constant that depends onPeandI(W). We show thatμ=3.579is a valid choice, and we conjecture that indeed the value ofμcan be improved toμ=3.627, the parameter for the binary erasure channel. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate likeN≤β/(I(W)−R)μ, whereβis a constant that depends onPeandI(W), andμ=6.
We provide upper and lower bounds on the escape rate of the Bhattacharyya process corresponding to polar codes where transmission takes place over the the binary erasure channel. More precisely, we bound the exponent of the number of sub-channels whose Bhattacharyya constant falls in a fixed interval [a, b]. Mathematically this can be stated as bounding the limit limn→∞1/n ln P(Zn∈ [a, b]), where Znis the Bhattacharyya process. The quantity P(Zn∈ [a, b]) represents the fraction of sub-channels that are still un-polarized at time n.
Consider the transmission of a polar code of block length N and rate R over a binary memoryless symmetric channel W and let Pebe the block error probability under successive cancellation decoding. In this paper, we develop new bounds that characterize the relationship of the parameters R, N, Pe, and the quality of the channel W quantified by its capacity I(W) and its Bhattacharyya parameter Z(W). In previous work, two main regimes were studied. In the error exponent regime, the channel W and the rate R-√N. In the scaling exponent approach, the channel W and the error probability Pe are fixed and it was proved that the gap to capacity I(W) - R scales as N-1/μ. Here, μ is called scaling exponent and this scaling exponent depends on the channel W. A heuristic computation for the binary erasure channel (BEC) gives μ = 3.627 and it was shown that, for any channel W, 3.579 ≤ μ ≤ 5.702. Our contributions are as follows. First, we provide the tighter upper bound μ <;≤ 4.714 valid for any W. With the same technique, we obtain the upper bound μ ≤ 3.639 for the case of the BEC; this upper bound approaches very closely the heuristically derived value for the scaling exponent of the erasure channel. Second, we develop a trade-off between the gap to capacity I(W)- R and the error probability Pe as the functions of the block length N. In other words, we neither fix the gap to capacity (error exponent regime) nor the error probability (scaling exponent regime), but we do consider a moderate deviations regime in which we study how fast both quantities, as the functions of the block length N, simultaneously go to 0. Third, 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. Then, we vary the channel W and study the impact of this variation on the error probability. We show that the error probability Pe scales as the Bhattacharyya parameter Z(W) raised to a power that scales roughly like VN. This agrees with the scaling in the error exponent regime.
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), where Zn=Z(Wn) 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 limn→∞P(Zn≤2−22n+n2Q−1(I(W)R)+o(n))=R and for R<1−I(W) we have limn→∞P(Zn≥1−2−22n+n2Q−1(1−I(W)R)+o(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 PeSC(n,R) the probability of error using polar codes of block-length N=2n and rate $R
A general framework is proposed that includes polar codes over arbitrary channels with arbitrary kernels. The asymptotic tradeoff among block length N, code rate R, and error probability P is analyzed. Given a tradeoff between N,P and a tradeoff between N,R, we return an interpolating tradeoff among N,R,P (Theorem 5). Quantitatively, if P=exp(−Nβ∗) is possible for some β∗ and if $R=\Capacity-N^{1/μ^*}$ is possible for some 1/μ∗, then $(P,R)=(\exp(-N^{β'}),\Capacity-N^{-1/μ'})$ is possible for some pair (β′,1/μ′) determined by β∗, 1/μ∗, and auxiliary information. In fancy words, an error exponent regime tradeoff plus a scaling exponent regime tradeoff implies a moderate deviations regime tradeoff. The current world records are: [arXiv:1304.4321][arXiv:1501.02444][arXiv:1806.02405] analyzing Arıkan's codes over BEC; [arXiv:1706.02458] analyzing Arıkan's codes over AWGN; and [arXiv:1802.02718][arXiv:1810.04298] analyzing general codes over general channels. An attempt is made to generalize all at once (Section IX). As a corollary, a grafted variant of polar coding almost catches up the code rate and error probability of random codes with complexity slightly larger than NlogN over BEC. In particular, $(P,R)=(\exp(-N^{.33}),\Capacity-N^{-.33})$ is possible (Corollary 10). In fact, all points in this triangle are possible (β′,1/μ′)-pairs. $$ \require{enclose} \def\r{\phantom{\Rule{4em}{1em}{1em}}} \enclose{}\r^\llap{(0,1/2)}_\llap{(0,0)} \enclose{left,bottom,downdiagonalstrike}\r_\rlap{(1,0)} \enclose{}\r $$
Polar codes approach channel capacity provably and empirically and are thereby a constituent code of the 5G standard. Compared to low-density parity-check codes, however, the performance of short-length polar codes have rooms for improvement that could hinder its adoption by a wider class of applications. As part of the program that addresses the performance issue at short length, it is crucial to understand how fast binary memoryless symmetric channels polarize. A number, called scaling exponent, was defined to measure the speed of polarization and several estimates of the scaling exponent were given in literature. As of 2022, the tightest overestimate is 4.714 made by Mondelli, Hassani, and Urbanke in 2015. We lower the overestimate to 4.63. The idea behind this improvement is that, instead of describing the relation between a channelWand its childrenW⋆andW◯⋆, we describe the relation betweenWand its grandchildren$ {W}^{\scriptscriptstyle {\boxed {\star}} \, {\scriptscriptstyle {\boxed {\star}}} },{W}^{\scriptscriptstyle {\boxed {\star}}\, {{\bigcirc \!\! \star} }},{W}^{{\bigcirc \!\!\! \star}\,\,{\scriptscriptstyle {\boxed {\star}}} },and {W}^{{\bigcirc \!\!\! \star}\,{\bigcirc \!\!\! \star} }$. By doing so, the evolution of channels becomes “less Markovian” and hence more tighter inequalities can be obtained.