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 International Symposium on Information Theory (ISIT)

Simplified Successive-Cancellation List decoding of polar codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

Published Jul 1, 2016• 72 citations
Publisher

Abstract

The Successive-Cancellation List (SCL) decoding algorithm is one of the most promising approaches towards practical polar code decoding. It is able to provide a good trade-off between error-correction performance and complexity, tunable through the size of the list. In this paper, we show that in the conventional formulation of SCL, there are redundant calculations which do not need to be performed in the course of the algorithm. We simplify SCL by removing these redundant calculations and prove that the proposed simplified SCL and the conventional SCL algorithms are equivalent. The simplified SCL algorithm is valid for any code and can reduce the time-complexity of SCL without affecting the space complexity.

DOI
10.1109/isit.2016.7541412

Related papers

An Improved Simplified Successive-Cancellation List Decoding of Polar Codes

Yu Guo, Shufeng Li, Mingyu Cai

The Successive-Cancellation List (SCL) algorithm is a popular decoding algorithm for polar codes. Although SCL algorithm overcomes the error propagation problem in polar codes decoding, the improvement of error correction performance needs to pay the price of high latency. To solve this problem, a simplified SCL (SSCL) algorithm is proposed. For some special nodes, the SSCL algorithm can calculate path metric (PM) without traversing the decoding tree to achieve direct decoding, reducing the latency and complexity of decoding. In this paper, a new special node has been discovered, it is also possible to calculate PM without traversing decoding tree. Based on this, we propose an improved SSCL algorithm. Simulation results show that improved SSCL algorithm can further reduce the decoding latency and the loss of error-correction performance is negligible.

IEEE International Conference on Computer and Communication Engineering Technology (CCET)•Aug 19, 2022•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•86 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

Partitioned successive-cancellation list decoding of polar codes

Seyyed Ali Hashemi, Alexios Balatsoukas‐Stimming, Pascal Giard +2 more

Successive-cancellation list (SCL) decoding is an algorithm that provides very good error-correction performance for polar codes. However, its hardware implementation requires a large amount of memory, mainly to store intermediate results. In this paper, a partitioned SCL algorithm is proposed to reduce the large memory requirements of the conventional SCL algorithm. The decoder tree is broken into partitions that are decoded separately. We show that with careful selection of list sizes and number of partitions, the proposed algorithm can outperform conventional SCL while requiring less memory.

arXiv:1512.03128•IEEE International Conference on Acoustics Speech and Signal Processing•Mar 1, 2016•48 citations

Improved Adaptive Successive Cancellation List Decoding of Polar Codes

Xiumin Wang, Jinlong He, Jun Li +3 more

Although the adaptive successive cancellation list (AD-SCL) algorithm and the segmented-CRC adaptive successive cancellation list (SCAD-SCL) algorithm based on the cyclic redundancy check (CRC) can greatly reduce the computational complexity of the successive cancellation list (SCL) algorithm, these two algorithms discard the previous decoding result and re-decode by increasing L, where L is the size of list. When CRC fails, these two algorithms waste useful information from the previous decoding. In this paper, a simplified adaptive successive cancellation list (SAD-SCL) is proposed. Before the re-decoding of updating value L each time, SAD-SCL uses the existing log likelihood ratio (LLR) information to locate the range of burst error bits, and then re-decoding starts at the incorrect bit with the smallest index in this range. Moreover, when the segmented information sequence cannot get the correct result of decoding, the SAD-SCL algorithm uses SC decoding to complete the decoding of the subsequent segmentation information sequence. Furthermore, its decoding performance is almost the same as that of the subsequent segmentation information sequence using the AD-SCL algorithm. The simulation results show that the SAD-SCL algorithm has lower computational complexity than AD-SCL and SCAD-SCL with negligible loss of performance.

Entropy•Sep 17, 2019•3 citations

Successive Cancellation Priority Decoding of Polar Codes

Di Guan, Kai Niu, Chao Dong +1 more

