Finite-length scaling of polar codes

Hamed Hassani, Kasra Alishahi, Rudiger L. Urbanke

Published Aug 18, 2016• 130 citations

Abstract

Related papers

Finite-Length Scaling for Polar Codes

Hamed Hassani, Kasra Alishahi, Rudiger L. Urbanke

Consider a binary-input memoryless output-symmetric channel$W$. Such a channel has a capacity, call it$I(W)$, and for any$R<I(W)$and strictly positive constant$P_{\rm e}$we know that we can construct a coding scheme that allows transmission at rate$R$with an error probability not exceeding$P_{\rm e}$. Assume now that we let the rate$R$tend to$I(W)$and we ask how we have to scale the blocklength$N$in order to keep the error probability fixed to$P_{\rm e}$. 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 that$N$must grow at least as the square of the reciprocal of$I(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$\bigl \{{1}/{n} \log {\rm {Pr}}(Z_{n} \!\in \! [a,b])\bigr \}_{n \in \mathbb {N}}$, where$Z_{n}$is 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 value$P_{\rm e}>0$, then the required block-length$N$scales in terms of the rate$R < I(W)$as$N \geq {\alpha }/{(I(W)-R)^{\underline {\mu }}}$, where$\alpha $is a positive constant that depends on$P_{\rm e}$and$I(W)$. We show that$\underline {\mu } = 3.579$is a valid choice, and we conjecture that indeed the value of$\underline {\mu }$can be improved to$\underline {\mu }=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 like$N \leq {\beta }/{(I(W)-R)^{\overline {\mu }}}$, where$\beta $is a constant that depends on$P_{\rm e}$and$I(W)$, and$\overline {\mu }=6$.

arXiv:1304.4778IEEE Transactions on Information TheoryJul 25, 2014108 citations

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

Hamed Hassani, Rudiger L. Urbanke

arXiv:1001.2766Jan 15, 201019 citations

Universal Bounds on the Scaling Behavior of Polar Codes

Ali Goli, Hamed Hassani, Rudiger L. Urbanke

arXiv:1205.2876May 13, 20123 citations

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

Hamed Hassani, Rudiger L. Urbanke

IEEE International Symposium on Information Theory (ISIT)Jun 1, 201045 citations

An Analytical Study of the Min-Sum Approximation for Polar Codes

Nir Chisnevski, Ido Tal, Shlomo Shitz Shamai

arXiv:2501.13092IEEE International Symposium on Information Theory (ISIT)Jun 22, 20251 citation

Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors

Marco Mondelli, Rudiger L. Urbanke, Hamed Hassani

arXiv:1501.02444IEEE International Symposium on Information Theory (ISIT)Jun 1, 2015127 citations

Finite-length scaling of polar codes

Hamed Hassani, Kasra Alishahi, Rudiger L. Urbanke

Published Aug 18, 2016• 130 citations

OpenAlex

Abstract

Consider a binary-input memoryless output-symmetric channel

W

. Such a channel has a capacity, call it

I(W)

, and for any

R<I(W)

and strictly positive constant

P_{\rm e}

we know that we can construct a coding scheme that allows transmission at rate

R

with an error probability not exceeding

P_{\rm e}

. Assume now that we let the rate

R

tend to

I(W)

and we ask how we have to "scale" the blocklength

N

in order to keep the error probability fixed to

P_{\rm e}

. 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 that

N

must grow at least as the square of the reciprocal of

I(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. Our approach is based on analyzing the dynamics of the un-polarized channels. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of sub-channels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given value

P_{\rm e}>0

, then the required block-length

N

scales in terms of the rate

R < I(W)

N \geq \frac{\alpha}{(I(W)-R)^{\underline{\mu}}}

, where

\alpha

is a positive constant that depends on

P_{\rm e}

and

I(W)

, and

\underline{\mu} = 3.579

. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like

N \leq \frac{\beta}{(I(W)-R)^{\overline{\mu}}}

, where

\beta

is a constant that depends on

P_{\rm e}

and

I(W)

, and

\overline{\mu}=6

Related papers

Finite-Length Scaling for Polar Codes

Hamed Hassani, Kasra Alishahi, Rudiger L. Urbanke

Consider a binary-input memoryless output-symmetric channel $W$ . Such a channel has a capacity, call it $I(W)$ , and for any $R<I(W)$ and strictly positive constant $P_{\rm e}$ we know that we can construct a coding scheme that allows transmission at rate $R$ with an error probability not exceeding $P_{\rm e}$ . Assume now that we let the rate $R$ tend to $I(W)$ and we ask how we have to scale the blocklength $N$ in order to keep the error probability fixed to $P_{\rm e}$ . 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 that $N$ must grow at least as the square of the reciprocal of $I(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 $\bigl \{{1}/{n} \log {\rm {Pr}}(Z_{n} \!\in \! [a,b])\bigr \}_{n \in \mathbb {N}}$ , where $Z_{n}$ is 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 value $P_{\rm e}>0$ , then the required block-length $N$ scales in terms of the rate $R < I(W)$ as $N \geq {\alpha }/{(I(W)-R)^{\underline {\mu }}}$ , where $\alpha$ is a positive constant that depends on $P_{\rm e}$ and $I(W)$ . We show that $\underline {\mu } = 3.579$ is a valid choice, and we conjecture that indeed the value of $\underline {\mu }$ can be improved to $\underline {\mu }=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 like $N \leq {\beta }/{(I(W)-R)^{\overline {\mu }}}$ , where $\beta$ is a constant that depends on $P_{\rm e}$ and $I(W)$ , and $\overline {\mu }=6$ .Consider a binary-input memoryless output-symmetric channel$W$. Such a channel has a capacity, call it$I(W)$, and for any$R<I(W)$and strictly positive constant$P_{\rm e}$we know that we can construct a coding scheme that allows transmission at rate$R$with an error probability not exceeding$P_{\rm e}$. Assume now that we let the rate$R$tend to$I(W)$and we ask how we have to scale the blocklength$N$in order to keep the error probability fixed to$P_{\rm e}$. 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 that$N$must grow at least as the square of the reciprocal of$I(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$\bigl \{{1}/{n} \log {\rm {Pr}}(Z_{n} \!\in \! [a,b])\bigr \}_{n \in \mathbb {N}}$, where$Z_{n}$is 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 value$P_{\rm e}>0$, then the required block-length$N$scales in terms of the rate$R < I(W)$as$N \geq {\alpha }/{(I(W)-R)^{\underline {\mu }}}$, where$\alpha $is a positive constant that depends on$P_{\rm e}$and$I(W)$. We show that$\underline {\mu } = 3.579$is a valid choice, and we conjecture that indeed the value of$\underline {\mu }$can be improved to$\underline {\mu }=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 like$N \leq {\beta }/{(I(W)-R)^{\overline {\mu }}}$, where$\beta $is a constant that depends on$P_{\rm e}$and$I(W)$, and$\overline {\mu }=6$.

arXiv:1304.4778IEEE Transactions on Information TheoryJul 25, 2014108 citations

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

Hamed Hassani, Rudiger L. Urbanke

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 \leq 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 \leq 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 \geq 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 $RWe 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 \leq 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 \leq 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 \geq 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

arXiv:1001.2766Jan 15, 201019 citations

Universal Bounds on the Scaling Behavior of Polar Codes

Ali Goli, Hamed Hassani, Rudiger L. Urbanke

We consider the problem of determining the trade-off between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter $μ$ such that for any binary memoryless symmetric channel $W$ with capacity $I(W)$ , reliable communication requires rates that satisfy $R< I(W)-αN^{-\frac{1}μ}$ , where $α$ is a positive constant and $N$ is the block-length. We provide lower bounds on $μ$ , namely $μ\geq 3.553$ , and we conjecture that indeed $μ=3.627$ , the parameter for the binary erasure channel.We consider the problem of determining the trade-off between the rate and the block-length of polar codes for a given block error probability when we use the successive cancellation decoder. We take the sum of the Bhattacharyya parameters as a proxy for the block error probability, and show that there exists a universal parameter $μ$ such that for any binary memoryless symmetric channel $W$ with capacity $I(W)$, reliable communication requires rates that satisfy $R< I(W)-αN^{-\frac{1}μ}$, where $α$ is a positive constant and $N$ is the block-length. We provide lower bounds on $μ$, namely $μ\geq 3.553$, and we conjecture that indeed $μ=3.627$, the parameter for the binary erasure channel.

arXiv:1205.2876May 13, 20123 citations

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

Hamed Hassani, Rudiger L. Urbanke

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(Zn≤ z), where Zn= Z(Wn) is the Bhattacharyya process, and its dependence on the rate of transmission R. We show that for a BMS channel W, for Rn→8P (Zn≤ 2-2n/2+√n(Q-1(R/I(W)/2)+o(√n))) = R and for Rn→8P (Zn≤ 2-2n/2+√n(Q-1(R/I(W)/2)+o(√n))) = R, where Q(x) is the probability that a standard normal random variable exceeds x. As a result, if we denote by PeSC(n,R) the probability of error using polar codes of block-length N = 2nand rate ReSC(n,R))) scales as n/2+√n(Q-1(R/I(W)/2)+o(√n)). We also prove that the same result holds for the block error probability using the MAP decoder, i.e., for log(-log(PeMAP(n,R))).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(Zn≤ z), where Zn= Z(Wn) is the Bhattacharyya process, and its dependence on the rate of transmission R. We show that for a BMS channel W, for Rn→8P (Zn≤ 2-2n/2+√n(Q-1(R/I(W)/2)+o(√n))) = R and for Rn→8P (Zn≤ 2-2n/2+√n(Q-1(R/I(W)/2)+o(√n))) = R, where Q(x) is the probability that a standard normal random variable exceeds x. As a result, if we denote by PeSC(n,R) the probability of error using polar codes of block-length N = 2nand rate ReSC(n,R))) scales as n/2+√n(Q-1(R/I(W)/2)+o(√n)). We also prove that the same result holds for the block error probability using the MAP decoder, i.e., for log(-log(PeMAP(n,R))).

