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

SCAN-BF Decoding of Polar Codes

Xiumin Wang, Heng Liu, Jun Li, Zhijun Zheng, Jinlong He

Published May 7, 2021• 11 citations
Publisher

Abstract

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.

DOI
10.1109/lcomm.2021.3078259

Related papers

Efficient Soft-Cancellation Flip Decoding of Polar Codes

Yangcan Zhou, Zijian Qin, Zhongfeng Wang

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.

IEEE Communications Letters•Jun 27, 2024•1 citation

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

Polar Codes based on Bit Flipping Improved BP Decoding Algorithm

H. Wang, Hong Qin, Ze-sheng FANG +2 more

Polar codes is the only coding scheme in the world that has been proved that the Shannon threshold is reachable. Because of the high time delay caused by the serial characteristic of Successive Cancellation (SC) decoding, the Belief Propagation (BP) decoding has received more attention because of its higher throughput. However, because its decoding performance is not as good as SC decoding, Bit-Flip (BF) decoding is used in BP. Aiming at the inaccurate construction of flip set in current bit flipping decoding, this paper proposes a new bit error rate BP BF (BPF) decoding algorithm, which is used to construct flip set. We also propose rough flip set and fine flip set Concept of flip set. The rough flip set is constructed by the variance of the characteristics of data stability. The range of the flip set is reduced by the difference in bit error rate, that is, the fine flip set. The research results show that the algorithm proposed in this paper is superior to the current best decoding algorithms such as BP, Enhanced BPF (EBPF) and Log Likelihood Ratio BPF (BPF-LLR). At the same time, the number of iterations of the algorithm is significantly reduced compared with other bit-flipping decoding algorithms.

•Jan 1, 2021•0 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

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

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
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.
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 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.
Polar codes is the only coding scheme in the world that has been proved that the Shannon threshold is reachable. Because of the high time delay caused by the serial characteristic of Successive Cancellation (SC) decoding, the Belief Propagation (BP) decoding has received more attention because of its higher throughput. However, because its decoding performance is not as good as SC decoding, Bit-Flip (BF) decoding is used in BP. Aiming at the inaccurate construction of flip set in current bit flipping decoding, this paper proposes a new bit error rate BP BF (BPF) decoding algorithm, which is used to construct flip set. We also propose rough flip set and fine flip set Concept of flip set. The rough flip set is constructed by the variance of the characteristics of data stability. The range of the flip set is reduced by the difference in bit error rate, that is, the fine flip set. The research results show that the algorithm proposed in this paper is superior to the current best decoding algorithms such as BP, Enhanced BPF (EBPF) and Log Likelihood Ratio BPF (BPF-LLR). At the same time, the number of iterations of the algorithm is significantly reduced compared with other bit-flipping decoding algorithms.
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 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.
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.