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

Wireless and Optical Communications Conference

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

Wenpeng Li, Lining Du, Yuevun Chen

Published May 1, 2019• 2 citations
Publisher

Abstract

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.

DOI
10.1109/wocc.2019.8770542

Related papers

Successive cancellation list polar decoder using log-likelihood ratios

Bo Yuan, Keshab K. Parhi

Successive cancellation list (SCL) decoding algorithm is a powerful method that can help polar codes achieve excellent error-correcting performance. However, the current SCL algorithm and decoders are based on likelihood or log-likelihood forms, which render high hardware complexity. In this paper, we propose a log-likelihood-ratio (LLR)-based SCL (LLR-SCL) decoding algorithm, which only needs half the computation and storage complexity than the conventional one. Then, based on the proposed algorithm, we develop low-complexity VLSI architectures for LLR-SCL decoders. Analysis results show that the proposed LLR-SCL decoder achieves 50% reduction in hardware and 98% improvement in hardware efficiency.

arXiv:1411.7282•Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2014•41 citations

Simplified Successive-Cancellation List decoding of polar codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•74 citations

Improved Logical Error Rate via List Decoding of Quantum Polar Codes

Anqi Gong, Joseph M. Renes

The successive cancellation list decoder (SCL) is an efficient decoder for classical polar codes with low decoding error, approximating the maximum likelihood decoder (MLD) for small list sizes. Here we adapt the SCL to the task of decoding quantum polar codes and show that it inherits the high performance and low complexity of the classical case, and can approximate the quantum MLD for certain channels. We apply SCL decoding to a novel version of quantum polar codes based on the polarization weight (PW) method, which entirely avoids the need for small amounts of entanglement assistance apparent in previous quantum polar code constructions. When used to find the precise error pattern, the quantum SCL decoder (SCL-E) shows competitive performance with surface codes of similar size and low-density parity check codes of similar size and rate. The SCL decoder may instead be used to approximate the probability of each equivalence class of errors, and then choose the most likely class. We benchmark this class-oriented decoder (SCL-C) against the SCL-E decoder and find a noticeable improvement in the logical error rate. This improvement stems from the fact that the contributions from just the low-weight errors give a reasonable approximation to the error class probabilities. Both SCL-E and SCL-C maintain the complexity O(LN log N) of SCL for code size$N$and list size L.

arXiv:2304.04743•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

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

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

Interleaver-Aided Successive Cancellation Flip Decoding Algorithm for Polar Codes

Haseong Kim, Hyunjee Lee, Hosung Park

When the code length is finite, the successive cancellation list (SCL) decoding of polar codes shows as good error-correction performance as low-density parity-check codes and turbo codes and it will be used in high-speed communications. However, since the hardware complexity of the SCL increases linearly as the size of the list increases, it is difficult to use the high-complexity SCL decoding for devices with limited resource such as IoT devices. The successive cancellation flip (SCF) decoding algorithm has been proposed to solve the problem of high hardware complexity and to enhance the error-correction performance of successive cancellation decoding. However, the conventional SCF decoding has high computational complexity. In this paper, we propose the interleaver-aided successive cancellation flip (ISCF) decoding to reduce the computational complexity. The computational complexity of the ISCF decoding is less by at least 32% than the conventional SCF decoding for error frame at Eb/N0=3.5dB.

IEEE International Conference on Computer and Communications (ICCC)•Dec 1, 2018•1 citation
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.
Successive cancellation list (SCL) decoding algorithm is a powerful method that can help polar codes achieve excellent error-correcting performance. However, the current SCL algorithm and decoders are based on likelihood or log-likelihood forms, which render high hardware complexity. In this paper, we propose a log-likelihood-ratio (LLR)-based SCL (LLR-SCL) decoding algorithm, which only needs half the computation and storage complexity than the conventional one. Then, based on the proposed algorithm, we develop low-complexity VLSI architectures for LLR-SCL decoders. Analysis results show that the proposed LLR-SCL decoder achieves 50% reduction in hardware and 98% improvement in hardware efficiency.
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 decoder (SCL) is an efficient decoder for classical polar codes with low decoding error, approximating the maximum likelihood decoder (MLD) for small list sizes. Here we adapt the SCL to the task of decoding quantum polar codes and show that it inherits the high performance and low complexity of the classical case, and can approximate the quantum MLD for certain channels. We apply SCL decoding to a novel version of quantum polar codes based on the polarization weight (PW) method, which entirely avoids the need for small amounts of entanglement assistance apparent in previous quantum polar code constructions. When used to find the precise error pattern, the quantum SCL decoder (SCL-E) shows competitive performance with surface codes of similar size and low-density parity check codes of similar size and rate. The SCL decoder may instead be used to approximate the probability of each equivalence class of errors, and then choose the most likely class. We benchmark this class-oriented decoder (SCL-C) against the SCL-E decoder and find a noticeable improvement in the logical error rate. This improvement stems from the fact that the contributions from just the low-weight errors give a reasonable approximation to the error class probabilities. Both SCL-E and SCL-C maintain the complexity O(LN log N) of SCL for code sizeNNNand list size L.
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.
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.
When the code length is finite, the successive cancellation list (SCL) decoding of polar codes shows as good error-correction performance as low-density parity-check codes and turbo codes and it will be used in high-speed communications. However, since the hardware complexity of the SCL increases linearly as the size of the list increases, it is difficult to use the high-complexity SCL decoding for devices with limited resource such as IoT devices. The successive cancellation flip (SCF) decoding algorithm has been proposed to solve the problem of high hardware complexity and to enhance the error-correction performance of successive cancellation decoding. However, the conventional SCF decoding has high computational complexity. In this paper, we propose the interleaver-aided successive cancellation flip (ISCF) decoding to reduce the computational complexity. The computational complexity of the ISCF decoding is less by at least 32% than the conventional SCF decoding for error frame at Eb/N0=3.5dB.