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

Bit Metrics Based on SCLF Decoding Algorithm for Polar Codes

Haifeng Lin, Rui Guo

Published May 31, 2025• 0 citations
Publisher

Abstract

As an indispensable part of cyclic redundancy check aided Successive Cancellation List (CA-SCL) decoding and SCL bit flipping (CA-SCLF) decoding, sort operation increases the complexity of decoding.In order to minimize the quantity of sorting and simplify the complexity of SCLF decoding algorithm, this paper proposes an improved SCLF decoding algorithm, called NSCLF algorithm, which reduces the number of paths involved in sorting by detecting and pruning paths whose bit metric value is less than the set threshold before sorting operations.Meanwhile, pruning paths are dynamically selected according to node states during the flipping process.The flipping path selections are more accurate and the number of flipping correspondingly decreases.The simulation results demonstrate that when SNR is 3dB, the code length and code rate , while maintaining decoding performance comparable to that of traditional CA-SCLF, the sorting operation of our proposed NSCLF is about 93% less than that of traditional CA-SCLF, and the decoding complexity is less than that of traditional CA-SCLF.

DOI
10.3837/tiis.2025.05.017

Related papers

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

An Improved CA-SCL Decoding Algorithm for Polar Code

Yunfei Tai, Kezhen Li, Liang Zhou +2 more

An improved CA-SCL (CRC-Aided Successive Cancellation List) decoding algorithm for Polar codes is proposed in this paper. By introducing the global cyclic redundancy check and local parity check, a lower bit error rate is obtained comparing with the known results. The new algorithm constructs a prune decoding path by the parity check in the local processing. Since the parity check can only detect an odd number of errors, the global CRC is used to increase the error detection ability and the decoding accuracy. The performance of the improved decoding algorithm is better than the known results, especially when the code length is either less than or equal to 512, and the code rate is not greater than 0.5 in case of the signal-to-noise ratio (SNR) higher than 3dB. In particular, when the code length is 256 with code rate of 0.5 and decoding list size of 32 under the condition of bit error rate 10-5on the AWGN channel, the proposed algorithm has around 0.25dB and 0.55dB performance gain comparing with that of the CA-SCL and SCL algorithms, respectively.

International Symposium on Networks, Computers and Communications (ISNCC)•Jul 19, 2022•3 citations

Complete State Critical Set Based SCLF Decoding Algorithm for Polar Codes

Wenjie Dai, Rui Guo

The revised critical set (RCS) used by successive cancellation list flip (SCLF) decoding algorithm only retains the unreliable bits of SC state.So, the bits of information in the RCS are not comprehensive enough.Aiming at this problem, this paper proposed a kind of complete state critical set (CSCS) based SCLF decoding algorithm for polar codes.In order to obtain a more complete flipping set of states, the proposed CSCS is constructed according to different path splitting states after pruning.According to different states of CSCS, hard decision and path metric (PM) correction methods are adopted respectively, to cut off the wrong path and keep the correct path, so as to achieve bit flipping function.Experimental results show that compared with the traditional SCLF decoding algorithm, the performance of complete state SCLF (CS-SCLF) decoding algorithm is improved.At the same time, the average flipping number of flips is reduced without loss of decoding performance.

KSII Transactions on Internet and Information Systems•Dec 31, 2024•0 citations

An Improved Bit-Flipping Based Decoding Algorithm for Polar Codes

Xiao Hu, Shufeng Li, Mingyu Cai

In this paper, we propose three improved bit flipping algorithms in successive cancellation (SC) decoding and successive cancellation list (SCL) decoding. Weighted single-bit flipping successive cancellation (WSFSC) decoding first performs SC decoding on the output sequence, T bits with the smallest product of channel capacity and absolute value of LLR are regarded as unreliable bits. In multi-bit flipping successive cancellation (MFSC) algorithm, the unreliable bits are respectively corrected according to the single-bit flipping and multi-bit flipping rules. In single flipping successive cancellation list (SFSCL) algorithm, by subtracting a large penalty value from the path metric (PM) value of the unreliable bit, the decoding path corresponding to this bit is more likely to be pruned during path screening, so as to realize bit flipping indirectly. Simulation results show that the proposed WSFSC and MFSC algorithm has a gain of 0.3dB compared with the traditional SC algorithm, SFSCL algorithm has a gain of 0.3dB compared with the traditional SCL algorithm.

IEEE International Conference on Control Science and Systems Engineering (ICCSSE)•Jul 30, 2021•2 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

A Tree Pruning Technique for Decoding Complexity Reduction of Polar Codes and PAC Codes

Mohsen Moradi, Amir Mozammel

Sorting operation is one of the main bottlenecks for the successive-cancellation list (SCL) decoding. This paper introduces an improvement to the SCL decoding for polar and pre-transformed polar codes that reduces the number of sorting operations without visible degradation in the code’s error-correction performance. In an SCL decoding with an optimum metric function we show that, on average, the correct branch’s bit-metric value must be equal to the bit-channel capacity, and on the other hand, the average bit-metric value of a wrong branch can be at most zero. This implies that a wrong path’s partial path metric value deviates from the bit-channel capacity’s partial summation. For relatively reliable bit-channels, the bit metric for a wrong branch becomes very large negative number, which enables us to detect and prune such paths. We prove that, for a threshold lower than the bit-channel cutoff rate, the probability of pruning the correct path decreases exponentially by the given threshold. Based on these findings, we presented a pruning technique, and the experimental results demonstrate a substantial decrease in the amount of sorting procedures required for SCL decoding. In the stack algorithm, a similar technique is used to significantly reduce the average number of paths in the stack.

