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

Performance of binary polar codes with high- dimensional kernel 1

Vera Miloslavskaya, Peter Trifonov

Published Jan 1, 2011• 1 citation
OpenAlex

Abstract

Upper union bound for the decoding error probability of polar codes with arbitrary binary kernels under the successive cancellation decoding is derived. The proposed approach is based on the representation of polar codes as multilevel ones.

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

On the Successive Cancellation Decoding of Polar Codes with Arbitrary Linear Binary Kernels

Zhiliang Huang, Zhang, Shiyi, Zhang, Feiyan +2 more

A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a $l$-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities $W_{G}^{(\cdot)}(\cdot|0)$ and $W_{G}^{(\cdot)}(\cdot|1)$ separately, a $W$-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a $m\times m$ binary kernel, the complexity of straightforward SC decoder is $O(2^{m}N\log N)$. With $W$-expressions, we reduce the complexity of straightforward SC decoder to $O(m^{2}N\log N)$ when $m\leq 16$. Simulation results show that $16\times16$ kernel polar codes offer significant advantages in terms of error performances compared with $2\times2$ kernel polar codes under SC and list SC decoders.

arXiv:1701.03264•Jan 12, 2017•9 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 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

Fast Successive Cancellation Decoding of Polar Codes With Large Kernels

Anatolii Ashikhmin, Peter Trifonov

A generalization of the fast successive cancellation decoding algorithm to the case of binary polar codes with arbitrary large kernels is presented. Its asymptotic latency is shown to be$O(N^{1-1/\mu })$, where$\mu $is the scaling exponent of the underlying polarization kernel.

IEEE Transactions on Communications•Jun 28, 2024•6 citations

Simplified Successive Cancellation Decoding of Polar Codes With Medium-Dimensional Binary Kernels

Zhiliang Huang, Shiyi Zhang, Feiyan Zhang +3 more

A method is proposed, called$l$-formula, to design efficient successive cancellation (SC) decoding of polar codes with medium-dimensional binary kernels (dimensions up to 16). Our$l$-formula method obtains the simplified recursive formulas of the SC decoder in the likelihood ratio domain for any binary kernel. We confirm that the complexity of the SC decoder based on$l$-formulas achieves considerable advantages over the straightforward SC decoder for polar codes with medium-dimensional binary kernels.

IEEE Access•Jan 1, 2018•14 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
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.
A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a lll-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities WG(⋅)(⋅∣0)W_{G}^{(\cdot)}(\cdot|0)WG(⋅)​(⋅∣0) and WG(⋅)(⋅∣1)W_{G}^{(\cdot)}(\cdot|1)WG(⋅)​(⋅∣1) separately, a WWW-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a m×mm\times mm×m binary kernel, the complexity of straightforward SC decoder is O(2mNlog⁡N)O(2^{m}N\log N)O(2mNlogN). With WWW-expressions, we reduce the complexity of straightforward SC decoder to O(m2Nlog⁡N)O(m^{2}N\log N)O(m2NlogN) when m≤16m\leq 16m≤16. Simulation results show that 16×1616\times1616×16 kernel polar codes offer significant advantages in terms of error performances compared with 2×22\times22×2 kernel polar codes under SC and list SC decoders.
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.
A generalization of the fast successive cancellation decoding algorithm to the case of binary polar codes with arbitrary large kernels is presented. Its asymptotic latency is shown to beO(N1−1/μ)O(N^{1-1/\mu })O(N1−1/μ), where$\mu $is the scaling exponent of the underlying polarization kernel.
A method is proposed, calledlll-formula, to design efficient successive cancellation (SC) decoding of polar codes with medium-dimensional binary kernels (dimensions up to 16). Ourlll-formula method obtains the simplified recursive formulas of the SC decoder in the likelihood ratio domain for any binary kernel. We confirm that the complexity of the SC decoder based onlll-formulas achieves considerable advantages over the straightforward SC decoder for polar codes with medium-dimensional binary kernels.