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 Very Large Scale Integration (VLSI) Systems

Efficient Successive Cancellation Stack Decoder for Polar Codes

Wenqing Song, Huayi Zhou, Kai Niu, Zaichen Zhang, Li Li, Xiaohu You, Chuan Zhang

Published Jul 15, 2019• 19 citations
Publisher

Abstract

As an improved version of successive cancellation (SC) polar decoder, an SC stack (SCS) decoder has been proposed for performance improvement. However, the existing SCS polar decoder suffers a lot from high time complexity at low signal-to-noise ratio (SNR) region and space complexity compared with the SC decoder. To this end, two improved decoders are proposed to reduce time and space complexity in both low and high SNR regions. The first one is the segmented cyclic redundancy check (CRC)-aided SCS (SCA-SCS) decoder, which is based on segmented parity checkers. The second one is the adaptive SCS (ASCS) decoder, which has the flexibility of stack depth and searching width. Furthermore, a channel condition estimator is proposed to select appropriate decision criteria for different SNR scenarios. Results have shown that for the polar code of length 1024 and rate 1/2, two improved SCS decoders can perform better than the traditional SCS decoder. The proposed SCA-SCS decoder and the ASCS decoder can achieve 10.8% and 11.42% time complexity reduction and 31.68% and 60.85% space complexity reduction on average over binary-input additive white Gaussian noise channels (BI-AWGNCs), respectively. Efficient parallel hardware architecture of the SCS polar decoder is first proposed and implemented with 90- and 65-nm technologies. Results have verified its advantages over the state of the art (SOA).

DOI
10.1109/tvlsi.2019.2925029

Related papers

A Modified Successive-Cancellation Stack Polar Decoder

Li Chun, Xinhai Tong

Polar codes represent an emerging correcting codes with power to approach the capacity of a discrete memoryless channel.However, the decoding performance of polar codes with traditional successive cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes.In this paper, a modified successive cancellation stack (MSCS) polar decoder is proposed.Unlike the original SC stack polar (SCS) decoders, we propose a modified path that can significantly reduce latency of SCS decoders.Simulation results in the binary-input additive white Gaussian noise channel show that modified algorithm has the slightly performance as the SCS algorithm.Moreover, the time and space complexity of the MSCS decoder is much lower than that of the SCS and can be very close to that of the SC in the high SNR regime.

Advances in computer science research•Jan 1, 2015•1 citation

Adaptive Successive Cancellation Priority Decoder for 5G Polar Codes

Wenqing Song, Yifei Shen, Yuxiang Fu +2 more

As two common successive cancellation (SC)-based decoding algorithms of polar codes, the SC list (SCL) and SC stack (SCS) decoder can achieve satisfactory error correction performance, especially with increased list size or stack depth. Nevertheless, a large list size or stack depth will lead to high computational complexities and hardware resources. To this end, successive cancellation priority (SCP) decoding with priority- first searching strategy and trellis-like storage is proposed to offer one solution. In this paper, an efficient SCP decoder is first proposed to verify its advantages over SCL and SCS decoders. Furthermore, an adaptive node-inserting scheme is proposed to reduce the number of bits insert into the priority queue. Numerical results have shown that for the polar code with transmission length 1024 and rate 1/2, the proposed adaptive SCP (ASCP) decoder can achieve significant time complexity reduction on average compared with the standard SCL decoder. The hardware architecture of SCP decoding is implemented using 65-nm CMOS technology and the results show better throughput compared with the SCS decoder.

IEEE International Symposium on Circuits and Systems proceedings•Apr 27, 2021•4 citations

Successive-Cancellation Flip and Perturbation Decoder of Polar Codes

Charles Pillet, Ilshat Sagitov, Dominic Deslandes +1 more

In this paper, two decoding algorithms based on Successive-Cancellation (SC) are proposed to improve the error-correction performance of cyclic redundancy check (CRC)-aided polar codes while aiming for a low-complexity implementation. Comparisons with Dynamic SC Flip (DSCF) and SC Perturbation (SCP) are carried out since the proposed DSCF and Perturbation (DSCFP) and Perturbed DSCF (PDSCF) algorithms combine both methods. The analysis includes comparisons with several code lengths$N$and various number of decoding attempts$T_{max}$. For$N=1024$and the coding rate$R= 1/2$, the DSCF and the SCP algorithms with$T_{\max}= 17$are bested by approximately 0.1 dB at block-error rate (BLER) of 0.001. At BLER = 10−6and for$T_{max}= 64$, the gain is of 0.375 dB and > 0.5 dB with respect to DSCF and SCP, respectively. At high signal-to-noise ratio, the average computational complexity of the proposed algorithms is virtually equivalent to that of SC.

arXiv:2504.12102•IEEE Wireless Communications and Networking Conference•Mar 24, 2025•0 citations

Improved Parity Check Aided Successive Cancellation Flip Polar Decoders

Dwaipayan Ghosh, Sudipta Chattopadhyay

Polar Codes achieve average error correction performance at finite code lengths, when decoded using Successive Cancellation (SC) decoding. Successive Cancellation Flip (SC-Flip) based decoders provide a viable low complexity substitute of the high performing high complexity Successive Cancellation List (SCL) decoders, providing a considerable improvement in the performance. A novel approach to identify and flip multiple erroneous bits in each decoding attempt has been aimed in this paper. Moreover, a faster version of the proposed decoder is also presented, which provides better performance throughout the entire decoding range. The performance of the proposed decoders have been evaluated with respect to frame error correction rate along with average normalized complexity and then compared with some of the existing works for validating the outperformance.

International Conference on Advances in Electrical, Computing, Communication and Sustainable Technologies (ICAECT)•Jan 11, 2024•1 citation

