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

IEEE Access

Fast Polar Decoding With Successive Cancellation List Creeper Algorithm

Ilya Timokhin, Fedor I. Ivanov

Published Jan 1, 2024• 3 citations
Publisher

Abstract

Polar codes have emerged as a focal point in the field of error-correcting codes, owing to their remarkable capacity-achieving characteristics and their relevance in various modern communication systems. The basic successive cancellation (SC) approach is not optimal to use in terms of the trade-off between performance and decoding complexity. SC-Creeper algorithm performs better with about the same low complexity as the SC version of the algorithm. However, the SC-Creeper algorithm did not have the ability to use the candidate list as a measure to improve performance and refine the search for the true codeword. To compare with successive cancellation list (SCL) approach and the ability to use more computing memory, the SCL-Creeper method was developed, using two additional lists. This method can also be used as a development of Fano algorithms for polar codes (mainly, Fano decoding in polar decoding does not use lists). This paper addresses the challenge of computational complexity in polar code decoding by integrating a list structure with the SC-Creeper algorithm. Building on prior research that introduced the concept of SC-Creeper, the study focuses on enhancing error correction performance while mitigating computational burden. The first chapters describe the polar encoding process and basic decoding technologies, then discuss the basic Creeper algorithm. In the following chapters, the authors describe a modified version of the two-list Creeper approach (that is, the SCL-Creeper version of the algorithm). Extensive simulations and numerical analysis presented in the paper underscore the tangible advantages of this novel decoding strategy. Leveraging the basic list algorithm, renowned for its superior error correction capabilities, the research explores the integration of Creeper to systematically prune unnecessary decoding paths. The resulting SCL-Creeper hybrid approach aims to strike a balance between error correction efficiency and computational complexity. Finally, the optimal selection of parameters for the SCL-Creeper approach and future directions in the research of the list version of the fast Creeper algorithm are discussed.

DOI
10.1109/access.2024.3416826

Related papers

List Decoding of Polar Codes

Mohammad Rowshan, Emanuele Viterbo

To address the weaknesses of successive cancellation (SC) decoding, this chapter explores enhanced algorithms that follow multiple paths in the decoding tree. These decoders, known as successive cancelation list (SCL) decoders, retain the recursive structure of SC decoding while improving its performance by considering several distinct solutions. The chapter delves into both parallel and serial implementations of SCL decoders, highlighting their fundamental structures and trade-offs. It helps the readers to gain an understanding of the fundamental principles behind SC list decoders and learn how to exploit the structural properties of polar codes to enhance decoding efficiency. The SCL decoding algorithm scans the binary tree (in the case of binary codes) by following more than one path at a time. That is, a number of paths are followed in parallel. The chapter review different strategies for additional decoding attempts in an iterative manner for the SC and SCL decoding algorithms.

Wiley eBooks•Oct 27, 2025•1 citation

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•89 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

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

Adaptive Perturbation Enhanced SCL Decoder for Polar Codes

Xianbin Wang, Huazi Zhang, Jiajie Tong +2 more

For polar codes, successive cancellation list (SCL) decoding algorithm significantly improves finite-length performance compared to SC decoding. SCL-flip decoding can further enhance the performance but the gain diminishes as code length increases, due to the difficulty in locating the first error bit position. In this work, we introduce an SCL-perturbation decoding algorithm to address this issue. A basic version of the algorithm introduces small random perturbations to the received symbols before each SCL decoding attempt, and exhibits non-diminishing gain at large block lengths. Its enhanced version adaptively performs random perturbations or directional perturbation on each received symbol according to previous decoding results, and managed to correct more errors with fewer decoding attempts. Extensive simulation results demonstrate stable gains across various code rates, lengths and list sizes. To the best of our knowledge, this is the first SCL enhancement with non-diminishing gains as code length increases, and achieves unprecedented efficiency. With only one additional SCL-$L$ decoding attempt (in total two), the proposed algorithm achieves SCL-$2L$-equivalent performance. Since the gain is obtained without increasing list size, the algorithm is best suited for hardware implementation.

arXiv:2407.03555•Jul 4, 2024•3 citations

A Low Complexity Successive Cancellation List Decoding Algorithm of Polar Codes

Jiansong Miao, Weijie Li, Xuejia Hu +1 more

