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 Open Journal of the Communications Society

Complexity-Constrained D-SCFlip Decoding

Anna A. Fominykh, Daria Ustinova, Alexey Frolov, Kirill Shabunov

Published Jan 1, 2026• 0 citations
Publisher

Abstract

Dynamic successive cancellation flip (D-SCFlip) decoding has emerged as a low-complexity alternative to successive cancellation list (SCL) decoding for polar codes, bridging the performance gap between conventional successive cancellation (SC) and SCL decoding. While D-SCFlip enhances SC decoding with adaptive bit-flip capabilities, its practical efficiency remains constrained by several factors, including the rapid growth of the search space with code dimension, lack of spatial error localization, and uniform resource allocation for correcting bit error decisions. This work presents a complexity-constrained D-SCFlip decoding algorithm that leverages segmented cyclic redundancy check (CRC) as a tool for fine-grained complexity budgeting, enabling dynamic allocation of fixed computational resources based on localized error information. First, we adapt the segmented CRC approach to the D-SCFlip context, replacing the global CRC with localized checks across optimally sized segments to constrain the flip search space to specific error regions. Second, we introduce a computational complexity budgeting mechanism that efficiently allocates decoding resources across segments based on their error susceptibility and correction potential. Our contribution also includes rigorous optimization of segment configuration specifically designed for complexity-constrained decoding. Simulation results demonstrate that our approach achieves better block error rate performance compared to conventional D-SCFlip decoding under equivalent worst-case complexity constraints, with gains of 0.05-0.14 dB across various code rates and lengths.

DOI
10.1109/ojcoms.2026.3673859

Related papers

BER Evaluation Based SCFlip Algorithm for Polar Codes Decoding

Xueting Zhang, Yingzhuang Liu, Shaoping Chen

Successive cancellation (SC) decoding of polar codes may bring about error propagation that needs to be mitigated. In this paper, we present a new SC Flipping (SCFlip) decoder, named bit error rate (BER) evaluation based SCFlip (BER-SCFlip), which can accurately target the first error bit and correct it with a high probability. Thus, a high error correction capability and a low decoding complexity can be achieved. First, we propose a new criterion to find out the most suspicious error bit. Those non-frozen bits that have higher decoding BERs derived from log-likelihood-ratios (LLRs) after SC decoding than the corresponding expected ones estimated via Gaussian Approximation (GA), are collected into the flip-bits set. These candidate bits will be flipped one by one according to their SC decoding orderings in extra decoding attempts until the decoded codeword passes cyclic redundancy check (CRC) or a predetermined maximum number of extra attempts is reached. We then propose an extended version of BER-SCFlip, named BER-SCFlip-w with the capability to correct up to w error bits in each extra decoding attempt. By combining our criterion for the flip-bits selection with that of Dynamic SCFlip (D-SCFlip), the proposed BER-SCFlip-w significantly reduces decoding complexity and latency while maintaining the superior error-correction performance close to that of D-SCFlip-w. The simulation results show that the proposed schemes are competitive among existing SCFlip algorithms and could achieve the error-correction performance approaching that of CRC-aided SCL decoding under list size L = 16 while maintaining low complexity.

IEEE Access•Dec 25, 2019•7 citations

An Error Segment Bit-Flip Algorithm for Successive Cancellation List Decoding of Polar Codes

Jing Zhang, Hongbing Qiu, Ling Zhan +1 more

Polar codes have garnered significant attention since they were proposed due to their capacity-achieving properties and their low-complexity decoding process, and they were selected as the coding scheme for the control channel in 5G mobile communication technology. A successive cancellation list (SCL) decoder, aided by a cyclic redundancy check (CRC), performs the competitive error correcting performance for polar codes compared to other sophisticated codes. The SCL-Flip decoding algorithm is proposed to enhance the error correction performance of the SCL. However, the SCL-Flip is hampered by a high decoding complexity due to the necessary selection and sorting process of path metrics (PMs). Additionally, it requires a large number of iterations to achieve a good error correction performance. In this paper, we propose the error segment bit-flip (ES-SCL-Flip) decoding algorithm, a simplified bit-flip approach for the SCL decoder based on analyzing the distributions of the first error bit. Firstly, we construct an index set with a high probability of the first erroneous bit. Second, a bit-flip criterion is introduced to prevent the costly operation of the PM selection and sorting without compromising the error correction performance. Finally, a search strategy is employed that utilizes segmented error indication to target and rectify the initial error segment sequentially. The simulation results demonstrate that the ES-SCL-Flip decoder provides an improved error correction performance with only a minimal increase in decoding complexity compared to the conventional CRC-aided SCL decoder. This algorithm attains a commendable equilibrium between the error correction performance and decoding complexity.