A simplified decoding algorithm for multi-CRC polar codes

School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China, Haifen YANG

Polar codes represent one of the major breakthroughs in 5G standard, and have been proven to be able to achieve the symmetric capacity of binary-input discrete memoryless channels using the successive cancellation list (SCL) decoding algorithm.However, the SCL algorithm suffers from a large amount of memory overhead.This paper proposes an adaptive simplified decoding algorithm for multiple cyclic redundancy check (CRC) polar codes.Simulation results show that the proposed method can reduce the decoding complexity and memory space.It can also acquire the performance gain in the low signal to noise ratio region.

Journal of Systems Engineering and Electronics•Jan 31, 2020•10 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
As an improved version of successive cancellation (SC) polar decoder, an SC stack (SCS) decoder has been proposed for performance improvement. However, the existing SCS polar decoder suffers a lot from high time complexity at low signal-to-noise ratio (SNR) region and space complexity compared with the SC decoder. To this end, two improved decoders are proposed to reduce time and space complexity in both low and high SNR regions. The first one is the segmented cyclic redundancy check (CRC)-aided SCS (SCA-SCS) decoder, which is based on segmented parity checkers. The second one is the adaptive SCS (ASCS) decoder, which has the flexibility of stack depth and searching width. Furthermore, a channel condition estimator is proposed to select appropriate decision criteria for different SNR scenarios. Results have shown that for the polar code of length 1024 and rate 1/2, two improved SCS decoders can perform better than the traditional SCS decoder. The proposed SCA-SCS decoder and the ASCS decoder can achieve 10.8% and 11.42% time complexity reduction and 31.68% and 60.85% space complexity reduction on average over binary-input additive white Gaussian noise channels (BI-AWGNCs), respectively. Efficient parallel hardware architecture of the SCS polar decoder is first proposed and implemented with 90- and 65-nm technologies. Results have verified its advantages over the state of the art (SOA).
Polar codes represent an emerging correcting codes with power to approach the capacity of a discrete memoryless channel.However, the decoding performance of polar codes with traditional successive cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes.In this paper, a modified successive cancellation stack (MSCS) polar decoder is proposed.Unlike the original SC stack polar (SCS) decoders, we propose a modified path that can significantly reduce latency of SCS decoders.Simulation results in the binary-input additive white Gaussian noise channel show that modified algorithm has the slightly performance as the SCS algorithm.Moreover, the time and space complexity of the MSCS decoder is much lower than that of the SCS and can be very close to that of the SC in the high SNR regime.
As two common successive cancellation (SC)-based decoding algorithms of polar codes, the SC list (SCL) and SC stack (SCS) decoder can achieve satisfactory error correction performance, especially with increased list size or stack depth. Nevertheless, a large list size or stack depth will lead to high computational complexities and hardware resources. To this end, successive cancellation priority (SCP) decoding with priority- first searching strategy and trellis-like storage is proposed to offer one solution. In this paper, an efficient SCP decoder is first proposed to verify its advantages over SCL and SCS decoders. Furthermore, an adaptive node-inserting scheme is proposed to reduce the number of bits insert into the priority queue. Numerical results have shown that for the polar code with transmission length 1024 and rate 1/2, the proposed adaptive SCP (ASCP) decoder can achieve significant time complexity reduction on average compared with the standard SCL decoder. The hardware architecture of SCP decoding is implemented using 65-nm CMOS technology and the results show better throughput compared with the SCS decoder.
In this paper, two decoding algorithms based on Successive-Cancellation (SC) are proposed to improve the error-correction performance of cyclic redundancy check (CRC)-aided polar codes while aiming for a low-complexity implementation. Comparisons with Dynamic SC Flip (DSCF) and SC Perturbation (SCP) are carried out since the proposed DSCF and Perturbation (DSCFP) and Perturbed DSCF (PDSCF) algorithms combine both methods. The analysis includes comparisons with several code lengthsNNNand various number of decoding attemptsTmaxT_{max}Tmax​. ForN=1024N=1024N=1024and the coding rateR=1/2R= 1/2R=1/2, the DSCF and the SCP algorithms withTmax⁡=17T_{\max}= 17Tmax​=17are bested by approximately 0.1 dB at block-error rate (BLER) of 0.001. At BLER = 10−6and forTmax=64T_{max}= 64Tmax​=64, the gain is of 0.375 dB and > 0.5 dB with respect to DSCF and SCP, respectively. At high signal-to-noise ratio, the average computational complexity of the proposed algorithms is virtually equivalent to that of SC.
Polar Codes achieve average error correction performance at finite code lengths, when decoded using Successive Cancellation (SC) decoding. Successive Cancellation Flip (SC-Flip) based decoders provide a viable low complexity substitute of the high performing high complexity Successive Cancellation List (SCL) decoders, providing a considerable improvement in the performance. A novel approach to identify and flip multiple erroneous bits in each decoding attempt has been aimed in this paper. Moreover, a faster version of the proposed decoder is also presented, which provides better performance throughout the entire decoding range. The performance of the proposed decoders have been evaluated with respect to frame error correction rate along with average normalized complexity and then compared with some of the existing works for validating the outperformance.
Polar codes represent one of the major breakthroughs in 5G standard, and have been proven to be able to achieve the symmetric capacity of binary-input discrete memoryless channels using the successive cancellation list (SCL) decoding algorithm.However, the SCL algorithm suffers from a large amount of memory overhead.This paper proposes an adaptive simplified decoding algorithm for multiple cyclic redundancy check (CRC) polar codes.Simulation results show that the proposed method can reduce the decoding complexity and memory space.It can also acquire the performance gain in the low signal to noise ratio region.
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.