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

arXiv:1511.02150 · IEEE Journal on Selected Areas in Communications

A Split-Reduced Successive Cancellation List Decoder for Polar Codes

Zhaoyang Zhang, Liang Zhang, Xianbin Wang, Caijun Zhong, H. Vincent Poor

Published Nov 30, 2015• 77 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/jsac.2015.2504321

Related papers

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

A Low-Latency Successive Cancellation Hybrid Decoder for Convolutional Polar Codes

Yu Wang, Shikai Qiu, Lirui Chen +4 more

By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.

IEEE International Conference on Acoustics Speech and Signal Processing•Apr 9, 2020•1 citation

Simplified Path Split Strategy for SCL Decoding Algorithm with Lower Latency

Yiling Peng, Huihui Wu, Pingping Chen +1 more

This work focuses on further reducing the decoding latency of the successive cancellation list (SCL) algorithm for polar codes, considering the fact that some path splitting may be unnecessary if a bit is reliable during the transmission. Specifically, during the node-wise SCL decoding progress, only unreliable bits need to conduct path clone, leading to the reduction of the number of path splitting and the decoding latency. On this basis, this paper proposes an improved simplified SCL (SSCL) algorithm and an improved Fast-SCL (FSCL) algorithm, for low-latency polar decoding. Simulation results performed on a (4096, 2048) polar code show that the improved SSCL algorithm reduces the decoding latency by around 44.7% when L = 4, and by 62.8% when L = 8, respectively. Moreover, the improved FSCL algorithm achieves a reduction of decoding latency by about 37.3% when L = 8, for a (4096, 3840) polar code.

Wireless Telecommunications Symposium•Apr 6, 2022•2 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 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

Low-complexity Successive Cancellation List Decoding for Polar Codes based on SPRT

Wenpeng Li, Lining Du, Yuevun Chen

Successive cancellation list (SCL) decoding algorithm for polar codes is one of the best decoding algorithms due to its excellent decoding performance. The decoding complexity of conventional SCL decoding algorithm is O(LN log N). The decoding complexity will increase as the size of the list increases. To solve this problem, we introduce an improved SCL decoding algorithm based on the sequential probability ratio test (SPRT). The proposed algorithm use double thresholds to decode the polar codes instead of single threshold decision used by the conventional SCL algorithm. Numerical results have shown that for (1024, 512) polar code, the proposed SPRT-SCL decoder can achieve a reduction in decoding complexity, and keep the similar decoding performance compared with conventional SCL decoder.

Wireless and Optical Communications Conference•May 1, 2019•2 citations
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 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.
By adopting successive cancellation list decoding (SCL), polar codes demonstrate competitive error correction performance over LDPC and Turbo codes. However, SCL decoding suffers from high computational complexity and long decoding latency, especially when the list size is very large. Successive cancellation flip (SCF), as another decoding algorithm that can achieve high error correction performance, has a complexity that is close to that of successive cancellation (SC) decoding. With the observation that SCL and SCF decoding are similar at giving more chances to inspect possible codewords simultaneously or sequentially, a novel hybrid decoder is proposed in this paper, which essentially combines the ideas of SCF and SCL decoders. Moreover, in order to compensate for the degradation of performance caused by the reduction of path splitting and further reduce the decoding latency, the convolutional polar codes are adopted with a designed bit-flipping set. Simulation results demonstrate that the proposed decoder achieves the reduction of decoding latency while attaining better performance than conventional CRC-aided SCL decoder.
This work focuses on further reducing the decoding latency of the successive cancellation list (SCL) algorithm for polar codes, considering the fact that some path splitting may be unnecessary if a bit is reliable during the transmission. Specifically, during the node-wise SCL decoding progress, only unreliable bits need to conduct path clone, leading to the reduction of the number of path splitting and the decoding latency. On this basis, this paper proposes an improved simplified SCL (SSCL) algorithm and an improved Fast-SCL (FSCL) algorithm, for low-latency polar decoding. Simulation results performed on a (4096, 2048) polar code show that the improved SSCL algorithm reduces the decoding latency by around 44.7% when L = 4, and by 62.8% when L = 8, respectively. Moreover, the improved FSCL algorithm achieves a reduction of decoding latency by about 37.3% when L = 8, for a (4096, 3840) polar code.
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.
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.
Successive cancellation list (SCL) decoding algorithm for polar codes is one of the best decoding algorithms due to its excellent decoding performance. The decoding complexity of conventional SCL decoding algorithm is O(LN log N). The decoding complexity will increase as the size of the list increases. To solve this problem, we introduce an improved SCL decoding algorithm based on the sequential probability ratio test (SPRT). The proposed algorithm use double thresholds to decode the polar codes instead of single threshold decision used by the conventional SCL algorithm. Numerical results have shown that for (1024, 512) polar code, the proposed SPRT-SCL decoder can achieve a reduction in decoding complexity, and keep the similar decoding performance compared with conventional SCL decoder.