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

KSII Transactions on Internet and Information Systems

Generalized SCAN Bit-Flipping Decoding Algorithm for Polar Code

Lou Chen, Guo Rui

Published Apr 30, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.3837/tiis.2023.04.014

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

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

Belief Propagation Bit-Flip Decoder for Polar Codes

Yongrun Yu, Zhiwen Pan, Nan Liu +1 more

The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.

IEEE Access•Jan 1, 2019•69 citations

An Improved Multiple Bit-Flipping Successive Cancellation Decoding Algorithm for Polar Codes

Sha Sha, Li Guo Zhang, Yejun He

Although original successive cancellation flip (SCF) decoding of the polar codes can identify the first error position and flip the error, decoding still fails when other errors occur after the corrected error bit. Therefore, the improvement of the block error rate (BLER) performance is limited. In this paper, we present an improved algorithm that can correct multiple error bits, named as improved multiple bit-flipping successive cancellation decoding algorithm. First, multiple sets are constructed by calculating the log likelihood ratio (LLR) of each information bit. Then, a bit is selected and corrected from the first set when original decoding fails; two bits are selected and flipped from the second set when all bits in the first set cannot be successfully decoded; when all bits combinations in the second set are flipped but the output vector still does not match the input vector, three bits are selected and corrected from the third set. Simulation results show that the BLER performance of the improved algorithm is better than that of the successive cancellation list decoding (SCL) decoding algorithm with a list size of L = 8 for N = 256. When N = 1024 and SNR = 3 dB, the BLER performance of improved algorithm is slightly better than that of SCL decoding algorithm with a list size of L = 4.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 21, 2020•1 citation

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

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 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.
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.
The bit-flip method has been successfully applied to the successive cancellation (SC) decoder to improve the block error rate (BLER) performance for polar codes in the finite code length region. However, due to the sequential decoding, the SC decoder inherently suffers from longer decoding latency than that of the belief propagation (BP) decoder with efficient early stopping criterion. It is natural to ask how to perform bit-flip in a polar BP decoder. In this paper, bit-flip is introduced into the BP decoder for polar codes. The idea of critical set (CS), that is, originally proposed by Zhang et al. for identifying unreliable bits in a SC bit-flip decoder, is extended to the BP decoder here. After revealing the relationship between CS and the incorrect BP decoding results, critical set with order ω (CS-ω) is constructed to identify unreliable bit decisions in polar BP decoding. The simulation results demonstrate that compared with the conventional BP decoder, the BLER of the proposed bit-flip decoder can achieve significant signal-to-noise ratio (SNR) gain which is comparable to that of a cyclic redundancy check-aided SC list decoder with a moderate list size. In addition, the decoding latency of the proposed BP bit-flip decoder is only slightly higher than that of the conventional BP decoder in the medium and high SNR regions.
Although original successive cancellation flip (SCF) decoding of the polar codes can identify the first error position and flip the error, decoding still fails when other errors occur after the corrected error bit. Therefore, the improvement of the block error rate (BLER) performance is limited. In this paper, we present an improved algorithm that can correct multiple error bits, named as improved multiple bit-flipping successive cancellation decoding algorithm. First, multiple sets are constructed by calculating the log likelihood ratio (LLR) of each information bit. Then, a bit is selected and corrected from the first set when original decoding fails; two bits are selected and flipped from the second set when all bits in the first set cannot be successfully decoded; when all bits combinations in the second set are flipped but the output vector still does not match the input vector, three bits are selected and corrected from the third set. Simulation results show that the BLER performance of the improved algorithm is better than that of the successive cancellation list decoding (SCL) decoding algorithm with a list size of L = 8 for N = 256. When N = 1024 and SNR = 3 dB, the BLER performance of improved algorithm is slightly better than that of SCL decoding algorithm with a list size of L = 4.
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.
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.