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

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

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

Published Jan 12, 2017• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1701.03264

Related papers

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

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

Efficient stochastic list successive cancellation decoder for polar codes

Xiao Liang, Chuan Zhang, Menghui Xu +2 more

Representing continuous values by streams of random binary bits, stochastic decoding has shown advantages in both hardware efficiency and fault tolerance, therefore has been widely adopted by iterative decoding of error correction codes such as low-density parity-check (LDPC) codes and so on. Recently, polar codes, the first codes that can provably achieve the capacity of symmetric binary-input discrete memoryless channels (B-DMCs), have drawn a lot of attentions from both academia and industry. Although, polar codes with list successive cancellation (SC) decoding can outperform several best-known LDPC codes even within high error-rate regions, the linearly increasing hardware complexity makes its efficient implementation difficult. To this end, the stochastic list SC polar decoding algorithm is proposed in this paper to provide a good tradeoff between performance and complexity. In order to increase the decoding performance of stochastic list SC polar decoder, doubling probability approach is presented. The corresponding hardware architecture is also given. The approximate doubling approach is employed to facilitate the efficient implementation. Implementation results have shown that the proposed stochastic list SC polar decoder can achieve a good trade-off between performance and complexity.

IEEE International System-on-Chip Conference (SOCC)•Sep 1, 2015•12 citations
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.
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.
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.
Representing continuous values by streams of random binary bits, stochastic decoding has shown advantages in both hardware efficiency and fault tolerance, therefore has been widely adopted by iterative decoding of error correction codes such as low-density parity-check (LDPC) codes and so on. Recently, polar codes, the first codes that can provably achieve the capacity of symmetric binary-input discrete memoryless channels (B-DMCs), have drawn a lot of attentions from both academia and industry. Although, polar codes with list successive cancellation (SC) decoding can outperform several best-known LDPC codes even within high error-rate regions, the linearly increasing hardware complexity makes its efficient implementation difficult. To this end, the stochastic list SC polar decoding algorithm is proposed in this paper to provide a good tradeoff between performance and complexity. In order to increase the decoding performance of stochastic list SC polar decoder, doubling probability approach is presented. The corresponding hardware architecture is also given. The approximate doubling approach is employed to facilitate the efficient implementation. Implementation results have shown that the proposed stochastic list SC polar decoder can achieve a good trade-off between performance and complexity.