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 Access

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

Zhiliang Huang, Shiyi Zhang, Feiyan Zhang, Chunjiang Duanmu, Farong Zhong, Ming Chen

Published Jan 1, 2018• 14 citations
Publisher

Abstract

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.

DOI
10.1109/access.2018.2834465

Related papers

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

On the Non-Approximate Successive Cancellation Decoding of Binary Polar Codes With Medium Kernels

Zhiliang Huang, Zongsheng Jiang, Shuihong Zhou +1 more

Polar codes constructed by large kernels can attain better finite length performance than those originating from Arıkan’s 2 × 2 kernel. However, the successive cancellation (SC) decoding for these polar codes is impractical even for relatively small kernel size ofmbecause complexity of thekernel computationgrows exponentially withm. This research shows whenm> 2, there exists a large amount oflike termsin the kernel computation which yields a ground for facilitating the decoding. By transferring the kernel computation from the probability domain to the likelihood ratio domain (l-domain), the so-calledl-formula method provides an efficient way to combine the like terms in the kernel computation for kernels up to size 11. However, thel-formula method becomes intractable for kernel size beyond 11. To further reduce the computational complexity, this paper proposes aW-formula method which transforms the kernel computation into the probability pair domain (W-domain). Advanced from thel-domain, the numerator and denominator of the likelihood ratio are considered separately, which eases the restrictions of combining like terms. TheW-formula method can combine much more like terms resulting in a significant reduction on the number of sub-formulas for medium kernels (m≤ 16). Furthermore, in theW-domain, sub-formulas become regular and there exist many common sub-formulas whose computations can be shared. Being able to handle kernels of size up to 16, we show that theW-formula based SC decoding achieves a significant complexity reduction over the existing non-approximate SC decoding (thel-formula based SC decoding).

IEEE Access•Jan 1, 2023•5 citations

Recursive Processing Algorithm for Low Complexity Decoding of Polar Codes With Large Kernels

Peter Trifonov, Liudmila Karakchieva

A reduced complexity algorithm is presented for computing the log-likelihood ratios (LLRs) arising in the successive cancellation (SC) decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits a recursive trellis representation of the codes generated by submatrices of the polarization kernel and enables polar codes based on large kernels to be decoded with lower complexity compared to the codes based on the Arıkan kernel with the same performance. Extensions to the case of non-binary kernels are presented.

IEEE Transactions on Communications•Jun 13, 2023•15 citations

Fast Successive-Cancellation Decoding of 2 × 2 Kernel Non-Binary Polar Codes

Ali Farsiabi, Hamid Ebrahimzad, Masoud Ardakani +1 more

Non-binary polar codes (NBPCs) decoded by successive cancellation (SC) algorithm have remarkable bit-error-rate performance compared to the binary polar codes (BPCs). Due to its serial nature, SC decoding suffers from long latency. The latency issue in BPCs has been the topic of extensive research and it has been notably resolved by the introduction of fast SC-based decoders. However, the latency problem of NBPCs is mainly untouched and the vast majority of research on NBPCs is devoted to issues concerning design and efficient implementation. In this paper, we propose fast SC decoding for NBPCs constructed based on$2\times 2$kernels. In particular, we extend the special nodes of BPCs to their non-binary counterpart and define various non-binary special nodes in the SC decoding tree of NBPCs and propose their fast decoding. This way, we avoid traversing the full decoding tree and significantly reduce the decoding delay compared to symbol-by-symbol SC decoding. We also propose a simplified NBPC structure that facilitates the procedure of non-binary fast SC decoding. Using our proposed fast non-binary decoder, we observe an improvement of more than 96% in latency concerning the original SC decoding. This is while our proposed fast SC decoder for NBPCs incurs no error-rate loss.

IEEE Transactions on Communications•Aug 26, 2024•5 citations

Fast Successive-Cancellation Decoding of 2 x 2 Kernel Non-Binary Polar Codes: Identification, Decoding and Simplification

Ali Farsiabi, Hamid Ebrahimzad, Masoud Ardakani +1 more

Non-binary polar codes (NBPCs) decoded by successive cancellation (SC) algorithm have remarkable bit-error-rate performance compared to the binary polar codes (BPCs). Due to the serial nature, SC decoding suffers from large latency. The latency issue in BPCs has been the topic of extensive research and it has been notably resolved by the introduction of fast SC-based decoders. However, the vast majority of research on NBPCs is devoted to issues concerning design and efficient implementation. In this paper, we propose fast SC decoding for NBPCs constructed based on 2 x 2 kernels. In particular, we identify various non-binary special nodes in the SC decoding tree of NBPCs and propose their fast decoding. This way, we avoid traversing the full decoding tree and significantly reduce the decoding delay compared to symbol-by-symbol SC decoding. We also propose a simplified NBPC structure that facilitates the procedure of non-binary fast SC decoding. Using our proposed fast non-binary decoder, we observed an improvement of up to 95% in latency concerning the original SC decoding. This is while our proposed fast SC decoder for NBPCs incurs no error-rate loss.

arXiv:2401.07433•Jan 15, 2024•0 citations

Generalized Schematic Successive Cancellation Decoding for Polar Codes

