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

Fast Partial-Sum Update Method for Successive-Cancellation Decoding of Polar Codes and PAC Codes

Xun Li, Yucheng Wu

Published Jan 1, 2026• 0 citations
Publisher

Abstract

The decoding complexity of polarization-adjusted convolutional (PAC) codes and Polar codes is significantly affected by the efficiency of partial-sum updates. In this letter, we propose a fast partial-sum update method for the successive-cancellation decoding (SCD) of PAC and Polar codes by exploiting the Pascal-triangle structure of the Polar generator matrix. Simulation results show that the proposed method reduces the number of partial-sum updates compared with conventional SCD, particularly for short code lengths and in the low-rate regime. Compared with representative fast decoding methods, the proposed method also shows a complexity advantage in the low-rate regime.

DOI
10.1109/lcomm.2026.3683509

Related papers

Complexity-efficient Fano Decoding of Polarization-adjusted Convolutional (PAC) Codes

Mohammad Rowshan, Andreas Peter Burg, Emanuele Viterbo

Polarization-adjusted convolutional (PAC) codes are modified polar codes in which a one-to-one convolutional transformation is employed before the classical polar transform. Fano decoding of PAC codes in the Shannon lecture at ISIT2019 showed an outstanding performance at the cost of a high time-complexity, particularly at low SNR regimes. In order to reduce this complexity, an adaptive heuristic metric is proposed that improves the comparability of the variable-length paths and adjusts itself in response to the channel noise level. This metric can significantly reduce the number of nodes visited on average in tree-traversal. Additionally, a partial rewinding of the successive cancellation process is proposed to efficiently compute the intermediate LLRs and partial sums when backtracking occurs in the Fano algorithm. This method avoids storing the intermediate results of the decoding process or restarting (full rewinding) the decoding process.

International Symposium on Information Theory and its Applications•Oct 24, 2020•6 citations

A Novel SCL Bit-Flipping Decoding Of Polarization-Adjusted Convolutional (PAC) Codes

Zhang, Wei

Polar codes have attracted the attention of numerous researchers in the past decade due to their excellent performance. However, their performance at short block lengths under standard successive cancellation decoding is far from desirable. An effective method to improve the performance at short lengths is CRC precoding followed by successive-cancellation list decoding. Later, Arikan presented polarization-adjusted convolutional (PAC) codes, which further improve the performance of polar codes. In fact, bit-flipping is another post-processing method that can improve decoding performance. In this paper, we propose a novel SCL Bit-Flipping of PAC Codes. We show that better performance can be achieved using list decoding when the list size is the same for PAC codes (N=128, K=64). The decoding performance of our newly proposed PAC-SCLF with a list size of 32 is 0.3 dB better than that of the traditional PAC-SCL with a list size of 32. We set the maximum number of bit flips to 5. The performance of the list size (L=32) for PAC-SCLF is almost the same as the performance of the list size (L=128) for PAC-SCL.

arXiv:2307.05871•Jul 12, 2023•1 citation

Efficient Partial Sum Architecture and Memory Reduction Method for SC-Flip Polar Decoder

Jae Hong Roh, Useok Lee, Yongje Lee +1 more

To improve the error correction performance of successive cancellation (SC) decoding of polar codes, SC-flip (SCF) decoding was proposed. However, it requires large additional memory to save the decoding history for hardware implementation. This paper proposes a partial sum (PS) memory reduction method and a PS architecture for SCF decoders. We analyze the fractal structure of the generator matrix and propose a logic circuit to decide the corresponding row of the generator matrix for an arbitrary bit-index. The proposed design was implemented on the Xilinx Virtex-7 FPGA, which can reduce the number of flip-flops by up to 47% and the PS history memory size by 94% compared to other PS architectures.

International SoC Design Conference•Oct 6, 2021•0 citations

A hybrid partial sum computation unit architecture for list decoders of polar codes

Jun Ting Lin, Zhiyuan Yan

Although the successive cancelation (SC) algorithm works well for very long polar codes, its error performance for shorter polar codes is much worse. Several SC based list decoding algorithms have been proposed to improve the error performances of both long and short polar codes. A significant step of SC based list decoding algorithms is the updating of partial sums for all decoding paths. In this paper, we first proposed a lazy copy partial sum computation algorithm for SC based list decoding algorithms. Instead of copying partial sums directly, our lazy copy algorithm copies indices of partial sums. Based on our lazy copy algorithm, we propose a hybrid partial sum computation unit architecture, which employs both registers and memories so that the overall area efficiency is improved. Compared with a recent partial sum computation unit for list decoders, when the list size L = 4, our partial sum computation unit achieves an area saving of 23% and 63% for block length 213and 215, respectively.

arXiv:1506.05896•IEEE International Conference on Acoustics Speech and Signal Processing•Apr 1, 2015•3 citations

