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:1812.08112

Polar-like Codes and Asymptotic Tradeoff among Block Length, Code Rate, and Error Probability

Hsin-Po Wang, Iwan Duursma

Published Dec 19, 2018• 5 citations
arXivHTMLPDF

Abstract

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). $\def\Capacity{\text{Capacity}}$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 $N\log N$ 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 $$

DOI
10.48550/arxiv.1812.08112

Related papers

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 Transactions on Information Theory•Jun 1, 2015•134 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•116 citations

Polar Codes’ Simplicity, Random Codes’ Durability

Hsin-Po Wang, Iwan Duursma

Over any discrete memoryless channel, we offer error correction codes such that: for one, their block error probabilities and code rates scale like random codes'; and for two, their encoding and decoding complexities scale like polar codes'. Quantitatively, for any constants π, ρ > 0 π +2ρπ) , code rate N-ρless than the Shannon capacity, and encoding and decoding complexity O(N log N}) per code block. The core theme is to incorporate polar coding (which limits the complexity to polar's realm) with large, random, dynamic kernels (which boosts the performance to random's realm). The putative codes are optimal in the following manner: Should π +2ρ>1 , no such codes exist over generic channels regardless of complexity.

arXiv:1912.08995•IEEE Transactions on Information Theory•Dec 1, 2020•18 citations

Explicit Polar Codes with Small Scaling Exponent

Hanwen Yao, Arman Fazeli, Alexander Vardy

Polar coding gives rise to the first explicit family of codes that provably achieve capacity for a wide range of channels with efficient encoding and decoding. But how fast can polar coding approach capacity as a function of the code length? In finite-length analysis, the scaling between code length and the gap to capacity is usually measured in terms of the scaling exponent μ. It is well known that the optimal scaling exponent, achieved by random binary codes, is μ = 2. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is μ = 3.627, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from ℓ × ℓ binary polarization kernels approach the optimal scaling exponent μ = 2 on the BEC as ℓ→∞, with high probability over a random choice of the kernel. Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ ≤ 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent μℓtransforms an underlying BEC into ℓ bit-channels W1, W2>,..., Wℓ. The erasure probabilities of W1, W2>,..., Wℓ, known as the polarization behavior of Kℓ, determine the resulting scaling exponent μ(Kℓ). We first introduce a class of self-dual binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing Kℓto that of producing a certain nested chain of only ℓ/2 self-orthogonal codes. We use nested cyclic codes, whose distance is as high as possible subject to the orthogonality constraint, to construct the kernels K32and K64. In order to evaluate the polarization behavior of K32and K64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that μ(K32) = 3.122 and explicitly compute over half of the polarization-behavior coefficients for K64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate μ(K64) ≃ 2.87. We augment this estimate with a rigorous proof that μ(K64) <; 2.97.

arXiv:1901.08186•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•29 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 $R

arXiv:1001.2766•Jan 15, 2010•21 citations

Capacity-Achieving Rate-Compatible Polar Codes for General Channels

Marco Mondelli, Hamed Hassani, Ivana Marić +2 more

We present a rate-compatible polar coding scheme that achieves the capacity of any family of channels. Our solution generalizes the previous results [1], [2] that provide capacity-achieving rate-compatible polar codes for a degraded family of channels. The motivation for our extension comes from the fact that in many practical scenarios, e.g., MIMO systems and non-Gaussian interference, the channels cannot be ordered by degradation. The main technical contribution of this paper consists in removing the degradation condition. To do so, we exploit the ideas coming from the construction of universal polar codes. Our scheme possesses the usual attractive features of polar codes: low complexity code construction, encoding, and decoding; super-polynomial scaling of the error probability with the block length; and absence of error floors. On the negative side, the scaling of the gap to capacity with the block length is slower than in standard polar codes, and we prove an upper bound on the scaling exponent.