IEEE International Symposium on Information Theory (ISIT)Jun 1, 201045 citations

An Analytical Study of the Min-Sum Approximation for Polar Codes

Nir Chisnevski, Ido Tal, Shlomo Shitz Shamai

The min-sum approximation is widely used in the decoding of polar codes. Although it is a numerical approximation, hardly any penalties are incurred in practice. We give a theoretical justification for this. We consider the common case of a binary-input, memoryless, and symmetric channel, decoded using successive cancellation and the min-sum approximation. Under mild assumptions, we show the following. For the finite length case, we show how to exactly calculate the error probabilities of all synthetic (bit) channels in time $\mathcal{O}\left(N^{1.585}\right)$ , where $N$ is the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted $R_{\mathrm{L}}=R_{\mathrm{L}}(\lambda)$ and $R_{\mathrm{U}}=R_{\mathrm{U}}(\lambda)$ , where $\lambda(\cdot)$ is the labeler of the channel outputs (essentially, a quantizer). For any $0<\beta<\frac{1}{2}$ and any code rate $R<R_{\mathrm{L}}$ , there exists a family of polar codes with growing lengths such that their rates are at least $R$ and their error probabilities are at most $2^{-N^{\beta}}$ . That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding $R_{\mathrm{U}}$ , the error probability approaches 1 as the code-length increases, irrespective of which bits are frozen. We show that $0<R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C$ , where $C$ is the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity.The min-sum approximation is widely used in the decoding of polar codes. Although it is a numerical approximation, hardly any penalties are incurred in practice. We give a theoretical justification for this. We consider the common case of a binary-input, memoryless, and symmetric channel, decoded using successive cancellation and the min-sum approximation. Under mild assumptions, we show the following. For the finite length case, we show how to exactly calculate the error probabilities of all synthetic (bit) channels in time$\mathcal{O}\left(N^{1.585}\right)$, where$N$is the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted$R_{\mathrm{L}}=R_{\mathrm{L}}(\lambda)$and$R_{\mathrm{U}}=R_{\mathrm{U}}(\lambda)$, where$\lambda(\cdot)$is the labeler of the channel outputs (essentially, a quantizer). For any$0<\beta<\frac{1}{2}$and any code rate$R<R_{\mathrm{L}}$, there exists a family of polar codes with growing lengths such that their rates are at least$R$and their error probabilities are at most$2^{-N^{\beta}}$. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding$R_{\mathrm{U}}$, the error probability approaches 1 as the code-length increases, irrespective of which bits are frozen. We show that$0<R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C$, where$C$is the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity.

