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:2303.01561 · IEEE Wireless Communications and Networking Conference

Successive-Cancellation Flip Decoding of Polar Codes with a Simplified Restart Mechanism

Ilshat Sagitov, Charles Pillet, Alexios Balatsoukas‐Stimming, Pascal Giard

Published Mar 1, 2023• 4 citations
arXivHTMLPDF

Abstract

Polar codes are a class of error-correcting codes that provably achieve the capacity of practical channels. The successive-cancellation flip (SCF) decoder is a low-complexity decoder that was proposed to improve the performance of the successive-cancellation (SC) decoder as an alternative to the high-complexity successive-cancellation list (SCL) decoder. The SCF decoder improves the error-correction performance of the SC decoder, but the variable execution time and the high worst-case execution time pose a challenge for the realization of receivers with fixed-time algorithms. The dynamic SCF (DSCF) variation of the SCF decoder further improves the error-correction performance but the challenge of decoding delay remains. In this work, we propose a simplified restart mechanism (SRM) that reduces the execution time of SCF and DSCF decoders through conditional restart of the additional trials from the second half of the codeword. We show that the proposed mechanism is able to improve the execution time characteristics of SCF and DSCF decoders while providing identical error-correction performance. For a DSCF decoder that can flip up to 3 simultaneous bits per decoding trial, the average execution time, the average additional execution time and the execution-time variance are reduced by approximately 31%, 37% and 57%, respectively. For this setup, the mechanism requires approximately 3.9% additional memory.

DOI
10.1109/wcnc55385.2023.10119097

Related papers

Restart Mechanisms for the Successive-Cancellation List-Flip Decoding of Polar Codes

Charles Pillet, Ilshat Sagitov, Alexios Balatsoukas‐Stimming +1 more

Polar codes concatenated with a cyclic redundancy check (CRC) code have been selected in the 5G standard with the successive-cancellation list (SCL) of list size L = 8 as the baseline algorithm. Despite providing great error-correction performance, a large list size increases the hardware complexity of the SCL decoder. Alternatively, flip decoding algorithms were proposed to improve the error-correction performance with a low-complexity hardware implementation. The combination of list and flip algorithms, the successive-cancellation list flip (SCLF) and dynamic SCLF (DSCLF) algorithms, provides error-correction performance close to SCL-32 with a list size L = 2 and Tmax = 300 maximum additional trials. However, these decoders have a variable execution time, a characteristic that poses a challenge to some practical applications. In this work, we propose a restart mechanism for list-flip algorithms that allows us to skip parts of the decoding computations without affecting the error-correction performance. We show that the restart location cannot realistically be allowed to occur at any location in a codeword as it would lead to an unreasonable memory overhead under DSCLF. Hence, we propose a mechanism where the possible restart locations are limited to a set and propose various construction methods for that set. The construction methods are compared, and the tradeoffs are discussed. For a polar code of length N = 1024 and rate ¼, under DSCLF decoding with a list size L = 2 and a maximum number of trials Tmax = 300, our proposed approach is shown to reduce the average execution time by 41.7% with four restart locations at the cost of approximately 1.5% in memory overhead.

Entropy•Mar 14, 2025•2 citations

Neural Dynamic Successive Cancellation Flip Decoding of Polar Codes

Nghia Doan, Seyyed Ali Hashemi, Furkan Ercan +2 more

Dynamic successive cancellation flip (DSCF) decoding of polar codes is a powerful algorithm that can achieve the error correction performance of successive cancellation list (SCL) decoding, with a complexity that is close to that of successive cancellation (SC) decoding at practical signal-to-noise ratio (SNR) regimes. However, DSCF decoding requires costly transcendental computations which adversely affect its implementation complexity. In this paper, we first show that a direct application of common approximation schemes on the conventional DSCF decoding results in significant error-correction performance loss. We then introduce a training parameter and propose an approximation scheme which completely removes the need to perform transcendental computations in DSCF decoding, with almost no error-correction performance degradation.

arXiv:1907.11563•SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2019•11 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

Reducing Search Complexity of Dynamic SC-Flip Decoding for Polar Codes

Xinyuan Qiao, Hangxuan Cui, Jun Ting Lin +1 more

Polar codes are the first error-correcting codes that achieve the Shannon limit under successive cancellation (SC) decoding when the code length is infinite. However, the error-correcting performance of SC decoding is mediocre for short and moderate code lengths. Dynamic successive cancellation flip (DSCF) decoding has been proposed that performs extra SC decoding trails with multi-bit flipping to improve the performance of short and moderate polar codes. The DSCF decoding suffers from high computational complexity and decoding latency since all information bits are tested when searching for the flipping candidates, which leads to intensive metric calculations. To reduce the search complexity of the DSCF, a method based on the critical set (CS) is proposed in this paper to narrow the search range and two types of special nodes, rate-0 nodes and repetition nodes, are incorporated for further complexity reduction. Simulation results show that the proposed method can achieve more than 70% reduction in calculations on metrics, and up to 22.79% reduction in calculations on nodes without performance loss compared to the original DSCF decoding.

