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

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

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

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

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

Fast List Decoding of High-Rate Polar Codes

Yang Lu, Minjian Zhao, Ming Lei +1 more

Due to the ability to provide superior error-correction performance, the successive cancellation list (SCL) algorithm is widely regarded as one of the most promising decoding algorithms for polar codes with short-to-moderate code lengths. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. To reduce the decoding latency, developing tailored fast and efficient list decoding algorithms of specific polar constituent codes (special nodes) is a promising solution. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming to further speedup the SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) nodes and sequence rate one or single-parity-check (SR1/SPC) nodes. In particular, we develop two classes of fast list decoding algorithms for these nodes, where the first class uses a sequential decoding procedure to yield decoding latency that is linear with the list size, and the second further parallelizes the decoding process by pre-determining the redundant candidate paths offline. Simulation results show that the proposed list decoding algorithms are able to achieve up to 70.7% lower decoding latency than state-of-the-art fast SCL decoders, while exhibiting the same error-correction performance.

arXiv:2311.08188•IEEE Transactions on Communications•Jul 12, 2024•7 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.
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.
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.
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 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 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.
Due to the ability to provide superior error-correction performance, the successive cancellation list (SCL) algorithm is widely regarded as one of the most promising decoding algorithms for polar codes with short-to-moderate code lengths. However, the application of SCL decoding in low-latency communication scenarios is limited due to its sequential nature. To reduce the decoding latency, developing tailored fast and efficient list decoding algorithms of specific polar constituent codes (special nodes) is a promising solution. Recently, fast list decoding algorithms are proposed by considering special nodes with low code rates. Aiming to further speedup the SCL decoding, this paper presents fast list decoding algorithms for two types of high-rate special nodes, namely single-parity-check (SPC) nodes and sequence rate one or single-parity-check (SR1/SPC) nodes. In particular, we develop two classes of fast list decoding algorithms for these nodes, where the first class uses a sequential decoding procedure to yield decoding latency that is linear with the list size, and the second further parallelizes the decoding process by pre-determining the redundant candidate paths offline. Simulation results show that the proposed list decoding algorithms are able to achieve up to 70.7% lower decoding latency than state-of-the-art fast SCL decoders, while exhibiting the same error-correction performance.