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 Information Theory Workshop (ITW)

Trellis-based Decoding Techniques for Polar Codes with Large Kernels

Peter Trifonov

Published Aug 1, 2019• 11 citations
Publisher

Abstract

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.

DOI
10.1109/itw44776.2019.8989386

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

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

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 trellis decoding based on Massey trellis for polar codes with a ternary kernel

Feifei Zhang, Zhiliang Huang, Youyan Zhang +1 more

A trellis decoding scheme based on Massey trellis for polar codes with a ternary kernel is proposed. First, we construct trellises for kernel computations of the successive cancellation (SC) decoder based on the Massey trellis. Then, the scheme calculates the bit-channel transition probability through these trellises, which provides an appropriate framework to take advantage of the distributive law and can effectively reduce the number of operations. Simulation results show that for a G5⊗3 polar code of length 243 and rate 0.5, our scheme can save 14.2% of the computational cost with no sacrifice in error performance under the SC decoder.

International Conference on Optics and Communication Technology (ICOCT)•Dec 15, 2023•1 citation

Recursive Trellis Decoding Techniques of Polar Codes

Peter Trifonov

Recursive trellis decoding of polar codes is considered. Polar codes are shown to have much lower recursive trellis decoding complexity compared to similar Reed-Muller codes. Furthermore, a low-latency decoding algorithm, which combines recursive trellis and successive cancellation decoding methods, is presented.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•5 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
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.
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 trellis decoding scheme based on Massey trellis for polar codes with a ternary kernel is proposed. First, we construct trellises for kernel computations of the successive cancellation (SC) decoder based on the Massey trellis. Then, the scheme calculates the bit-channel transition probability through these trellises, which provides an appropriate framework to take advantage of the distributive law and can effectively reduce the number of operations. Simulation results show that for a G5⊗3 polar code of length 243 and rate 0.5, our scheme can save 14.2% of the computational cost with no sacrifice in error performance under the SC decoder.