arXiv:2501.13092IEEE International Symposium on Information Theory (ISIT)Jun 22, 20251 citation

Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors

Marco Mondelli, Rudiger L. Urbanke, Hamed Hassani

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

arXiv:1501.02444IEEE International Symposium on Information Theory (ISIT)Jun 1, 2015127 citations

Consider a binary-input memoryless output-symmetric channel

W

. Such a channel has a capacity, call it

I(W)

, and for any

R<I(W)

and strictly positive constant

P_{\rm e}

we know that we can construct a coding scheme that allows transmission at rate

R

with an error probability not exceeding

P_{\rm e}

. Assume now that we let the rate

R

tend to

I(W)

and we ask how we have to "scale" the blocklength

N

in order to keep the error probability fixed to

P_{\rm e}

. 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 that

N

must grow at least as the square of the reciprocal of

I(W)-R

P_{\rm e}>0

, then the required block-length

N

scales in terms of the rate

R < I(W)

N \geq \frac{\alpha}{(I(W)-R)^{\underline{\mu}}}

, where

\alpha

is a positive constant that depends on

P_{\rm e}

and

I(W)

, and

\underline{\mu} = 3.579

. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like

N \leq \frac{\beta}{(I(W)-R)^{\overline{\mu}}}

, where

\beta