IEEE International Conference on Computer and Communications (ICCC)•Dec 10, 2021•2 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 Low-Latency Successive Cancellation Hybrid Decoder for Convolutional Polar Codes

Yu Wang, Shikai Qiu, Lirui Chen +4 more

By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•1 citation
Polar codes are a class of error-correcting codes that provably achieve the capacity of practical channels. The successive-cancellation flip (SCF) decoder is a low-complexity decoder that was proposed to improve the performance of the successive-cancellation (SC) decoder as an alternative to the high-complexity successive-cancellation list (SCL) decoder. The SCF decoder improves the error-correction performance of the SC decoder, but the variable execution time and the high worst-case execution time pose a challenge for the realization of receivers with fixed-time algorithms. The dynamic SCF (DSCF) variation of the SCF decoder further improves the error-correction performance but the challenge of decoding delay remains. In this work, we propose a simplified restart mechanism (SRM) that reduces the execution time of SCF and DSCF decoders through conditional restart of the additional trials from the second half of the codeword. We show that the proposed mechanism is able to improve the execution time characteristics of SCF and DSCF decoders while providing identical error-correction performance. For a DSCF decoder that can flip up to 3 simultaneous bits per decoding trial, the average execution time, the average additional execution time and the execution-time variance are reduced by approximately 31%, 37% and 57%, respectively. For this setup, the mechanism requires approximately 3.9% additional memory.
Polar codes concatenated with a cyclic redundancy check (CRC) code have been selected in the 5G standard with the successive-cancellation list (SCL) of list size L = 8 as the baseline algorithm. Despite providing great error-correction performance, a large list size increases the hardware complexity of the SCL decoder. Alternatively, flip decoding algorithms were proposed to improve the error-correction performance with a low-complexity hardware implementation. The combination of list and flip algorithms, the successive-cancellation list flip (SCLF) and dynamic SCLF (DSCLF) algorithms, provides error-correction performance close to SCL-32 with a list size L = 2 and Tmax = 300 maximum additional trials. However, these decoders have a variable execution time, a characteristic that poses a challenge to some practical applications. In this work, we propose a restart mechanism for list-flip algorithms that allows us to skip parts of the decoding computations without affecting the error-correction performance. We show that the restart location cannot realistically be allowed to occur at any location in a codeword as it would lead to an unreasonable memory overhead under DSCLF. Hence, we propose a mechanism where the possible restart locations are limited to a set and propose various construction methods for that set. The construction methods are compared, and the tradeoffs are discussed. For a polar code of length N = 1024 and rate ¼, under DSCLF decoding with a list size L = 2 and a maximum number of trials Tmax = 300, our proposed approach is shown to reduce the average execution time by 41.7% with four restart locations at the cost of approximately 1.5% in memory overhead.
Dynamic successive cancellation flip (DSCF) decoding of polar codes is a powerful algorithm that can achieve the error correction performance of successive cancellation list (SCL) decoding, with a complexity that is close to that of successive cancellation (SC) decoding at practical signal-to-noise ratio (SNR) regimes. However, DSCF decoding requires costly transcendental computations which adversely affect its implementation complexity. In this paper, we first show that a direct application of common approximation schemes on the conventional DSCF decoding results in significant error-correction performance loss. We then introduce a training parameter and propose an approximation scheme which completely removes the need to perform transcendental computations in DSCF decoding, with almost no error-correction performance degradation.
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 are the first error-correcting codes that achieve the Shannon limit under successive cancellation (SC) decoding when the code length is infinite. However, the error-correcting performance of SC decoding is mediocre for short and moderate code lengths. Dynamic successive cancellation flip (DSCF) decoding has been proposed that performs extra SC decoding trails with multi-bit flipping to improve the performance of short and moderate polar codes. The DSCF decoding suffers from high computational complexity and decoding latency since all information bits are tested when searching for the flipping candidates, which leads to intensive metric calculations. To reduce the search complexity of the DSCF, a method based on the critical set (CS) is proposed in this paper to narrow the search range and two types of special nodes, rate-0 nodes and repetition nodes, are incorporated for further complexity reduction. Simulation results show that the proposed method can achieve more than 70% reduction in calculations on metrics, and up to 22.79% reduction in calculations on nodes without performance loss compared to the original DSCF decoding.
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.
By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.