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

International Wireless Communications and Mobile Computing Conference (IWCMC)

An Optimized Successive Cancellation List Decoder for Polar Codes Combined with Critical Set

Xiuqi Hu, Huiling Hou, Xinglong Jiang, Siyue Sun, Guang Liang, Shuai Han

Published May 30, 2022• 2 citations
Publisher

Abstract

Successive cancellation list (SCL) decoder has high decoding performance but also require great resource consumption. In this paper, we combine the SCL decoder and the critical set to form a new decoder, which can stably reduce the number of operations by 65%$\sim$70% and maintain similar decoding performance to SCL decoder. The reduction in resource consumption depends only on the arrangement of unfrozen bit sequences, not on the quality of the channel. We also propose to combine this new decoder with adaptive algorithms. In this way, the decoding performance of the decoder can be improved beyond SCL decoders without increasing resource consumption.

DOI
10.1109/iwcmc55113.2022.9824965

Related papers

A Split-Reduced Successive Cancellation List Decoder for Polar Codes

Zhaoyang Zhang, Liang Zhang, Xianbin Wang +2 more

This paper focuses on low complexity successive cancellation list (SCL) decoding of polar codes. In particular, using the fact that splitting may be unnecessary when the reliability of decoding the unfrozen bit is sufficiently high, a novel splitting rule is proposed. Based on this rule, it is conjectured that, if the correct path survives at some stage, it tends to survive till termination without splitting with high probability. On the other hand, the incorrect paths are more likely to split at the following stages. Motivated by these observations, a simple counter that counts the successive number of stages without splitting is introduced for each decoding path to facilitate the identification of correct and incorrect paths. Specifically, any path with counter value larger than a predefined threshold ω is deemed to be the correct path, which will survive at the decoding stage, while other paths with counter value smaller than the threshold will be pruned, thereby reducing the decoding complexity. Furthermore, it is proved that there exists a unique unfrozen bit uN-K1+1, after which the successive cancellation decoder achieves the same error performance as the maximum likelihood decoder if all the prior unfrozen bits are correctly decoded, which enables further complexity reduction. Simulation results demonstrate that the proposed low complexity SCL decoder attains performance similar to that of the conventional SCL decoder, while achieving substantial complexity reduction.

arXiv:1511.02150•IEEE Journal on Selected Areas in Communications•Nov 30, 2015•75 citations

Fast Simplified Successive-Cancellation List Decoding of Polar Codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time- steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.

IEEE Wireless Communications and Networking Conference Workshops (WCNCW)•Mar 1, 2017•86 citations

An Improved Successive Cancellation List Flip Decoder for Polar Codes Based on Key Sets

Jingyun Bao, Shunjie Lin, Xingcheng Liu

Existing studies have documented that flipping operation can improve the performance of polar codes based on CRC-aided successive cancellation list (CA-SCL) decoding algorithm. However, the introduction of the flips greatly increases the complexity and delay of the decoder as well. In this paper, we analyzed the error distribution in the CA-SCL decoding and proposed a new efficient flipping set, key set, to reduce the complexity of the SCL-Flip decoding by narrowing down the size of the flipping set applicable. Different from the critical set which focuses on rate-1 nodes only, the key set can be constructed dynamically based on the results of the original CA-SCL decoding. In addition, we proposed an order-1 SCL-Flip decoder based on the key set to reduce the decoding complexity. Simulation results showed that the key set has a high accuracy of locating the first error and our proposed algorithm has almost no performance degradation compared with the existing SCL-Flip algorithms while the average complexity is reduced significantly.

International Symposium on Medical Information and Communication Technology•Apr 14, 2021•2 citations

Fast Simplified Successive-Cancellation List Decoding of Polar Codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time-steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.

arXiv:1701.08126•Jan 27, 2017•4 citations

Critical-Set-Aided Multi-Bit Successive Cancellation List Decoders for Polar Codes

Shan Chen, Shan Cao, Limin Jiang +1 more

