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 Communications Letters

Efficient Soft-Cancellation Flip Decoding of Polar Codes

Yangcan Zhou, Zijian Qin, Zhongfeng Wang

Published Jun 27, 2024• 1 citation
Publisher

Abstract

The soft-cancellation (SCAN) is a low-complexity soft-output decoding algorithm of polar codes. However, the performance of the SCAN is inferior for short to medium codes. To address this issue, an efficient SCAN Flip decoding algorithm devoted to correct the first erroneous bit in the SCAN is proposed in this letter. The minimum dissemination characteristic of the SCAN decoding is found and analyzed. Besides, an on-the-fly critical set method is proposed to narrow down the range of flip locations. Moreover, before each flipping trial, cleaning of some internal messages is performed to avoid the negative impact of previous wrong message propagation. Numerical results show that the proposed algorithm has better error-correction performance and lower average number of iterations than state-of-the-art SCAN Flip decoding algorithms.

DOI
10.1109/lcomm.2024.3418773

Related papers

SCAN-BF Decoding of Polar Codes

Xiumin Wang, Heng Liu, Jun Li +2 more

In this letter, a new soft cancellation bit-flip (SCAN-BF) decoding algorithm is proposed, reducing errors caused by error propagation. In order to find the bit index with high error probability, a flipping set for soft cancellation (SCAN) decoding algorithm is constructed based on special error distribution regularity. Segmented submatrix check is adopted in the proposed SCAN-BF algorithm to find the subblock where decoding error occurred. Since the search range of finding candidate flipping bits is reduced, the decoding complexity of SCAN-BF algorithm is also reduced. Experimental simulation shows that SCAN-BF decoding obtains a large performance gain in short and medium code lengths.

IEEE Communications Letters•May 7, 2021•11 citations

Generalized SCAN Bit-Flipping Decoding Algorithm for Polar Code

Lou Chen, Guo Rui

In this paper, based on the soft cancellation (SCAN) bit-flipping (SCAN-BF) algorithm, a generalized SCAN bit-flipping (GSCAN-BF-Ω ) decoding algorithm is carried out, where Ω represents the number of bits flipped or corrected at the same time.GSCAN-BF-Ω algorithm corrects the prior information of the code bits and flips the prior information of the unreliable information bits simultaneously to improve the block error rate (BLER) performance.Then, a joint threshold scheme for the GSCAN-BF-2 decoding algorithm is proposed to reduce the average decoding complexity by considering both the bit channel quality and the reliability of the coded bits.Simulation results show that the GSCAN-BF-Ω decoding algorithm reduces the average decoding latency while getting performance gains compared to the common multiple SCAN bit-flipping decoding algorithm.And the GSCAN-BF-2 decoding algorithm with the joint threshold reduces the average decoding latency further by approximately 50% with only a slight performance loss compared to the GSCAN-BF-2 decoding algorithm.

KSII Transactions on Internet and Information Systems•Apr 30, 2023•3 citations

Efficient Soft Cancelation Decoder Architectures for Polar Codes

Jun Ting Lin, Zhiyuan Yan, Zhongfeng Wang

The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jul 12, 2016•12 citations

Hardware implementation of a soft cancellation decoder for polar codes

Guillaume Berhault, Camille Leroux, Christophe Jégo +1 more

Polar Codes can provably achieve the capacity of discrete memoryless channels. In order to make practical, it is necessary to propose efficient hardware decoder architectures. In this paper, the first hardware decoder architecture implementing the Soft-output CANcellation (SCAN) decoding algorithm, is presented. This decoder was implemented on Field Programmable Gate Array (FPGA) devices. The proposed architecture is parametrizable for any number of iterations without adding hardware complexity. The SCAN decoder architecture is compared to another soft-output decoder that implements a Belief Propagation (BP) algorithm. The SCAN decoder can reach a higher throughput than a BP decoder, with a lower memory footprint. Moreover, only one iteration with the SCAN algorithm leads to better decoding performance than 50 iterations of the BP algorithm.

Conference on Design and Architectures for Signal and Image Processing•Sep 1, 2015•15 citations

SCAN List Decoding of Polar Codes

Charles Pillet, Carlo Condo, Valerio Bioglio

In this paper we propose an enhanced soft cancellation (SCAN) decoder for polar codes based on decoding stages permutation. The proposed soft cancellation list (SCANL) decoder runs L independent SCAN decoders, each one relying on a different permuted factor graph. The estimated bits are selected among the L candidates through a dedicated metric provided by the decoders. Furthermore, we introduce an early-termination scheme reducing decoding latency without affecting error correction performance. We investigate the error-correction performance of the proposed scheme under various combinations of number of iterations used, permutation set and early-termination condition. Simulation results show that the proposed SCANL provides similar results when compared with belief propagation list, while having a smaller complexity. Moreover, for large list sizes, SCANL outperforms non-CRC aided successive cancellation list decoding.

arXiv:2001.11283•International Conference on Communications•Jun 1, 2020•29 citations

Combined SCF and SCAN Algorithms for Soft-Output Polar Decoding

Pin-Geng Zeng, Cheng-Hung Dixson Lin, Pei-Hsuan Chen

