Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1205.2876

Universal Bounds on the Scaling Behavior of Polar Codes

Ali Goli, Hamed Hassani, Rudiger L. Urbanke

Published May 13, 2012• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1205.2876

Related papers

Universal bounds on the scaling behavior of polar codes

Ali Goli, Hamed Hassani, Rudiger L. Urbanke

We consider the problem of determining the tradeoff 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-1/μ, where α is a positive constant and N is the block-length. We provide lower bounds on μ, namely μ ≥ 3.553, and we conjecture that indeed μ = 3.627, the parameter for the binary erasure channel.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•29 citations

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.4778•IEEE Transactions on Information Theory•Jul 25, 2014•108 citations

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.

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

Finite-length scaling of 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. 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)$ as $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$.

•Aug 18, 2016•130 citations

An empirical scaling law for polar codes

Satish Babu Korada, Andrea Montanari A, Emre Telatar +1 more

Using scaling laws, we obtain estimates of the block error probability of polar codes under successive cancellation decoding. For the binary erasure channel we present an upper and a lower bound for the scaling parameter. Numerically these two bounds match. We also present a scaling law for general binary discrete memoryless channels.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•62 citations

Scaling Exponent of List Decoders with Applications to Polar Codes

Marco Mondelli, Hamed Hassani, Rudiger L. Urbanke

Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed and the trade-off between block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under $\rm MAP$ decoding with list size $L$ for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under $\rm MAP$ decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.

arXiv:1304.5220•Apr 18, 2013•3 citations
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 WWW with capacity I(W)I(W)I(W), reliable communication requires rates that satisfy R<I(W)−αN−1μR< I(W)-αN^{-\frac{1}μ}R<I(W)−αN−μ1​, where ααα is a positive constant and NNN is the block-length. We provide lower bounds on μμμ, namely μ≥3.553μ\geq 3.553μ≥3.553, and we conjecture that indeed μ=3.627μ=3.627μ=3.627, the parameter for the binary erasure channel.
We consider the problem of determining the tradeoff 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-1/μ, where α is a positive constant and N is the block-length. We provide lower bounds on μ, namely μ ≥ 3.553, and we conjecture that indeed μ = 3.627, the parameter for the binary erasure channel.
Consider a binary-input memoryless output-symmetric channelWWW. Such a channel has a capacity, call itI(W)I(W)I(W), and for anyR<I(W)R<I(W)R<I(W)and strictly positive constantPeP_{\rm e}Pe​we know that we can construct a coding scheme that allows transmission at rateRRRwith an error probability not exceedingPeP_{\rm e}Pe​. Assume now that we let the rateRRRtend toI(W)I(W)I(W)and we ask how we have to scale the blocklengthNNNin order to keep the error probability fixed toPeP_{\rm e}Pe​. 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 thatNNNmust grow at least as the square of the reciprocal ofI(W)−RI(W)-RI(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][a,b][a,b]. Mathematically, this can be stated as bounding the sequence{1/nlog⁡Pr(Zn ⁣∈ ⁣[a,b])}n∈N\bigl \{{1}/{n} \log {\rm {Pr}}(Z_{n} \!\in \! [a,b])\bigr \}_{n \in \mathbb {N}}{1/nlogPr(Zn​∈[a,b])}n∈N​, whereZnZ_{n}Zn​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 valuePe>0P_{\rm e}>0Pe​>0, then the required block-lengthNNNscales in terms of the rateR<I(W)R < I(W)R<I(W)asN≥α/(I(W)−R)μ‾N \geq {\alpha }/{(I(W)-R)^{\underline {\mu }}}N≥α/(I(W)−R)μ​, whereα\alpha αis a positive constant that depends onPeP_{\rm e}Pe​andI(W)I(W)I(W). We show thatμ‾=3.579\underline {\mu } = 3.579μ​=3.579is a valid choice, and we conjecture that indeed the value ofμ‾\underline {\mu }μ​can be improved toμ‾=3.627\underline {\mu }=3.627μ​=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)μ‾N \leq {\beta }/{(I(W)-R)^{\overline {\mu }}}N≤β/(I(W)−R)μ​, whereβ\beta βis a constant that depends onPeP_{\rm e}Pe​andI(W)I(W)I(W), andμ‾=6\overline {\mu }=6μ​=6.
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 a binary-input memoryless output-symmetric channel WWW. Such a channel has a capacity, call it I(W)I(W)I(W), and for any R<I(W)R<I(W)R<I(W) and strictly positive constant PeP_{\rm e}Pe​ we know that we can construct a coding scheme that allows transmission at rate RRR with an error probability not exceeding PeP_{\rm e}Pe​. Assume now that we let the rate RRR tend to I(W)I(W)I(W) and we ask how we have to "scale" the blocklength NNN in order to keep the error probability fixed to PeP_{\rm e}Pe​. 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 NNN must grow at least as the square of the reciprocal of I(W)−RI(W)-RI(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 Pe>0P_{\rm e}>0Pe​>0, then the required block-length NNN scales in terms of the rate R<I(W)R < I(W)R<I(W) as N≥α(I(W)−R)μ‾N \geq \frac{\alpha}{(I(W)-R)^{\underline{\mu}}}N≥(I(W)−R)μ​α​, where α\alphaα is a positive constant that depends on PeP_{\rm e}Pe​ and I(W)I(W)I(W), and μ‾=3.579\underline{\mu} = 3.579μ​=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≤β(I(W)−R)μ‾N \leq \frac{\beta}{(I(W)-R)^{\overline{\mu}}}N≤(I(W)−R)μ​β​, where β\betaβ is a constant that depends on PeP_{\rm e}Pe​ and I(W)I(W)I(W), and μ‾=6\overline{\mu}=6μ​=6.
Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed and the trade-off between block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP\rm MAPMAP decoding with list size LLL for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP\rm MAPMAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open.