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 Error Segment Bit-Flip Algorithm for Successive Cancellation List Decoding of Polar Codes

Jing Zhang, Hongbing Qiu, Ling Zhan, Lili Chen

Published Jul 2, 2024• 1 citation
Publisher

Abstract

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.

DOI
10.3390/math12132072

Related papers

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

Desheng Wang, Jihang Yin, Yonggang Xu +3 more

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.

Mathematics•Oct 27, 2023•2 citations

Bit-Flip Algorithm for Successive Cancellation List Decoder of Polar Codes

Fengyi Cheng, Aijun Liu, Yingxian Zhang +1 more

A successive cancellation list (SCL) decoder with the assistance of a cyclic redundancy check (CRC) can provide competitive decoding performance for polar codes compared with the state-of-the-art codes. In this paper, we adopt a bit-flip algorithm for the CRC-assisted SCL decoder to further improve the error-correcting performance. We first introduce a new bit-flip criterion for the SCL decoder. To support this criterion, we give the metric to identify the positions that need to be flipped. To verify the superiority of the proposed bit-flip criterion, we also consider a kind of SCL-flip decoder whose criterion is very similar with the existing one and we will prove that its performance is worse than the decoder with the proposed bit-flip criterion. The simulation results show that the decoder with the proposed bit-flip criterion outperforms both the standard CRC-assisted SCL decoder and the existing SCL-based bit-flip decoder.

IEEE Access•Jan 1, 2019•41 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

Improved Polar SCL Decoding by Exploiting the Error Correction Capability of CRC

Xijin Liu, Shaohua Wu, Xiao Mei Xu +2 more

Novel successive cancellation list (SCL) decoding schemes of Polar codes by exploiting the error correction (EC) capability of the cyclic redundancy check (CRC) codes are proposed in this paper. Different from the schemes in the literature that only considered the error detection capability of CRC, the proposed schemes aim to improve the performance of CRC-aided Polar decoding to the most by benefiting from the potential EC capability of CRC. Specifically, we first propose a basic decoding scheme, named CRC error-correction-aided successive cancellation list (CRC-EC-SCL) decoding, by introducing the look-up-table-based CRC EC method into the Polar SCL decoding process. Then, based on the basic scheme, we further propose the segmented-CRC-EC-SCL decoding scheme. By segmented-CRC, the information block is divided into multiple segments and each segment is attached with a shorter CRC sequence. By conducting the CRC-EC-aided coding for each of the segments, multiple erroneous bits can be corrected early and error propagation can, thus, be efficiently suppressed. The simulation results show that both of the proposed decoding schemes have a significant performance gain over the classic CRC-EC-SCL decoding scheme. Especially for the segmented-CRC-EC-SCL, the performance gain at a frame error rate of 10−4is about 0.4 dB. Moreover, the average computation complexity of the segmented-CRC-EC-SCL is close to the classic scheme.

IEEE Access•Dec 28, 2018•27 citations

An LLR-Based Segmented Flipped SCL Decoding Algorithm for Polar Codes

Anqi Cao, Li Guo Zhang, Jian Qiao +1 more

Polar codes have attracted significant attention in the field of communication, for the capacity-achieving under binary-input discrete memoryless channels (BDMCs). On the basis of successive cancellation (SC) decoding algorithm, many excellent methods have been developed to improve the decoding performance on short and medium codes. In this paper, an LLR-based segmented flipped successive cancellation list (LLR-based SF-SCL) decoding algorithm is proposed, where the information bits are divided into segments for early bit-flipping and termination. In order to make the unreliable bits evenly distributed in each sub-block, an LLR-based segmentation scheme is applied. Simulation results show that the proposed segmented flipped algorithm is superior to CRC-aided successive cancellation list (CA-SCL) algorithm in the block error rate (BLER) performance, and LLR-based segmentation scheme has better performance compared to uniform segmentation scheme.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 1, 2019•9 citations

An Improved Segmented Flipped Successive Cancellation List Decoder for Polar Codes

Yunlong Peng, Xingcheng Liu, Jingyun Bao