Polar codes are the first provably capacity-achieving novel channel codes. Successive cancellation list (SCL) decoding algorithm has a performance close to maximum-likelihood decoding when code length is finite, though the complexity is high. To reduce the complexity of SCL, a partial path expansion with segmented check and pruning SCL (PPE-SCP-SCL) algorithm is proposed in this paper. Based on the successive decoding structure, if the decoding result of a bit is judged to be reliable enough, then a hard decision is made directly and no path expansion is necessary. Moreover, several parity-check points are introduced to perform segmented parity-check during the decoding process, and if the check fails, the current path is directly abandoned. The rationality of the operations is theoretically verified, and numerical simulations also verify that the proposed algorithm can significantly reduce the complexity of decoding with trivial loss of error performance.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 9, 2020•0 citations
Polar codes have emerged as a focal point in the field of error-correcting codes, owing to their remarkable capacity-achieving characteristics and their relevance in various modern communication systems. The basic successive cancellation (SC) approach is not optimal to use in terms of the trade-off between performance and decoding complexity. SC-Creeper algorithm performs better with about the same low complexity as the SC version of the algorithm. However, the SC-Creeper algorithm did not have the ability to use the candidate list as a measure to improve performance and refine the search for the true codeword. To compare with successive cancellation list (SCL) approach and the ability to use more computing memory, the SCL-Creeper method was developed, using two additional lists. This method can also be used as a development of Fano algorithms for polar codes (mainly, Fano decoding in polar decoding does not use lists). This paper addresses the challenge of computational complexity in polar code decoding by integrating a list structure with the SC-Creeper algorithm. Building on prior research that introduced the concept of SC-Creeper, the study focuses on enhancing error correction performance while mitigating computational burden. The first chapters describe the polar encoding process and basic decoding technologies, then discuss the basic Creeper algorithm. In the following chapters, the authors describe a modified version of the two-list Creeper approach (that is, the SCL-Creeper version of the algorithm). Extensive simulations and numerical analysis presented in the paper underscore the tangible advantages of this novel decoding strategy. Leveraging the basic list algorithm, renowned for its superior error correction capabilities, the research explores the integration of Creeper to systematically prune unnecessary decoding paths. The resulting SCL-Creeper hybrid approach aims to strike a balance between error correction efficiency and computational complexity. Finally, the optimal selection of parameters for the SCL-Creeper approach and future directions in the research of the list version of the fast Creeper algorithm are discussed.
To address the weaknesses of successive cancellation (SC) decoding, this chapter explores enhanced algorithms that follow multiple paths in the decoding tree. These decoders, known as successive cancelation list (SCL) decoders, retain the recursive structure of SC decoding while improving its performance by considering several distinct solutions. The chapter delves into both parallel and serial implementations of SCL decoders, highlighting their fundamental structures and trade-offs. It helps the readers to gain an understanding of the fundamental principles behind SC list decoders and learn how to exploit the structural properties of polar codes to enhance decoding efficiency. The SCL decoding algorithm scans the binary tree (in the case of binary codes) by following more than one path at a time. That is, a number of paths are followed in parallel. The chapter review different strategies for additional decoding attempts in an iterative manner for the SC and SCL decoding algorithms.
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.
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.
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.
For polar codes, successive cancellation list (SCL) decoding algorithm significantly improves finite-length performance compared to SC decoding. SCL-flip decoding can further enhance the performance but the gain diminishes as code length increases, due to the difficulty in locating the first error bit position. In this work, we introduce an SCL-perturbation decoding algorithm to address this issue. A basic version of the algorithm introduces small random perturbations to the received symbols before each SCL decoding attempt, and exhibits non-diminishing gain at large block lengths. Its enhanced version adaptively performs random perturbations or directional perturbation on each received symbol according to previous decoding results, and managed to correct more errors with fewer decoding attempts. Extensive simulation results demonstrate stable gains across various code rates, lengths and list sizes. To the best of our knowledge, this is the first SCL enhancement with non-diminishing gains as code length increases, and achieves unprecedented efficiency. With only one additional SCL-LLL decoding attempt (in total two), the proposed algorithm achieves SCL-2L2L2L-equivalent performance. Since the gain is obtained without increasing list size, the algorithm is best suited for hardware implementation.
Polar codes are the first provably capacity-achieving novel channel codes. Successive cancellation list (SCL) decoding algorithm has a performance close to maximum-likelihood decoding when code length is finite, though the complexity is high. To reduce the complexity of SCL, a partial path expansion with segmented check and pruning SCL (PPE-SCP-SCL) algorithm is proposed in this paper. Based on the successive decoding structure, if the decoding result of a bit is judged to be reliable enough, then a hard decision is made directly and no path expansion is necessary. Moreover, several parity-check points are introduced to perform segmented parity-check during the decoding process, and if the check fails, the current path is directly abandoned. The rationality of the operations is theoretically verified, and numerical simulations also verify that the proposed algorithm can significantly reduce the complexity of decoding with trivial loss of error performance.