The successive cancellation list (SCL) decoding of polar codes can achieve a performance close to that of maximum-likelihood decoding. Nevertheless, a large list size results in high-computational complexity. In this paper, a successive cancellation priority (SCP) decoding algorithm is proposed to reduce the time complexity. The SCP decoder performs a priority-first decoding, which is composed of a priority queue and a trellis. During the SCP decoding, the priority queue interacts with the trellis iteratively. Conceptually, the priority queue stores the priority information and guides the extension of the candidate path. The trellis calculates and stores the intermediate results. Since most of the unnecessary path extensions are avoided by using the priority queue, the time complexity of the SCP decoder is much lower than that of the standard SCL decoder. Then, a quantized priority queue is introduced to avoid the comparison operations in the path selection and to simplify the SCP decoder. Furthermore, we prove that the path extension of the SCP decoder is equivalent to the extension of the most reliable paths of the standard SCL decoder. Thus, the SCP decoder can achieve the same decoding performance as that of the standard SCL decoder.

IEEE Access•Jan 1, 2019•9 citations
The Successive-Cancellation List (SCL) decoding algorithm is one of the most promising approaches towards practical polar code decoding. It is able to provide a good trade-off between error-correction performance and complexity, tunable through the size of the list. In this paper, we show that in the conventional formulation of SCL, there are redundant calculations which do not need to be performed in the course of the algorithm. We simplify SCL by removing these redundant calculations and prove that the proposed simplified SCL and the conventional SCL algorithms are equivalent. The simplified SCL algorithm is valid for any code and can reduce the time-complexity of SCL without affecting the space complexity.
The Successive-Cancellation List (SCL) algorithm is a popular decoding algorithm for polar codes. Although SCL algorithm overcomes the error propagation problem in polar codes decoding, the improvement of error correction performance needs to pay the price of high latency. To solve this problem, a simplified SCL (SSCL) algorithm is proposed. For some special nodes, the SSCL algorithm can calculate path metric (PM) without traversing the decoding tree to achieve direct decoding, reducing the latency and complexity of decoding. In this paper, a new special node has been discovered, it is also possible to calculate PM without traversing decoding tree. Based on this, we propose an improved SSCL algorithm. Simulation results show that improved SSCL algorithm can further reduce the decoding latency and the loss of error-correction performance is negligible.
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 list (SCL) decoding is an algorithm that provides very good error-correction performance for polar codes. However, its hardware implementation requires a large amount of memory, mainly to store intermediate results. In this paper, a partitioned SCL algorithm is proposed to reduce the large memory requirements of the conventional SCL algorithm. The decoder tree is broken into partitions that are decoded separately. We show that with careful selection of list sizes and number of partitions, the proposed algorithm can outperform conventional SCL while requiring less memory.
Although the adaptive successive cancellation list (AD-SCL) algorithm and the segmented-CRC adaptive successive cancellation list (SCAD-SCL) algorithm based on the cyclic redundancy check (CRC) can greatly reduce the computational complexity of the successive cancellation list (SCL) algorithm, these two algorithms discard the previous decoding result and re-decode by increasing L, where L is the size of list. When CRC fails, these two algorithms waste useful information from the previous decoding. In this paper, a simplified adaptive successive cancellation list (SAD-SCL) is proposed. Before the re-decoding of updating value L each time, SAD-SCL uses the existing log likelihood ratio (LLR) information to locate the range of burst error bits, and then re-decoding starts at the incorrect bit with the smallest index in this range. Moreover, when the segmented information sequence cannot get the correct result of decoding, the SAD-SCL algorithm uses SC decoding to complete the decoding of the subsequent segmentation information sequence. Furthermore, its decoding performance is almost the same as that of the subsequent segmentation information sequence using the AD-SCL algorithm. The simulation results show that the SAD-SCL algorithm has lower computational complexity than AD-SCL and SCAD-SCL with negligible loss of performance.
The successive cancellation list (SCL) decoding of polar codes can achieve a performance close to that of maximum-likelihood decoding. Nevertheless, a large list size results in high-computational complexity. In this paper, a successive cancellation priority (SCP) decoding algorithm is proposed to reduce the time complexity. The SCP decoder performs a priority-first decoding, which is composed of a priority queue and a trellis. During the SCP decoding, the priority queue interacts with the trellis iteratively. Conceptually, the priority queue stores the priority information and guides the extension of the candidate path. The trellis calculates and stores the intermediate results. Since most of the unnecessary path extensions are avoided by using the priority queue, the time complexity of the SCP decoder is much lower than that of the standard SCL decoder. Then, a quantized priority queue is introduced to avoid the comparison operations in the path selection and to simplify the SCP decoder. Furthermore, we prove that the path extension of the SCP decoder is equivalent to the extension of the most reliable paths of the standard SCL decoder. Thus, the SCP decoder can achieve the same decoding performance as that of the standard SCL decoder.