Several studies have documented that segmentation can improve the performance of polar codes based on CRC-aided successive cancellation list (CA-SCL) decoding algorithm. In this paper, we propose a new segmented CA-SCL decoder, referred to as improved segmented flipped successive cancellation list (ISF-SCL) decoder, with a reasonable segmentation strategy and a number of extra flipping attempts. Different from the existing methods, in which the uniform segmentation or LLR based segmentation scheme was adopted, a novel segmentation strategy that we firstly analyzed and proposed is based on the distribution of the correct path elimination. Hence, the segment effectiveness is promoted. In addition, to further improve the error correcting performance, a multi-path flipped strategy is proposed to restore the correct path eliminated from the list. Simulation results show that the performance of the ISF-SCL decoding algorithm is superior to the existing segmented CA-SCL decoding algorithms in the low signal-to-noise ratio regime, while the average computational complexity does not increase significantly.

IEEE International Conference on Computer and Communications (ICCC)•Dec 11, 2020•4 citations
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.
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.
A successive cancellation list (SCL) decoder with the assistance of a cyclic redundancy check (CRC) can provide competitive decoding performance for polar codes compared with the state-of-the-art codes. In this paper, we adopt a bit-flip algorithm for the CRC-assisted SCL decoder to further improve the error-correcting performance. We first introduce a new bit-flip criterion for the SCL decoder. To support this criterion, we give the metric to identify the positions that need to be flipped. To verify the superiority of the proposed bit-flip criterion, we also consider a kind of SCL-flip decoder whose criterion is very similar with the existing one and we will prove that its performance is worse than the decoder with the proposed bit-flip criterion. The simulation results show that the decoder with the proposed bit-flip criterion outperforms both the standard CRC-assisted SCL decoder and the existing SCL-based bit-flip decoder.
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.
Novel successive cancellation list (SCL) decoding schemes of Polar codes by exploiting the error correction (EC) capability of the cyclic redundancy check (CRC) codes are proposed in this paper. Different from the schemes in the literature that only considered the error detection capability of CRC, the proposed schemes aim to improve the performance of CRC-aided Polar decoding to the most by benefiting from the potential EC capability of CRC. Specifically, we first propose a basic decoding scheme, named CRC error-correction-aided successive cancellation list (CRC-EC-SCL) decoding, by introducing the look-up-table-based CRC EC method into the Polar SCL decoding process. Then, based on the basic scheme, we further propose the segmented-CRC-EC-SCL decoding scheme. By segmented-CRC, the information block is divided into multiple segments and each segment is attached with a shorter CRC sequence. By conducting the CRC-EC-aided coding for each of the segments, multiple erroneous bits can be corrected early and error propagation can, thus, be efficiently suppressed. The simulation results show that both of the proposed decoding schemes have a significant performance gain over the classic CRC-EC-SCL decoding scheme. Especially for the segmented-CRC-EC-SCL, the performance gain at a frame error rate of 10−4is about 0.4 dB. Moreover, the average computation complexity of the segmented-CRC-EC-SCL is close to the classic scheme.
Polar codes have attracted significant attention in the field of communication, for the capacity-achieving under binary-input discrete memoryless channels (BDMCs). On the basis of successive cancellation (SC) decoding algorithm, many excellent methods have been developed to improve the decoding performance on short and medium codes. In this paper, an LLR-based segmented flipped successive cancellation list (LLR-based SF-SCL) decoding algorithm is proposed, where the information bits are divided into segments for early bit-flipping and termination. In order to make the unreliable bits evenly distributed in each sub-block, an LLR-based segmentation scheme is applied. Simulation results show that the proposed segmented flipped algorithm is superior to CRC-aided successive cancellation list (CA-SCL) algorithm in the block error rate (BLER) performance, and LLR-based segmentation scheme has better performance compared to uniform segmentation scheme.
Several studies have documented that segmentation can improve the performance of polar codes based on CRC-aided successive cancellation list (CA-SCL) decoding algorithm. In this paper, we propose a new segmented CA-SCL decoder, referred to as improved segmented flipped successive cancellation list (ISF-SCL) decoder, with a reasonable segmentation strategy and a number of extra flipping attempts. Different from the existing methods, in which the uniform segmentation or LLR based segmentation scheme was adopted, a novel segmentation strategy that we firstly analyzed and proposed is based on the distribution of the correct path elimination. Hence, the segment effectiveness is promoted. In addition, to further improve the error correcting performance, a multi-path flipped strategy is proposed to restore the correct path eliminated from the list. Simulation results show that the performance of the ISF-SCL decoding algorithm is superior to the existing segmented CA-SCL decoding algorithms in the low signal-to-noise ratio regime, while the average computational complexity does not increase significantly.