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 Transactions on Communications

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

Peter Trifonov, Liudmila Karakchieva

Published Jun 13, 2023• 15 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2023.3285773

Related papers

Recursive Trellis Processing of Large Polarization Kernels

Peter Trifonov

A reduced complexity algorithm is presented for computing the log-likelihood ratios arising in the successive cancellation decoder for polar codes with large kernels of arbitrary dimension. The proposed algorithm exploits recursive trellis representation of the codes generated by submatrices of the polarization kernel, and enables polar codes based on large kernels to provide better performance compared to the codes based on Arikan kernel with the same decoding complexity.

arXiv:2101.08081•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•12 citations

Trellis-based Decoding Techniques for Polar Codes with Large Kernels

Peter Trifonov

A recursive trellis-based algorithm is proposed for computing the probabilities arising in the successive cancellation (SC) decoding algorithm for polar codes with arbitrary linear kernels. This approach enables one to re-use intermediate values obtained at different phases. Arikan SC algorithm is shown to be a special case of this method.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•11 citations

Design and Decoding of Polar Codes with Large Kernels: A Survey

Peter Trifonov

We present techniques for the construction of polar codes with large kernels and their decoding. A crucial problem in the implementation of the successive cancellation decoding algorithm and its derivatives is kernel processing, i.e., fast evaluation of the log-likelihood ratios for kernel input symbols. We discuss window and recursive trellis processing methods. We consider techniques for evaluation of the reliability of bit subchannels and for obtaining codes with improved distance properties.

Problems of Information Transmission•Jan 1, 2023•8 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

Window Processing of Binary Polarization Kernels

Grigorii Trofimiuk, Peter Trifonov

A decoding algorithm for polar (sub)codes with binary 2t×2tpolarization kernels is presented. It is based on the window processing (WP) method, which exploits the linear relationship of the polarization kernels and the Arikan matrix. This relationship enables one to compute the kernel input symbols probabilities by computing the probabilities of several paths in Arikan successive cancellation (SC) decoder. In this paper we propose an improved version of WP, which has significantly lower arithmetic complexity and operates in log-likelihood ratios (LLRs) domain. The algorithm identifies and reuses common subexpressions arising in computation of Arikan SC path scores. The proposed algorithm is applied to kernels of size 16 and 32 with improved polarization properties. It enables polar (sub)codes with the considered kernels to simultaneously provide better performance and lower decoding complexity compared with polar (sub)codes with Arikan kernel.

arXiv:2010.07884•IEEE Transactions on Communications•Apr 12, 2021•21 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
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.
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 decoding algorithm for polar (sub)codes with binary 2t×2tpolarization kernels is presented. It is based on the window processing (WP) method, which exploits the linear relationship of the polarization kernels and the Arikan matrix. This relationship enables one to compute the kernel input symbols probabilities by computing the probabilities of several paths in Arikan successive cancellation (SC) decoder. In this paper we propose an improved version of WP, which has significantly lower arithmetic complexity and operates in log-likelihood ratios (LLRs) domain. The algorithm identifies and reuses common subexpressions arising in computation of Arikan SC path scores. The proposed algorithm is applied to kernels of size 16 and 32 with improved polarization properties. It enables polar (sub)codes with the considered kernels to simultaneously provide better performance and lower decoding complexity compared with polar (sub)codes with Arikan 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.