Polar code has lower coding and decoding requirements, linear complexity, and superior channel performance, so it is proven to be close to the Shannon limit for 5G communication. Successive cancellation (SC) is a polar code decoding method, but its performance has a lot of room for optimization, and flip methodology is one of its basic optimizations. Successive Cancellation Flip (SCF) has a good error correction capability. But due to the repetition of the SC decoder during computation, it has a very long latency. Moreover, SCF output is a hard decision, so it is not capable of soft input and soft output decoder. To allow SCF to be used in more decoding environments, the Hybrid SCF/SCAN proposed in this paper can freely select soft output and hard output, and the proposed architecture can reduce the problem of repeatedly computing SC decode.

International Conference on Consumer Electronics•Jan 6, 2024•0 citations
The soft-cancellation (SCAN) is a low-complexity soft-output decoding algorithm of polar codes. However, the performance of the SCAN is inferior for short to medium codes. To address this issue, an efficient SCAN Flip decoding algorithm devoted to correct the first erroneous bit in the SCAN is proposed in this letter. The minimum dissemination characteristic of the SCAN decoding is found and analyzed. Besides, an on-the-fly critical set method is proposed to narrow down the range of flip locations. Moreover, before each flipping trial, cleaning of some internal messages is performed to avoid the negative impact of previous wrong message propagation. Numerical results show that the proposed algorithm has better error-correction performance and lower average number of iterations than state-of-the-art SCAN Flip decoding algorithms.
In this letter, a new soft cancellation bit-flip (SCAN-BF) decoding algorithm is proposed, reducing errors caused by error propagation. In order to find the bit index with high error probability, a flipping set for soft cancellation (SCAN) decoding algorithm is constructed based on special error distribution regularity. Segmented submatrix check is adopted in the proposed SCAN-BF algorithm to find the subblock where decoding error occurred. Since the search range of finding candidate flipping bits is reduced, the decoding complexity of SCAN-BF algorithm is also reduced. Experimental simulation shows that SCAN-BF decoding obtains a large performance gain in short and medium code lengths.
In this paper, based on the soft cancellation (SCAN) bit-flipping (SCAN-BF) algorithm, a generalized SCAN bit-flipping (GSCAN-BF-Ω ) decoding algorithm is carried out, where Ω represents the number of bits flipped or corrected at the same time.GSCAN-BF-Ω algorithm corrects the prior information of the code bits and flips the prior information of the unreliable information bits simultaneously to improve the block error rate (BLER) performance.Then, a joint threshold scheme for the GSCAN-BF-2 decoding algorithm is proposed to reduce the average decoding complexity by considering both the bit channel quality and the reliability of the coded bits.Simulation results show that the GSCAN-BF-Ω decoding algorithm reduces the average decoding latency while getting performance gains compared to the common multiple SCAN bit-flipping decoding algorithm.And the GSCAN-BF-2 decoding algorithm with the joint threshold reduces the average decoding latency further by approximately 50% with only a slight performance loss compared to the GSCAN-BF-2 decoding algorithm.
The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.
Polar Codes can provably achieve the capacity of discrete memoryless channels. In order to make practical, it is necessary to propose efficient hardware decoder architectures. In this paper, the first hardware decoder architecture implementing the Soft-output CANcellation (SCAN) decoding algorithm, is presented. This decoder was implemented on Field Programmable Gate Array (FPGA) devices. The proposed architecture is parametrizable for any number of iterations without adding hardware complexity. The SCAN decoder architecture is compared to another soft-output decoder that implements a Belief Propagation (BP) algorithm. The SCAN decoder can reach a higher throughput than a BP decoder, with a lower memory footprint. Moreover, only one iteration with the SCAN algorithm leads to better decoding performance than 50 iterations of the BP algorithm.
In this paper we propose an enhanced soft cancellation (SCAN) decoder for polar codes based on decoding stages permutation. The proposed soft cancellation list (SCANL) decoder runs L independent SCAN decoders, each one relying on a different permuted factor graph. The estimated bits are selected among the L candidates through a dedicated metric provided by the decoders. Furthermore, we introduce an early-termination scheme reducing decoding latency without affecting error correction performance. We investigate the error-correction performance of the proposed scheme under various combinations of number of iterations used, permutation set and early-termination condition. Simulation results show that the proposed SCANL provides similar results when compared with belief propagation list, while having a smaller complexity. Moreover, for large list sizes, SCANL outperforms non-CRC aided successive cancellation list decoding.
Polar code has lower coding and decoding requirements, linear complexity, and superior channel performance, so it is proven to be close to the Shannon limit for 5G communication. Successive cancellation (SC) is a polar code decoding method, but its performance has a lot of room for optimization, and flip methodology is one of its basic optimizations. Successive Cancellation Flip (SCF) has a good error correction capability. But due to the repetition of the SC decoder during computation, it has a very long latency. Moreover, SCF output is a hard decision, so it is not capable of soft input and soft output decoder. To allow SCF to be used in more decoding environments, the Hybrid SCF/SCAN proposed in this paper can freely select soft output and hard output, and the proposed architecture can reduce the problem of repeatedly computing SC decode.