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 International Conference on Computer and Communications (ICCC)

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

Xinyuan Qiao, Hangxuan Cui, Jun Ting Lin, Zhongfeng Wang

Published Dec 10, 2021• 2 citations
Publisher

Abstract

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.

DOI
10.1109/iccc54389.2021.9674413

Related papers

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

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 Decoding of Polar Codes with a Simplified Restart Mechanism

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

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.

arXiv:2303.01561•IEEE Wireless Communications and Networking Conference•Mar 1, 2023•4 citations

Improved generalized successive cancellation list flip decoder of polar codes with fast decoding of special nodes

Fedor I. Ivanov, Valerii Morishnik, Evgenii A. Krouk

In this paper, an improvement for SC list flip (SCL-Flip) decoding is presented for polar codes. A novel bit-selection metric for critical set (set of information symbols of polar codes being flipped during additional decoding attempts) based on path metric of successive cancellation list (SCL) decoding is suggested. With the proposed metric, the improved SCL scheme based on special nodes (SN) decoders was developed. This decoder will be denoted by GSCLF. The main idea of the proposed decoder is joint using of two approaches: first one is a fast decoding of special nodes in binary tree representation of polar code (e.g., some special nodes in tree representation of polar code that allow efficient list decoding with low complexity) and the second one is an applying of additional decoding attempts (flips) in the case when initial decoding was erroneous. The simultaneous use of these two approaches results in both a significant reduction in spatial complexity and a significant reduction in the number of computations required for decoding whereas keeping excellent performance. Simulation results presented in this paper allow us to conclude that the computational complexity of the proposed GSCLF decoder is from 66% to 80% smaller than the one of SCL-32 decoder.

Journal of Communications and Networks•Dec 1, 2021•20 citations

Dynamic-SCFlip Decoding of Polar Codes

Ludovic Chandesris, Valentin Savin, David Declercq

This paper proposes a generalization of the recently introduced Successive Cancellation Flip (SCFlip) decoding of polar codes, characterized by a number of extra decoding attempts, where one or several positions are flipped from the standard Successive Cancellation (SC) decoding. To make such an approach effective, we first introduce the concept of higher-order bit-flips, and propose a new metric to determine the bit-flips that are more likely to correct the trajectory of the SC decoding. We then propose a generalized SCFlip decoding algorithm, referred to as Dynamic-SCFlip (D-SCFlip), which dynamically builds a list of candidate bit-flips, while guaranteeing that extra decoding attempts are performed by decreasing probability of success. Simulation results show that D-SCFlip is an effective alternative to SC-List decoding of polar codes, by providing very good error correcting performance, with an average computation complexity close to the one of the SC decoder.

arXiv:1703.04414•Mar 13, 2017•0 citations

An Improved Successive Cancellation List Flip Decoder for Polar Codes Based on Key Sets

Jingyun Bao, Shunjie Lin, Xingcheng Liu

Existing studies have documented that flipping operation can improve the performance of polar codes based on CRC-aided successive cancellation list (CA-SCL) decoding algorithm. However, the introduction of the flips greatly increases the complexity and delay of the decoder as well. In this paper, we analyzed the error distribution in the CA-SCL decoding and proposed a new efficient flipping set, key set, to reduce the complexity of the SCL-Flip decoding by narrowing down the size of the flipping set applicable. Different from the critical set which focuses on rate-1 nodes only, the key set can be constructed dynamically based on the results of the original CA-SCL decoding. In addition, we proposed an order-1 SCL-Flip decoder based on the key set to reduce the decoding complexity. Simulation results showed that the key set has a high accuracy of locating the first error and our proposed algorithm has almost no performance degradation compared with the existing SCL-Flip algorithms while the average complexity is reduced significantly.

International Symposium on Medical Information and Communication Technology•Apr 14, 2021•2 citations
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.
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.
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.
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.
In this paper, an improvement for SC list flip (SCL-Flip) decoding is presented for polar codes. A novel bit-selection metric for critical set (set of information symbols of polar codes being flipped during additional decoding attempts) based on path metric of successive cancellation list (SCL) decoding is suggested. With the proposed metric, the improved SCL scheme based on special nodes (SN) decoders was developed. This decoder will be denoted by GSCLF. The main idea of the proposed decoder is joint using of two approaches: first one is a fast decoding of special nodes in binary tree representation of polar code (e.g., some special nodes in tree representation of polar code that allow efficient list decoding with low complexity) and the second one is an applying of additional decoding attempts (flips) in the case when initial decoding was erroneous. The simultaneous use of these two approaches results in both a significant reduction in spatial complexity and a significant reduction in the number of computations required for decoding whereas keeping excellent performance. Simulation results presented in this paper allow us to conclude that the computational complexity of the proposed GSCLF decoder is from 66% to 80% smaller than the one of SCL-32 decoder.
This paper proposes a generalization of the recently introduced Successive Cancellation Flip (SCFlip) decoding of polar codes, characterized by a number of extra decoding attempts, where one or several positions are flipped from the standard Successive Cancellation (SC) decoding. To make such an approach effective, we first introduce the concept of higher-order bit-flips, and propose a new metric to determine the bit-flips that are more likely to correct the trajectory of the SC decoding. We then propose a generalized SCFlip decoding algorithm, referred to as Dynamic-SCFlip (D-SCFlip), which dynamically builds a list of candidate bit-flips, while guaranteeing that extra decoding attempts are performed by decreasing probability of success. Simulation results show that D-SCFlip is an effective alternative to SC-List decoding of polar codes, by providing very good error correcting performance, with an average computation complexity close to the one of the SC decoder.
Existing studies have documented that flipping operation can improve the performance of polar codes based on CRC-aided successive cancellation list (CA-SCL) decoding algorithm. However, the introduction of the flips greatly increases the complexity and delay of the decoder as well. In this paper, we analyzed the error distribution in the CA-SCL decoding and proposed a new efficient flipping set, key set, to reduce the complexity of the SCL-Flip decoding by narrowing down the size of the flipping set applicable. Different from the critical set which focuses on rate-1 nodes only, the key set can be constructed dynamically based on the results of the original CA-SCL decoding. In addition, we proposed an order-1 SCL-Flip decoder based on the key set to reduce the decoding complexity. Simulation results showed that the key set has a high accuracy of locating the first error and our proposed algorithm has almost no performance degradation compared with the existing SCL-Flip algorithms while the average complexity is reduced significantly.