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

Mathematics

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

Desheng Wang, Jihang Yin, Yonggang Xu, Xuan Yang, Qiuwei Xu, Gang Hua

Published Oct 27, 2023• 2 citations
Publisher

Abstract

Polar codes, as the coding scheme for the control channel in fifth-generation mobile communication technology (5G), have attracted widespread attention since their proposal. As a mainstream decoding algorithm for polar codes, the successive cancellation list (SCL) decoder usually improves the error correction performance by increasing the list size, but this method suffers from the problems of high decoding complexity. To address this problem, this paper proposes a layered-search bit-flipping (LS-SCLF) decoding algorithm based on SCL decoding. Firstly, a new flip-bit metric is proposed, which derives a formula to approximate the probability of an error occurring in an information bit. This formula introduces a perturbation parameter to improve the calculation accuracy. Secondly, a compromise scheme for determining the perturbation parameter is proposed. The scheme uses Monte Carlo simulation to determine an optimized parameter for the precise positioning of the first erroneous decoded bit under different decoding conditions. Finally, a layered search strategy is adopted to sequentially search the erroneous decoded bits from the low order to high order, which can correct up to multiple bits at the same time. Simulation results show that the proposed algorithm achieves improved error correction performance with a slight increase in decoding complexity compared to the generalized SCL-Flip (GSCLF) decoding algorithm. This algorithm also achieves a good balance between the error correction performance and decoding complexity.

DOI
10.3390/math11214462

Related papers

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

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

Generalized SCL-Flip Decoding of Polar Codes

Yaoxin Pan, Chung-Hsuan Wang, Yeong-Luh Ueng

In this paper, two improvements for successive cancellation list flip (SCL-Flip) decoding are presented for polar codes. First, a novel bit-selection metric based on path metric (PM) is introduced. With the proposed metric, the improved scheme can have lower complexity and saturate faster than other state-of-the-art decoders. Second, we generalize the SCL-Flip decoding, denoted SCL-Flip-ω, to flip the decision in path competition at most ω times in decoding process. We analyze the frequency of channel-induced error under various circumstances, measure the trade-off between error-correction performance and complexity, and then propose SCL-Flip-2 decoding which is the first SCL-based decoding that allows for multiple bits for flipping to the best of our knowledge. Simulation results reveal that the proposed decoding with a small list size can achieve a better performance than CA-SCL decoding with a large list size while keeping the complexity low.

Globecom•Dec 1, 2020•18 citations

Improved generalized successive cancellation list flip decoder of polar codes with fast decoding of special nodes

Fedor I. Ivanov, Valerii Morishnik, Evgenii A. Krouk

In this paper, an improvement for SC list flip (SCL-Flip) decoding is presented for polar codes. A novel bit-selection metric for critical set (set of information symbols of polar codes being flipped during additional decoding attempts) based on path metric of successive cancellation list (SCL) decoding is suggested. With the proposed metric, the improved SCL scheme based on special nodes (SN) decoders was developed. This decoder will be denoted by GSCLF. The main idea of the proposed decoder is joint using of two approaches: first one is a fast decoding of special nodes in binary tree representation of polar code (e.g., some special nodes in tree representation of polar code that allow efficient list decoding with low complexity) and the second one is an applying of additional decoding attempts (flips) in the case when initial decoding was erroneous. The simultaneous use of these two approaches results in both a significant reduction in spatial complexity and a significant reduction in the number of computations required for decoding whereas keeping excellent performance. Simulation results presented in this paper allow us to conclude that the computational complexity of the proposed GSCLF decoder is from 66% to 80% smaller than the one of SCL-32 decoder.

Journal of Communications and Networks•Dec 1, 2021•20 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

Successive Cancellation List Flip Decoding for eBCH-polar Codes

Wei-Cheng Wang, Meng-Ru Wu, Shan Lu +2 more

The eBCH-polar codes is a powerful way to construct polar codes. With high minimum Hamming distance, it outperforms ordinary Polar codes under successive cancellation list (SCL) decoder. However, the absence of cyclic redundancy check (CRC) bits in eBCH-polar codes makes it challenging to adopt SCL-flip (SCLF) decoding scheme. In this research, we propose a flip scheme activated by a Normalized Path Metric (PM) range and a mismatch criterion, which respectively leverage the properties of SCL decoding and dynamic frozen bits of eBCH-polar codes. This work also improves the selection the flipping bits by modifying metric to account for the structure of dynamic frozen bits and reduce the search space. Based on these modifications, we proposed SCLF-1 and SCLF-2 decoding algorithms for eBCH-polar codes. Simulation results show that both of the proposed decoding schemes achieve superior performance compared to other contemporary decoding algorithms for CRC aided polar (CA-polar) codes, demonstrating enhanced error rates performance within the same decoding attempt.

