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• 11 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•4 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•10 citations

Fast Successive-Cancellation List Flip Decoding of Polar Codes

Nghia Doan, Seyyed Ali Hashemi, Warren J. Gross

This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.

arXiv:2109.12239•IEEE Access•Jan 1, 2022•8 citations
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.
This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.