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

IEEE International Symposium on Information Theory (ISIT)

A lower bound on the probability of error of polar codes over BMS channels

Boaz Shuval, Ido Tal

Published Jun 1, 2017• 7 citations
Publisher

Abstract

Consider a polar code designed for some binary memoryless symmetric channel. We develop a lower bound on the probability of error of this polar code under successive-cancellation decoding. The bound exploits the correlation between the various codeword bits and improves upon existing lower bounds.
DOI
10.1109/isit.2017.8006649

Related papers

A Lower Bound on the Probability of Error of Polar Codes over BMS Channels

Boaz Shuval, Ido Tal

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.

IEEE Transactions on Information Theory•Oct 12, 2018•7 citations

A Lower Bound on the Probability of Error of Polar Codes over BMS Channels

Boaz Shuval, Ido Tal

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit- wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this research we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.

arXiv:1701.01628•Jan 6, 2017•0 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

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.

arXiv:1205.2876•May 13, 2012•3 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

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
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.
Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit- wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this research we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.
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.
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.