is a constant that depends on

P_{\rm e}

and

I(W)

, and

\overline{\mu}=6

Consider a binary-input memoryless output-symmetric channel

W

. Such a channel has a capacity, call it

I(W)

, and for any

R<I(W)

and strictly positive constant

P_{\rm e}

we know that we can construct a coding scheme that allows transmission at rate

R

with an error probability not exceeding

P_{\rm e}

. Assume now that we let the rate

R

tend to

I(W)

and we ask how we have to scale the blocklength

N

in order to keep the error probability fixed to

P_{\rm e}

. 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 that

N

must grow at least as the square of the reciprocal of

I(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

\bigl \{{1}/{n} \log {\rm {Pr}}(Z_{n} \!\in \! [a,b])\bigr \}_{n \in \mathbb {N}}

, where

Z_{n}

is 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 value

P_{\rm e}>0

, then the required block-length

N

scales in terms of the rate

R < I(W)

N \geq {\alpha }/{(I(W)-R)^{\underline {\mu }}}

, where

\alpha

is a positive constant that depends on

P_{\rm e}

and

I(W)

. We show that

\underline {\mu } = 3.579

is a valid choice, and we conjecture that indeed the value of

\underline {\mu }

can be improved to

\underline {\mu }=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 like

N \leq {\beta }/{(I(W)-R)^{\overline {\mu }}}

, where

\beta

is a constant that depends on

P_{\rm e}

and

I(W)

, and

\overline {\mu }=6

\mathbb{P}(Z_n \leq 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 \leq 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 \geq 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

μ

such that for any binary memoryless symmetric channel

W

with capacity

I(W)

, reliable communication requires rates that satisfy

R< I(W)-αN^{-\frac{1}μ}

, where

α

is a positive constant and

N

is the block-length. We provide lower bounds on

μ

, namely

μ\geq 3.553

, and we conjecture that indeed

μ=3.627

, the parameter for the binary erasure channel.

\mathcal{O}\left(N^{1.585}\right)

, where

N

is the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denoted

R_{\mathrm{L}}=R_{\mathrm{L}}(\lambda)

and

R_{\mathrm{U}}=R_{\mathrm{U}}(\lambda)

, where

\lambda(\cdot)

is the labeler of the channel outputs (essentially, a quantizer). For any

0<\beta<\frac{1}{2}

and any code rate

R<R_{\mathrm{L}}

, there exists a family of polar codes with growing lengths such that their rates are at least

R

and their error probabilities are at most

2^{-N^{\beta}}

. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceeding

R_{\mathrm{U}}

, the error probability approaches 1 as the code-length increases, irrespective of which bits are frozen. We show that

0<R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C

, where

C

is the channel capacity. The last inequality is often strict, in which case the ramification of using the min-sum approximation is that we can no longer achieve capacity.