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:1907.11563 · SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems

Neural Dynamic Successive Cancellation Flip Decoding of Polar Codes

Nghia Doan, Seyyed Ali Hashemi, Furkan Ercan, Thibaud Tonnellier, Warren J. Gross

Published Oct 1, 2019• 12 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/sips47522.2019.9020513

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

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•5 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

Simplified Dynamic SC-Flip Polar Decoding

Furkan Ercan, Thibaud Tonnellier, Nghia Doan +1 more

SC-Flip (SCF) decoding is a low-complexity polar code decoding algorithm alternative to SC-List (SCL) algorithm with small list sizes. To achieve the performance of the SCL algorithm with large list sizes, the Dynamic SC-Flip (DSCF) algorithm was proposed. However, DSCF involves logarithmic and exponential computations that are not suitable for practical hardware implementations. In this work, we propose a simple approximation that replaces the transcendental computations of DSCF decoding. Moreover, we show how to incorporate fast decoding techniques with the DSCF algorithm. With proposed approaches, the computational complexity of DSCF decoding is remarkably reduced while maintaining equivalent decoding performance.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•14 citations

Deep-Learning-Aided Successive-Cancellation Decoding of Polar Codes

Seyyed Ali Hashemi, Nghia Doan, Thibaud Tonnellier +1 more

A deep-learning-aided successive-cancellation list (DL-SCL) decoding algorithm for polar codes is introduced with deep-learning-aided successive-cancellation (DL-SC) decoding being a specific case of it. The DL-SCL decoder works by allowing additional rounds of SCL decoding when the first SCL decoding attempt fails, using a novel bit-flipping metric. The proposed bit-flipping metric exploits the inherent relations between the information bits in polar codes that are represented by a correlation matrix. The correlation matrix is then optimized using emerging deep-learning techniques. Performance results on a polar code of length 128 with 64 information bits concatenated with a 24-bit cyclic redundancy check show that the proposed bit-flipping metric in the proposed DL-SCL decoder requires up to 66% fewer multiplications and up to 36% fewer additions, without any need to perform transcendental functions, and by providing almost the same error-correction performance in comparison with the state of the art.

arXiv:1912.01086•Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2019•11 citations

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
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 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 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.
SC-Flip (SCF) decoding is a low-complexity polar code decoding algorithm alternative to SC-List (SCL) algorithm with small list sizes. To achieve the performance of the SCL algorithm with large list sizes, the Dynamic SC-Flip (DSCF) algorithm was proposed. However, DSCF involves logarithmic and exponential computations that are not suitable for practical hardware implementations. In this work, we propose a simple approximation that replaces the transcendental computations of DSCF decoding. Moreover, we show how to incorporate fast decoding techniques with the DSCF algorithm. With proposed approaches, the computational complexity of DSCF decoding is remarkably reduced while maintaining equivalent decoding performance.
A deep-learning-aided successive-cancellation list (DL-SCL) decoding algorithm for polar codes is introduced with deep-learning-aided successive-cancellation (DL-SC) decoding being a specific case of it. The DL-SCL decoder works by allowing additional rounds of SCL decoding when the first SCL decoding attempt fails, using a novel bit-flipping metric. The proposed bit-flipping metric exploits the inherent relations between the information bits in polar codes that are represented by a correlation matrix. The correlation matrix is then optimized using emerging deep-learning techniques. Performance results on a polar code of length 128 with 64 information bits concatenated with a 24-bit cyclic redundancy check show that the proposed bit-flipping metric in the proposed DL-SCL decoder requires up to 66% fewer multiplications and up to 36% fewer additions, without any need to perform transcendental functions, and by providing almost the same error-correction performance in comparison with the state of the art.
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.