arXiv:1611.01199•IEEE Wireless Communications and Networking Conference Workshops (WCNCW)•Mar 1, 2017•11 citations
A general framework is proposed that includes polar codes over arbitrary channels with arbitrary kernels. The asymptotic tradeoff among block length NNN, code rate RRR, and error probability PPP is analyzed. Given a tradeoff between N,PN,PN,P and a tradeoff between N,RN,RN,R, we return an interpolating tradeoff among N,R,PN,R,PN,R,P (Theorem 5). \def\Capacity{\text{Capacity}}Quantitatively, if P=exp⁡(−Nβ∗)P=\exp(-N^{β^*})P=exp(−Nβ∗) is possible for some β∗β^*β∗ and if R=\Capacity−N1/μ∗R=\Capacity-N^{1/μ^*}R=\Capacity−N1/μ∗ is possible for some 1/μ∗1/μ^*1/μ∗, then (P,R)=(exp⁡(−Nβ′),\Capacity−N−1/μ′)(P,R)=(\exp(-N^{β'}),\Capacity-N^{-1/μ'})(P,R)=(exp(−Nβ′),\Capacity−N−1/μ′) is possible for some pair (β′,1/μ′)(β',1/μ')(β′,1/μ′) determined by β∗β^*β∗, 1/μ∗1/μ^*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 Nlog⁡NN\log NNlogN over BEC. In particular, (P,R)=(exp⁡(−N.33),\Capacity−N−.33)(P,R)=(\exp(-N^{.33}),\Capacity-N^{-.33})(P,R)=(exp(−N.33),\Capacity−N−.33) is possible (Corollary 10). In fact, all points in this triangle are possible (β′,1/μ′)(β',1/μ')(β′,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
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 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.
Over any discrete memoryless channel, we offer error correction codes such that: for one, their block error probabilities and code rates scale like random codes'; and for two, their encoding and decoding complexities scale like polar codes'. Quantitatively, for any constants π, ρ > 0 π +2ρπ) , code rate N-ρless than the Shannon capacity, and encoding and decoding complexity O(N log N}) per code block. The core theme is to incorporate polar coding (which limits the complexity to polar's realm) with large, random, dynamic kernels (which boosts the performance to random's realm). The putative codes are optimal in the following manner: Should π +2ρ>1 , no such codes exist over generic channels regardless of complexity.
Polar coding gives rise to the first explicit family of codes that provably achieve capacity for a wide range of channels with efficient encoding and decoding. But how fast can polar coding approach capacity as a function of the code length? In finite-length analysis, the scaling between code length and the gap to capacity is usually measured in terms of the scaling exponent μ. It is well known that the optimal scaling exponent, achieved by random binary codes, is μ = 2. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is μ = 3.627, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from ℓ × ℓ binary polarization kernels approach the optimal scaling exponent μ = 2 on the BEC as ℓ→∞, with high probability over a random choice of the kernel. Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ ≤ 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent μℓtransforms an underlying BEC into ℓ bit-channels W1, W2>,..., Wℓ. The erasure probabilities of W1, W2>,..., Wℓ, known as the polarization behavior of Kℓ, determine the resulting scaling exponent μ(Kℓ). We first introduce a class of self-dual binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing Kℓto that of producing a certain nested chain of only ℓ/2 self-orthogonal codes. We use nested cyclic codes, whose distance is as high as possible subject to the orthogonality constraint, to construct the kernels K32and K64. In order to evaluate the polarization behavior of K32and K64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that μ(K32) = 3.122 and explicitly compute over half of the polarization-behavior coefficients for K64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate μ(K64) ≃ 2.87. We augment this estimate with a rigorous proof that μ(K64) <; 2.97.
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)\mathbb{P}(Z_n \leq z)P(Zn​≤z), where Zn=Z(Wn)Z_n=Z(W_n)Zn​=Z(Wn​) is the Bhattacharyya process, and its dependence to the rate of transmission R. We show that for a BMS channel WWW, for R<I(W)R < I(W)R<I(W) we have lim⁡n→∞P(Zn≤2−2n2+nQ−1(RI(W))2+o(n))=R\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})}}) = Rlimn→∞​P(Zn​≤2−22n​+n​2Q−1(I(W)R​)​+o(n​))=R and for R<1−I(W)R<1- I(W)R<1−I(W) we have lim⁡n→∞P(Zn≥1−2−2n2+nQ−1(R1−I(W))2+o(n))=R\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})}}) = Rlimn→∞​P(Zn​≥1−2−22n​+n​2Q−1(1−I(W)R​)​+o(n​))=R, where Q(x)Q(x)Q(x) is the probability that a standard normal random variable will obtain a value larger than xxx. As a result, if we denote by PeSC(n,R)\mathbb{P}_e ^{\text{SC}}(n,R)PeSC​(n,R) the probability of error using polar codes of block-length N=2nN=2^nN=2n and rate $R
We present a rate-compatible polar coding scheme that achieves the capacity of any family of channels. Our solution generalizes the previous results [1], [2] that provide capacity-achieving rate-compatible polar codes for a degraded family of channels. The motivation for our extension comes from the fact that in many practical scenarios, e.g., MIMO systems and non-Gaussian interference, the channels cannot be ordered by degradation. The main technical contribution of this paper consists in removing the degradation condition. To do so, we exploit the ideas coming from the construction of universal polar codes. Our scheme possesses the usual attractive features of polar codes: low complexity code construction, encoding, and decoding; super-polynomial scaling of the error probability with the block length; and absence of error floors. On the negative side, the scaling of the gap to capacity with the block length is slower than in standard polar codes, and we prove an upper bound on the scaling exponent.