Fast Successive-Cancellation List Flip Decoding of Polar Codes

Nghia Doan, Seyyed Ali Hashemi, Warren J. Gross

This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.

arXiv:2109.12239•IEEE Access•Jan 1, 2022•8 citations

Fast Successive-Cancellation-Based Decoders of Polar Codes

Maryam Haghighi Ardakani, Muhammad Hanif, Masoud Ardakani +1 more

The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.

IEEE Transactions on Communications•Mar 19, 2019•62 citations
The decoding complexity of polarization-adjusted convolutional (PAC) codes and Polar codes is significantly affected by the efficiency of partial-sum updates. In this letter, we propose a fast partial-sum update method for the successive-cancellation decoding (SCD) of PAC and Polar codes by exploiting the Pascal-triangle structure of the Polar generator matrix. Simulation results show that the proposed method reduces the number of partial-sum updates compared with conventional SCD, particularly for short code lengths and in the low-rate regime. Compared with representative fast decoding methods, the proposed method also shows a complexity advantage in the low-rate regime.
Polarization-adjusted convolutional (PAC) codes are modified polar codes in which a one-to-one convolutional transformation is employed before the classical polar transform. Fano decoding of PAC codes in the Shannon lecture at ISIT2019 showed an outstanding performance at the cost of a high time-complexity, particularly at low SNR regimes. In order to reduce this complexity, an adaptive heuristic metric is proposed that improves the comparability of the variable-length paths and adjusts itself in response to the channel noise level. This metric can significantly reduce the number of nodes visited on average in tree-traversal. Additionally, a partial rewinding of the successive cancellation process is proposed to efficiently compute the intermediate LLRs and partial sums when backtracking occurs in the Fano algorithm. This method avoids storing the intermediate results of the decoding process or restarting (full rewinding) the decoding process.
Polar codes have attracted the attention of numerous researchers in the past decade due to their excellent performance. However, their performance at short block lengths under standard successive cancellation decoding is far from desirable. An effective method to improve the performance at short lengths is CRC precoding followed by successive-cancellation list decoding. Later, Arikan presented polarization-adjusted convolutional (PAC) codes, which further improve the performance of polar codes. In fact, bit-flipping is another post-processing method that can improve decoding performance. In this paper, we propose a novel SCL Bit-Flipping of PAC Codes. We show that better performance can be achieved using list decoding when the list size is the same for PAC codes (N=128, K=64). The decoding performance of our newly proposed PAC-SCLF with a list size of 32 is 0.3 dB better than that of the traditional PAC-SCL with a list size of 32. We set the maximum number of bit flips to 5. The performance of the list size (L=32) for PAC-SCLF is almost the same as the performance of the list size (L=128) for PAC-SCL.
To improve the error correction performance of successive cancellation (SC) decoding of polar codes, SC-flip (SCF) decoding was proposed. However, it requires large additional memory to save the decoding history for hardware implementation. This paper proposes a partial sum (PS) memory reduction method and a PS architecture for SCF decoders. We analyze the fractal structure of the generator matrix and propose a logic circuit to decide the corresponding row of the generator matrix for an arbitrary bit-index. The proposed design was implemented on the Xilinx Virtex-7 FPGA, which can reduce the number of flip-flops by up to 47% and the PS history memory size by 94% compared to other PS architectures.
Although the successive cancelation (SC) algorithm works well for very long polar codes, its error performance for shorter polar codes is much worse. Several SC based list decoding algorithms have been proposed to improve the error performances of both long and short polar codes. A significant step of SC based list decoding algorithms is the updating of partial sums for all decoding paths. In this paper, we first proposed a lazy copy partial sum computation algorithm for SC based list decoding algorithms. Instead of copying partial sums directly, our lazy copy algorithm copies indices of partial sums. Based on our lazy copy algorithm, we propose a hybrid partial sum computation unit architecture, which employs both registers and memories so that the overall area efficiency is improved. Compared with a recent partial sum computation unit for list decoders, when the list size L = 4, our partial sum computation unit achieves an area saving of 23% and 63% for block length 213and 215, respectively.
This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.
The successive-cancellation list (SCL) and successive-cancellation flip (SCF) decoding can be used to improve the performance of polar codes, especially for short to moderate length codes. However, their serial decoding nature results in significant decoding latencies. Implementing some operations in parallel can reduce their decoding latencies. This paper presents fast implementations of the SCL and SCF decoders. In particular, we propose fast parallel list decoders for five newly identified types of nodes in the decoding tree of a polar code, which significantly improves the decoding latency. We also present novel fast SCF decoders that decode some special nodes in the decoding tree of a polar code without serially computing bit log-likelihood ratios. Using our proposed fast parallel SCF decoders, we observed an improvement up to 81% with respect to the original SCF decoder. This significant reduction in the decoding latency is observed without sacrificing the bit-error-rate performance of the code.