arXiv:2207.11946•IEEE Transactions on Communications•Mar 10, 2023•23 citations
As an indispensable part of cyclic redundancy check aided Successive Cancellation List (CA-SCL) decoding and SCL bit flipping (CA-SCLF) decoding, sort operation increases the complexity of decoding.In order to minimize the quantity of sorting and simplify the complexity of SCLF decoding algorithm, this paper proposes an improved SCLF decoding algorithm, called NSCLF algorithm, which reduces the number of paths involved in sorting by detecting and pruning paths whose bit metric value is less than the set threshold before sorting operations.Meanwhile, pruning paths are dynamically selected according to node states during the flipping process.The flipping path selections are more accurate and the number of flipping correspondingly decreases.The simulation results demonstrate that when SNR is 3dB, the code length and code rate , while maintaining decoding performance comparable to that of traditional CA-SCLF, the sorting operation of our proposed NSCLF is about 93% less than that of traditional CA-SCLF, and the decoding complexity is less than that of traditional CA-SCLF.
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.
An improved CA-SCL (CRC-Aided Successive Cancellation List) decoding algorithm for Polar codes is proposed in this paper. By introducing the global cyclic redundancy check and local parity check, a lower bit error rate is obtained comparing with the known results. The new algorithm constructs a prune decoding path by the parity check in the local processing. Since the parity check can only detect an odd number of errors, the global CRC is used to increase the error detection ability and the decoding accuracy. The performance of the improved decoding algorithm is better than the known results, especially when the code length is either less than or equal to 512, and the code rate is not greater than 0.5 in case of the signal-to-noise ratio (SNR) higher than 3dB. In particular, when the code length is 256 with code rate of 0.5 and decoding list size of 32 under the condition of bit error rate 10-5on the AWGN channel, the proposed algorithm has around 0.25dB and 0.55dB performance gain comparing with that of the CA-SCL and SCL algorithms, respectively.
The revised critical set (RCS) used by successive cancellation list flip (SCLF) decoding algorithm only retains the unreliable bits of SC state.So, the bits of information in the RCS are not comprehensive enough.Aiming at this problem, this paper proposed a kind of complete state critical set (CSCS) based SCLF decoding algorithm for polar codes.In order to obtain a more complete flipping set of states, the proposed CSCS is constructed according to different path splitting states after pruning.According to different states of CSCS, hard decision and path metric (PM) correction methods are adopted respectively, to cut off the wrong path and keep the correct path, so as to achieve bit flipping function.Experimental results show that compared with the traditional SCLF decoding algorithm, the performance of complete state SCLF (CS-SCLF) decoding algorithm is improved.At the same time, the average flipping number of flips is reduced without loss of decoding performance.
In this paper, we propose three improved bit flipping algorithms in successive cancellation (SC) decoding and successive cancellation list (SCL) decoding. Weighted single-bit flipping successive cancellation (WSFSC) decoding first performs SC decoding on the output sequence, T bits with the smallest product of channel capacity and absolute value of LLR are regarded as unreliable bits. In multi-bit flipping successive cancellation (MFSC) algorithm, the unreliable bits are respectively corrected according to the single-bit flipping and multi-bit flipping rules. In single flipping successive cancellation list (SFSCL) algorithm, by subtracting a large penalty value from the path metric (PM) value of the unreliable bit, the decoding path corresponding to this bit is more likely to be pruned during path screening, so as to realize bit flipping indirectly. Simulation results show that the proposed WSFSC and MFSC algorithm has a gain of 0.3dB compared with the traditional SC algorithm, SFSCL algorithm has a gain of 0.3dB compared with the traditional SCL algorithm.
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.
Sorting operation is one of the main bottlenecks for the successive-cancellation list (SCL) decoding. This paper introduces an improvement to the SCL decoding for polar and pre-transformed polar codes that reduces the number of sorting operations without visible degradation in the code’s error-correction performance. In an SCL decoding with an optimum metric function we show that, on average, the correct branch’s bit-metric value must be equal to the bit-channel capacity, and on the other hand, the average bit-metric value of a wrong branch can be at most zero. This implies that a wrong path’s partial path metric value deviates from the bit-channel capacity’s partial summation. For relatively reliable bit-channels, the bit metric for a wrong branch becomes very large negative number, which enables us to detect and prune such paths. We prove that, for a threshold lower than the bit-channel cutoff rate, the probability of pruning the correct path decreases exponentially by the given threshold. Based on these findings, we presented a pruning technique, and the experimental results demonstrate a substantial decrease in the amount of sorting procedures required for SCL decoding. In the stack algorithm, a similar technique is used to significantly reduce the average number of paths in the stack.