The utilization of 5G and beyond wireless communication systems in autonomous driving and remote healthcare has necessitated the development of channel codes with high reliability and low latency. The multi-bit successive cancellation list (MSCL) parallel decoding of polar codes has shown great potential in the decrease of decoding latency while maintaining a high level of reliability, in comparison to the conventional successive cancellation list (SCL) decoding. However, the complexity of decoding path sorting increases exponentially with the increase of parallelism, which poses significant limitations to the improvement of parallelism. To address this issue, this paper proposes a critical set aided multi-bit successive cancellation list (CS-MSCL) decoding algorithm. Critical sets are introduced to the MSCL decoding, which prunes less reliable candidate paths to guarantee high decoding performance. Meanwhile, dynamic configuration is allowed according to the application scenario to make a good balance in decoding latency, error correction performance, and algorithmic complexity. Simulation results demonstrate that the algorithmic complexity decreased by 1099.04% compared to MSCL decoding for (1024, 512) polar codes when the degree of parallelism is 8 and the list size is 16.

International Conference on Future Communications and Networks (FCN)•Dec 17, 2023•0 citations

Low-Complexity Successive Cancellation List Decoding of Polar Codes Based on Path Metric

Xiaodong Liu, Ce Sun, Wei Tang

Successive cancellation (SC) decoding algorithm and successive cancellation list (SCL) decoding algorithm are two common decoding methods for polar codes. The SC decoding algorithm has low complexity, but in its decoding process, the bits with small channel indices are used to assist the decoding of the bits with large channel indices. Therefore, the bit being decoded depends on the bits that have already been decoded which causes error propagation. On the basis of SC decoding, the SCL decoding algorithm overcomes the problem of error propagation by widening the path search width and retaining multiple paths at the same time in the decoding process. However, the complexity of SCL decoding is higher than that of SC decoding. Without changing the performance of the SCL decoding algorithm, we propose a low-complexity SCL decoding algorithm based on path metric (PM). After the last frozen bit is decoded, the path with the smallest PM is selected, and the subsequent nodes adopt SC decoding. Through this combination of SCL decoding and SC decoding, the complexity of the SCL decoding algorithm can be effectively reduced while the SCL decoding performance remains unchanged, especially in the case of high code rates.