Mathematics•Jul 2, 2024•1 citation

Improved Polar SCL Decoding by Exploiting the Error Correction Capability of CRC

Xijin Liu, Shaohua Wu, Xiao Mei Xu +2 more

Novel successive cancellation list (SCL) decoding schemes of Polar codes by exploiting the error correction (EC) capability of the cyclic redundancy check (CRC) codes are proposed in this paper. Different from the schemes in the literature that only considered the error detection capability of CRC, the proposed schemes aim to improve the performance of CRC-aided Polar decoding to the most by benefiting from the potential EC capability of CRC. Specifically, we first propose a basic decoding scheme, named CRC error-correction-aided successive cancellation list (CRC-EC-SCL) decoding, by introducing the look-up-table-based CRC EC method into the Polar SCL decoding process. Then, based on the basic scheme, we further propose the segmented-CRC-EC-SCL decoding scheme. By segmented-CRC, the information block is divided into multiple segments and each segment is attached with a shorter CRC sequence. By conducting the CRC-EC-aided coding for each of the segments, multiple erroneous bits can be corrected early and error propagation can, thus, be efficiently suppressed. The simulation results show that both of the proposed decoding schemes have a significant performance gain over the classic CRC-EC-SCL decoding scheme. Especially for the segmented-CRC-EC-SCL, the performance gain at a frame error rate of 10−4is about 0.4 dB. Moreover, the average computation complexity of the segmented-CRC-EC-SCL is close to the classic scheme.

IEEE Access•Dec 28, 2018•28 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

Bit-Flip Algorithm for Successive Cancellation List Decoder of Polar Codes

Fengyi Cheng, Aijun Liu, Yingxian Zhang +1 more

A successive cancellation list (SCL) decoder with the assistance of a cyclic redundancy check (CRC) can provide competitive decoding performance for polar codes compared with the state-of-the-art codes. In this paper, we adopt a bit-flip algorithm for the CRC-assisted SCL decoder to further improve the error-correcting performance. We first introduce a new bit-flip criterion for the SCL decoder. To support this criterion, we give the metric to identify the positions that need to be flipped. To verify the superiority of the proposed bit-flip criterion, we also consider a kind of SCL-flip decoder whose criterion is very similar with the existing one and we will prove that its performance is worse than the decoder with the proposed bit-flip criterion. The simulation results show that the decoder with the proposed bit-flip criterion outperforms both the standard CRC-assisted SCL decoder and the existing SCL-based bit-flip decoder.