Karim El‐Abbasy, Ramy Taki Eldin, Salwa Elramly +1 more

Recently, generalized polar codes were introduced to provide more code lengths and rates without the need for shortening or puncturing. However, as the size of the kernel matrix increases, computing the Log-Likelihood Ratio (LLR) functions in successive cancellation decoder for these codes becomes mathematically more complicated. In this paper, a new simplified general method is proposed to calculate these LLR functions based on the schematic diagram of the selected kernel matrix for sizes higher than 2. Our proposed method fragments the main block into some basic components whose formulas have been previously proven by Arikan for $2 \times 2$ kernel matrix. The validity of the resulting LLR functions is tested on different kernel matrices and proven to be similar to those in literature.

IEEE International Black Sea Conference on Communications and Networking•May 24, 2021•0 citations
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.
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 constructed by large kernels can attain better finite length performance than those originating from Arıkan’s 2 × 2 kernel. However, the successive cancellation (SC) decoding for these polar codes is impractical even for relatively small kernel size ofmbecause complexity of thekernel computationgrows exponentially withm. This research shows whenm> 2, there exists a large amount oflike termsin the kernel computation which yields a ground for facilitating the decoding. By transferring the kernel computation from the probability domain to the likelihood ratio domain (l-domain), the so-calledl-formula method provides an efficient way to combine the like terms in the kernel computation for kernels up to size 11. However, thel-formula method becomes intractable for kernel size beyond 11. To further reduce the computational complexity, this paper proposes aW-formula method which transforms the kernel computation into the probability pair domain (W-domain). Advanced from thel-domain, the numerator and denominator of the likelihood ratio are considered separately, which eases the restrictions of combining like terms. TheW-formula method can combine much more like terms resulting in a significant reduction on the number of sub-formulas for medium kernels (m≤ 16). Furthermore, in theW-domain, sub-formulas become regular and there exist many common sub-formulas whose computations can be shared. Being able to handle kernels of size up to 16, we show that theW-formula based SC decoding achieves a significant complexity reduction over the existing non-approximate SC decoding (thel-formula based SC decoding).
A reduced complexity algorithm is presented for computing the log-likelihood ratios (LLRs) arising in the successive cancellation (SC) decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits a recursive trellis representation of the codes generated by submatrices of the polarization kernel and enables polar codes based on large kernels to be decoded with lower complexity compared to the codes based on the Arıkan kernel with the same performance. Extensions to the case of non-binary kernels are presented.
Non-binary polar codes (NBPCs) decoded by successive cancellation (SC) algorithm have remarkable bit-error-rate performance compared to the binary polar codes (BPCs). Due to its serial nature, SC decoding suffers from long latency. The latency issue in BPCs has been the topic of extensive research and it has been notably resolved by the introduction of fast SC-based decoders. However, the latency problem of NBPCs is mainly untouched and the vast majority of research on NBPCs is devoted to issues concerning design and efficient implementation. In this paper, we propose fast SC decoding for NBPCs constructed based on2×22\times 22×2kernels. In particular, we extend the special nodes of BPCs to their non-binary counterpart and define various non-binary special nodes in the SC decoding tree of NBPCs and propose their fast decoding. This way, we avoid traversing the full decoding tree and significantly reduce the decoding delay compared to symbol-by-symbol SC decoding. We also propose a simplified NBPC structure that facilitates the procedure of non-binary fast SC decoding. Using our proposed fast non-binary decoder, we observe an improvement of more than 96% in latency concerning the original SC decoding. This is while our proposed fast SC decoder for NBPCs incurs no error-rate loss.
Non-binary polar codes (NBPCs) decoded by successive cancellation (SC) algorithm have remarkable bit-error-rate performance compared to the binary polar codes (BPCs). Due to the serial nature, SC decoding suffers from large latency. The latency issue in BPCs has been the topic of extensive research and it has been notably resolved by the introduction of fast SC-based decoders. However, the vast majority of research on NBPCs is devoted to issues concerning design and efficient implementation. In this paper, we propose fast SC decoding for NBPCs constructed based on 2 x 2 kernels. In particular, we identify various non-binary special nodes in the SC decoding tree of NBPCs and propose their fast decoding. This way, we avoid traversing the full decoding tree and significantly reduce the decoding delay compared to symbol-by-symbol SC decoding. We also propose a simplified NBPC structure that facilitates the procedure of non-binary fast SC decoding. Using our proposed fast non-binary decoder, we observed an improvement of up to 95% in latency concerning the original SC decoding. This is while our proposed fast SC decoder for NBPCs incurs no error-rate loss.
Recently, generalized polar codes were introduced to provide more code lengths and rates without the need for shortening or puncturing. However, as the size of the kernel matrix increases, computing the Log-Likelihood Ratio (LLR) functions in successive cancellation decoder for these codes becomes mathematically more complicated. In this paper, a new simplified general method is proposed to calculate these LLR functions based on the schematic diagram of the selected kernel matrix for sizes higher than 2. Our proposed method fragments the main block into some basic components whose formulas have been previously proven by Arikan for 2×22 \times 22×2 kernel matrix. The validity of the resulting LLR functions is tested on different kernel matrices and proven to be similar to those in literature.