IEEE Vehicular Technology Conference•Oct 19, 2025•0 citations
Polar codes, as the coding scheme for the control channel in fifth-generation mobile communication technology (5G), have attracted widespread attention since their proposal. As a mainstream decoding algorithm for polar codes, the successive cancellation list (SCL) decoder usually improves the error correction performance by increasing the list size, but this method suffers from the problems of high decoding complexity. To address this problem, this paper proposes a layered-search bit-flipping (LS-SCLF) decoding algorithm based on SCL decoding. Firstly, a new flip-bit metric is proposed, which derives a formula to approximate the probability of an error occurring in an information bit. This formula introduces a perturbation parameter to improve the calculation accuracy. Secondly, a compromise scheme for determining the perturbation parameter is proposed. The scheme uses Monte Carlo simulation to determine an optimized parameter for the precise positioning of the first erroneous decoded bit under different decoding conditions. Finally, a layered search strategy is adopted to sequentially search the erroneous decoded bits from the low order to high order, which can correct up to multiple bits at the same time. Simulation results show that the proposed algorithm achieves improved error correction performance with a slight increase in decoding complexity compared to the generalized SCL-Flip (GSCLF) decoding algorithm. This algorithm also achieves a good balance between the error correction performance and decoding complexity.
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.
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.
In this paper, two improvements for successive cancellation list flip (SCL-Flip) decoding are presented for polar codes. First, a novel bit-selection metric based on path metric (PM) is introduced. With the proposed metric, the improved scheme can have lower complexity and saturate faster than other state-of-the-art decoders. Second, we generalize the SCL-Flip decoding, denoted SCL-Flip-ω, to flip the decision in path competition at most ω times in decoding process. We analyze the frequency of channel-induced error under various circumstances, measure the trade-off between error-correction performance and complexity, and then propose SCL-Flip-2 decoding which is the first SCL-based decoding that allows for multiple bits for flipping to the best of our knowledge. Simulation results reveal that the proposed decoding with a small list size can achieve a better performance than CA-SCL decoding with a large list size while keeping the complexity low.
In this paper, an improvement for SC list flip (SCL-Flip) decoding is presented for polar codes. A novel bit-selection metric for critical set (set of information symbols of polar codes being flipped during additional decoding attempts) based on path metric of successive cancellation list (SCL) decoding is suggested. With the proposed metric, the improved SCL scheme based on special nodes (SN) decoders was developed. This decoder will be denoted by GSCLF. The main idea of the proposed decoder is joint using of two approaches: first one is a fast decoding of special nodes in binary tree representation of polar code (e.g., some special nodes in tree representation of polar code that allow efficient list decoding with low complexity) and the second one is an applying of additional decoding attempts (flips) in the case when initial decoding was erroneous. The simultaneous use of these two approaches results in both a significant reduction in spatial complexity and a significant reduction in the number of computations required for decoding whereas keeping excellent performance. Simulation results presented in this paper allow us to conclude that the computational complexity of the proposed GSCLF decoder is from 66% to 80% smaller than the one of SCL-32 decoder.
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.
The eBCH-polar codes is a powerful way to construct polar codes. With high minimum Hamming distance, it outperforms ordinary Polar codes under successive cancellation list (SCL) decoder. However, the absence of cyclic redundancy check (CRC) bits in eBCH-polar codes makes it challenging to adopt SCL-flip (SCLF) decoding scheme. In this research, we propose a flip scheme activated by a Normalized Path Metric (PM) range and a mismatch criterion, which respectively leverage the properties of SCL decoding and dynamic frozen bits of eBCH-polar codes. This work also improves the selection the flipping bits by modifying metric to account for the structure of dynamic frozen bits and reduce the search space. Based on these modifications, we proposed SCLF-1 and SCLF-2 decoding algorithms for eBCH-polar codes. Simulation results show that both of the proposed decoding schemes achieve superior performance compared to other contemporary decoding algorithms for CRC aided polar (CA-polar) codes, demonstrating enhanced error rates performance within the same decoding attempt.