IEEE Access•Jan 1, 2019•43 citations

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
Dynamic successive cancellation flip (D-SCFlip) decoding has emerged as a low-complexity alternative to successive cancellation list (SCL) decoding for polar codes, bridging the performance gap between conventional successive cancellation (SC) and SCL decoding. While D-SCFlip enhances SC decoding with adaptive bit-flip capabilities, its practical efficiency remains constrained by several factors, including the rapid growth of the search space with code dimension, lack of spatial error localization, and uniform resource allocation for correcting bit error decisions. This work presents a complexity-constrained D-SCFlip decoding algorithm that leverages segmented cyclic redundancy check (CRC) as a tool for fine-grained complexity budgeting, enabling dynamic allocation of fixed computational resources based on localized error information. First, we adapt the segmented CRC approach to the D-SCFlip context, replacing the global CRC with localized checks across optimally sized segments to constrain the flip search space to specific error regions. Second, we introduce a computational complexity budgeting mechanism that efficiently allocates decoding resources across segments based on their error susceptibility and correction potential. Our contribution also includes rigorous optimization of segment configuration specifically designed for complexity-constrained decoding. Simulation results demonstrate that our approach achieves better block error rate performance compared to conventional D-SCFlip decoding under equivalent worst-case complexity constraints, with gains of 0.05-0.14 dB across various code rates and lengths.
Successive cancellation (SC) decoding of polar codes may bring about error propagation that needs to be mitigated. In this paper, we present a new SC Flipping (SCFlip) decoder, named bit error rate (BER) evaluation based SCFlip (BER-SCFlip), which can accurately target the first error bit and correct it with a high probability. Thus, a high error correction capability and a low decoding complexity can be achieved. First, we propose a new criterion to find out the most suspicious error bit. Those non-frozen bits that have higher decoding BERs derived from log-likelihood-ratios (LLRs) after SC decoding than the corresponding expected ones estimated via Gaussian Approximation (GA), are collected into the flip-bits set. These candidate bits will be flipped one by one according to their SC decoding orderings in extra decoding attempts until the decoded codeword passes cyclic redundancy check (CRC) or a predetermined maximum number of extra attempts is reached. We then propose an extended version of BER-SCFlip, named BER-SCFlip-w with the capability to correct up to w error bits in each extra decoding attempt. By combining our criterion for the flip-bits selection with that of Dynamic SCFlip (D-SCFlip), the proposed BER-SCFlip-w significantly reduces decoding complexity and latency while maintaining the superior error-correction performance close to that of D-SCFlip-w. The simulation results show that the proposed schemes are competitive among existing SCFlip algorithms and could achieve the error-correction performance approaching that of CRC-aided SCL decoding under list size L = 16 while maintaining low complexity.
Polar codes have garnered significant attention since they were proposed due to their capacity-achieving properties and their low-complexity decoding process, and they were selected as the coding scheme for the control channel in 5G mobile communication technology. A successive cancellation list (SCL) decoder, aided by a cyclic redundancy check (CRC), performs the competitive error correcting performance for polar codes compared to other sophisticated codes. The SCL-Flip decoding algorithm is proposed to enhance the error correction performance of the SCL. However, the SCL-Flip is hampered by a high decoding complexity due to the necessary selection and sorting process of path metrics (PMs). Additionally, it requires a large number of iterations to achieve a good error correction performance. In this paper, we propose the error segment bit-flip (ES-SCL-Flip) decoding algorithm, a simplified bit-flip approach for the SCL decoder based on analyzing the distributions of the first error bit. Firstly, we construct an index set with a high probability of the first erroneous bit. Second, a bit-flip criterion is introduced to prevent the costly operation of the PM selection and sorting without compromising the error correction performance. Finally, a search strategy is employed that utilizes segmented error indication to target and rectify the initial error segment sequentially. The simulation results demonstrate that the ES-SCL-Flip decoder provides an improved error correction performance with only a minimal increase in decoding complexity compared to the conventional CRC-aided SCL decoder. This algorithm attains a commendable equilibrium between the error correction performance and decoding complexity.
Novel successive cancellation list (SCL) decoding schemes of Polar codes by exploiting the error correction (EC) capability of the cyclic redundancy check (CRC) codes are proposed in this paper. Different from the schemes in the literature that only considered the error detection capability of CRC, the proposed schemes aim to improve the performance of CRC-aided Polar decoding to the most by benefiting from the potential EC capability of CRC. Specifically, we first propose a basic decoding scheme, named CRC error-correction-aided successive cancellation list (CRC-EC-SCL) decoding, by introducing the look-up-table-based CRC EC method into the Polar SCL decoding process. Then, based on the basic scheme, we further propose the segmented-CRC-EC-SCL decoding scheme. By segmented-CRC, the information block is divided into multiple segments and each segment is attached with a shorter CRC sequence. By conducting the CRC-EC-aided coding for each of the segments, multiple erroneous bits can be corrected early and error propagation can, thus, be efficiently suppressed. The simulation results show that both of the proposed decoding schemes have a significant performance gain over the classic CRC-EC-SCL decoding scheme. Especially for the segmented-CRC-EC-SCL, the performance gain at a frame error rate of 10−4is about 0.4 dB. Moreover, the average computation complexity of the segmented-CRC-EC-SCL is close to the classic scheme.
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.
A successive cancellation list (SCL) decoder with the assistance of a cyclic redundancy check (CRC) can provide competitive decoding performance for polar codes compared with the state-of-the-art codes. In this paper, we adopt a bit-flip algorithm for the CRC-assisted SCL decoder to further improve the error-correcting performance. We first introduce a new bit-flip criterion for the SCL decoder. To support this criterion, we give the metric to identify the positions that need to be flipped. To verify the superiority of the proposed bit-flip criterion, we also consider a kind of SCL-flip decoder whose criterion is very similar with the existing one and we will prove that its performance is worse than the decoder with the proposed bit-flip criterion. The simulation results show that the decoder with the proposed bit-flip criterion outperforms both the standard CRC-assisted SCL decoder and the existing SCL-based bit-flip decoder.
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.