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:1912.08995 · IEEE Transactions on Information Theory

Polar Codes’ Simplicity, Random Codes’ Durability

Hsin-Po Wang, Iwan Duursma

Published Dec 1, 2020• 17 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2020.3041570

Related papers

Log-Logarithmic Time Pruned Polar Coding

Hsin-Po Wang, Iwan Duursma

A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.

arXiv:1905.13340•IEEE Transactions on Information Theory•Dec 1, 2020•9 citations

Polar Codes: Finite Length Implementation, Error Correlations and Multilevel Modulation

Mani Bastani Parizi

Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.

•Jan 1, 2012•4 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

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

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

Hsin-Po Wang, Iwan Duursma

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

arXiv:1812.08112•Dec 19, 2018•4 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.

arXiv:2501.13092•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation
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.
A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.
Shannon, in his seminal work, formalized the transmission of data over a communication channel and determined its fundamental limits. He characterized the relation between communication rate and error probability and showed that as long as the communication rate is below the capacity of the channel, error probability can be made as small as desirable by using appropriate coding over the communication channel and letting the codeword length approach infinity. He provided the formula for capacity of discrete memoryless channel. However, his proposed coding scheme was too complex to be practical in communication systems. Polar codes, recently introduced by Arikan, are the first practical codes that are known to achieve the capacity for a large class of channel and have low encoding and decoding complexity. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length as it goes to infinity. However, it is interesting to investigate their performance in finite length as this is the case in all practical communication schemes. In this dissertation, after a brief overview on polar codes, we introduce a practical framework for simulation of error correcting codes in general. We introduce the importance sampling concept to efficiently evaluate the performance of polar codes with finite bock length. Next, based on simulation results, we investigate the performance of different genie aided decoders to mitigate the poor performance of polar codes in low to moderate block length and propose single-error correction methods to improve the performance dramatically in expense of complexity of decoder. In this context, we also study the correlation between error events in a successive cancellation decoder. Finally, we investigate the performance of polar codes in non-binary channels. We compare the code construction of Sasoglu for Q-ary channels and classical multilevel codes. We construct multilevel polar codes for Q-ary channels and provide a thorough comparison of complexity and performance of two methods in finite length.
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.
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.
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-N^{1/μ^*}$ is possible for some 1/μ∗1/μ^*1/μ∗, then $(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})$ 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 $$
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 timeO(N1.585)\mathcal{O}\left(N^{1.585}\right)O(N1.585), whereNNNis the codeword length. This implies a code construction algorithm with the above complexity. For the asymptotic case, we develop two rate thresholds, denotedRL=RL(λ)R_{\mathrm{L}}=R_{\mathrm{L}}(\lambda)RL​=RL​(λ)andRU=RU(λ)R_{\mathrm{U}}=R_{\mathrm{U}}(\lambda)RU​=RU​(λ), whereλ(⋅)\lambda(\cdot)λ(⋅)is the labeler of the channel outputs (essentially, a quantizer). For any0<β<120<\beta<\frac{1}{2}0<β<21​and any code rateR<RLR<R_{\mathrm{L}}R<RL​, there exists a family of polar codes with growing lengths such that their rates are at leastRRRand their error probabilities are at most2−Nβ2^{-N^{\beta}}2−Nβ. That is, strong polarization continues to hold under the min-sum approximation. Conversely, for code rates exceedingRUR_{\mathrm{U}}RU​, the error probability approaches 1 as the code-length increases, irrespective of which bits are frozen. We show that0<RL≤RU≤C0<R_{\mathrm{L}} \leq R_{\mathrm{U}} \leq C0<RL​≤RU​≤C, whereCCCis 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.