IEEE International Conference on Communication Technology (ICCT)•Oct 13, 2021•3 citations
Successive cancellation list (SCL) decoder has high decoding performance but also require great resource consumption. In this paper, we combine the SCL decoder and the critical set to form a new decoder, which can stably reduce the number of operations by 65%∼\sim∼70% and maintain similar decoding performance to SCL decoder. The reduction in resource consumption depends only on the arrangement of unfrozen bit sequences, not on the quality of the channel. We also propose to combine this new decoder with adaptive algorithms. In this way, the decoding performance of the decoder can be improved beyond SCL decoders without increasing resource consumption.
This paper focuses on low complexity successive cancellation list (SCL) decoding of polar codes. In particular, using the fact that splitting may be unnecessary when the reliability of decoding the unfrozen bit is sufficiently high, a novel splitting rule is proposed. Based on this rule, it is conjectured that, if the correct path survives at some stage, it tends to survive till termination without splitting with high probability. On the other hand, the incorrect paths are more likely to split at the following stages. Motivated by these observations, a simple counter that counts the successive number of stages without splitting is introduced for each decoding path to facilitate the identification of correct and incorrect paths. Specifically, any path with counter value larger than a predefined threshold ω is deemed to be the correct path, which will survive at the decoding stage, while other paths with counter value smaller than the threshold will be pruned, thereby reducing the decoding complexity. Furthermore, it is proved that there exists a unique unfrozen bit uN-K1+1, after which the successive cancellation decoder achieves the same error performance as the maximum likelihood decoder if all the prior unfrozen bits are correctly decoded, which enables further complexity reduction. Simulation results demonstrate that the proposed low complexity SCL decoder attains performance similar to that of the conventional SCL decoder, while achieving substantial complexity reduction.
Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time- steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.
Existing studies have documented that flipping operation can improve the performance of polar codes based on CRC-aided successive cancellation list (CA-SCL) decoding algorithm. However, the introduction of the flips greatly increases the complexity and delay of the decoder as well. In this paper, we analyzed the error distribution in the CA-SCL decoding and proposed a new efficient flipping set, key set, to reduce the complexity of the SCL-Flip decoding by narrowing down the size of the flipping set applicable. Different from the critical set which focuses on rate-1 nodes only, the key set can be constructed dynamically based on the results of the original CA-SCL decoding. In addition, we proposed an order-1 SCL-Flip decoder based on the key set to reduce the decoding complexity. Simulation results showed that the key set has a high accuracy of locating the first error and our proposed algorithm has almost no performance degradation compared with the existing SCL-Flip algorithms while the average complexity is reduced significantly.
Polar codes are capacity achieving error correcting codes that can be decoded through the successive-cancellation algorithm. To improve its error-correction performance, a list-based version called successive-cancellation list (SCL) has been proposed in the past, that however substantially increases the number of time-steps in the decoding process. The simplified SCL (SSCL) decoding algorithm exploits constituent codes within the polar code structure to greatly reduce the required number of time-steps without introducing any error-correction performance loss. In this paper, we propose a faster decoding approach to decode one of these constituent codes, the Rate-1 node. We use this Rate-1 node decoder to develop Fast-SSCL. We demonstrate that only a list-size-bound number of bits needs to be estimated in Rate-1 nodes and Fast-SSCL exactly matches the error-correction performance of SCL and SSCL. This technique can potentially greatly reduce the total number of time-steps needed for polar codes decoding: analysis on a set of case studies show that Fast-SSCL has a number of time-steps requirement that is up to 66.6% lower than SSCL and 88.1% lower than SCL.
The utilization of 5G and beyond wireless communication systems in autonomous driving and remote healthcare has necessitated the development of channel codes with high reliability and low latency. The multi-bit successive cancellation list (MSCL) parallel decoding of polar codes has shown great potential in the decrease of decoding latency while maintaining a high level of reliability, in comparison to the conventional successive cancellation list (SCL) decoding. However, the complexity of decoding path sorting increases exponentially with the increase of parallelism, which poses significant limitations to the improvement of parallelism. To address this issue, this paper proposes a critical set aided multi-bit successive cancellation list (CS-MSCL) decoding algorithm. Critical sets are introduced to the MSCL decoding, which prunes less reliable candidate paths to guarantee high decoding performance. Meanwhile, dynamic configuration is allowed according to the application scenario to make a good balance in decoding latency, error correction performance, and algorithmic complexity. Simulation results demonstrate that the algorithmic complexity decreased by 1099.04% compared to MSCL decoding for (1024, 512) polar codes when the degree of parallelism is 8 and the list size is 16.
Successive cancellation (SC) decoding algorithm and successive cancellation list (SCL) decoding algorithm are two common decoding methods for polar codes. The SC decoding algorithm has low complexity, but in its decoding process, the bits with small channel indices are used to assist the decoding of the bits with large channel indices. Therefore, the bit being decoded depends on the bits that have already been decoded which causes error propagation. On the basis of SC decoding, the SCL decoding algorithm overcomes the problem of error propagation by widening the path search width and retaining multiple paths at the same time in the decoding process. However, the complexity of SCL decoding is higher than that of SC decoding. Without changing the performance of the SCL decoding algorithm, we propose a low-complexity SCL decoding algorithm based on path metric (PM). After the last frozen bit is decoded, the path with the smallest PM is selected, and the subsequent nodes adopt SC decoding. Through this combination of SCL decoding and SC decoding, the complexity of the SCL decoding algorithm can be effectively reduced while the SCL decoding performance remains unchanged, especially in the case of high code rates.