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

Journal of Beijing Institute of Technology

Improved Soft Cancellation Decoding of Polar Codes

Mingyue You, Zhifeng Ma

Published Sep 30, 2020• 0 citations
Publisher

Abstract

The soft cancellation decoding of polar codes achieves a better performance than the belief propagation decoding with lower computational time and space complexities. However, because the soft cancellation decoding is based on the successive cancellation decoding, the decoding efficiency and performance with finite-length blocks can be further improved. Exploiting the idea of the successive cancellation list decoding, the soft cancellation decoding can be improved in two aspects: one is by adding branch decoding to the error-prone information bits to increase the accuracy of the soft information, and the other is through using partial iterative decoding to reduce the time and computational complexities. Compared with the original method, the improved soft cancellation decoding makes progress in the error correction performance, increasing the decoding efficiency and reducing the computational complexity, at the cost of a small increase of space complexity.

DOI
10.15918/j.jbit1004-0579.20008

Related papers

Iterative and Adjustable Soft List Decoding for Polar Codes

Bowen Feng, Jian Jiao, Shaohua Wu +2 more

List decoding of polar codes is an outstanding decoding method, in which a fixed-size list is applied to retain the most probable paths. In general, it is preferable to use a large-size list in the decoding to achieve excellent error-control performance, but this can lead to high complexity. Moreover, the list decoding is still a one-time-pass algorithm with hard-decision outputs, which is not well suited for advanced concatenated coding systems. In this paper, a novel adjustable list decoding is proposed, in which the list size can be adjusted appropriately. Based on the reliability analyses of the decoding list, dynamic thresholds are designed to precisely guide the adjustments. The adjustable list decoding can also achieve excellent error-control performance, but the complexity is significantly reduced. Moreover, we propose an iterative adjustable list decoding scheme with soft-decision outputs for concatenated polar-coding systems, in which a log-likelihood-ratio update strategy is elaborately designed. It can achieve much better error-control performance compared with the existing iterative decoding schemes, such as the belief propagation (BP) decoding, and soft cancellation (SCAN) decoding. As the number of iterations increases, the decoding performance gradually improves, but the complexity increases little due to efficient complexity control designs.

IEEE Transactions on Signal Processing•Jan 1, 2020•5 citations

Efficient Soft Cancelation Decoder Architectures for Polar Codes

Jun Ting Lin, Zhiyuan Yan, Zhongfeng Wang

The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jul 12, 2016•12 citations

SCAN List Decoding of Polar Codes

Charles Pillet, Carlo Condo, Valerio Bioglio

In this paper we propose an enhanced soft cancellation (SCAN) decoder for polar codes based on decoding stages permutation. The proposed soft cancellation list (SCANL) decoder runs L independent SCAN decoders, each one relying on a different permuted factor graph. The estimated bits are selected among the L candidates through a dedicated metric provided by the decoders. Furthermore, we introduce an early-termination scheme reducing decoding latency without affecting error correction performance. We investigate the error-correction performance of the proposed scheme under various combinations of number of iterations used, permutation set and early-termination condition. Simulation results show that the proposed SCANL provides similar results when compared with belief propagation list, while having a smaller complexity. Moreover, for large list sizes, SCANL outperforms non-CRC aided successive cancellation list decoding.

arXiv:2001.11283•International Conference on Communications•Jun 1, 2020•27 citations

Improved Successive Cancellation Decoding of Polar Codes Through Perturbing A Posteriori LLRs

Zhongjun Yang, Li Chen, Kangjian Qin +2 more

For polar codes, perturbing received information can enhance the error-correction performance of successive cancellation (SC) decoding. This is an effective approach for realizing low-latency yet high decoding performance for long polar codes, since each perturbation-enhanced SC (PSC) decoding can be performed in parallel. This paper provides theoretical insights into the soft information perturbation. It first reveals that the PSC decoding can be equivalently viewed as perturbing the SC decoding a posteriori log-likelihood ratio (LLR) of the information bits. Such a revelation enables us to reduce the perturbation complexity by only targeting the information bits, resulting in an improved PSC (IPSC) decoding. By better utilizing the a posteriori LLRs, a set of possibly erroneous estimations can be formed to be perturbed, further reducing the perturbation complexity. Our simulation results show that, for various codeword lengths, the proposed IPSC decoding can achieve a similar performance as the PSC decoding, while yielding significant perturbation complexity reduction.

IEEE Information Theory Workshop (ITW)•Sep 29, 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•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
The soft cancellation decoding of polar codes achieves a better performance than the belief propagation decoding with lower computational time and space complexities. However, because the soft cancellation decoding is based on the successive cancellation decoding, the decoding efficiency and performance with finite-length blocks can be further improved. Exploiting the idea of the successive cancellation list decoding, the soft cancellation decoding can be improved in two aspects: one is by adding branch decoding to the error-prone information bits to increase the accuracy of the soft information, and the other is through using partial iterative decoding to reduce the time and computational complexities. Compared with the original method, the improved soft cancellation decoding makes progress in the error correction performance, increasing the decoding efficiency and reducing the computational complexity, at the cost of a small increase of space complexity.
List decoding of polar codes is an outstanding decoding method, in which a fixed-size list is applied to retain the most probable paths. In general, it is preferable to use a large-size list in the decoding to achieve excellent error-control performance, but this can lead to high complexity. Moreover, the list decoding is still a one-time-pass algorithm with hard-decision outputs, which is not well suited for advanced concatenated coding systems. In this paper, a novel adjustable list decoding is proposed, in which the list size can be adjusted appropriately. Based on the reliability analyses of the decoding list, dynamic thresholds are designed to precisely guide the adjustments. The adjustable list decoding can also achieve excellent error-control performance, but the complexity is significantly reduced. Moreover, we propose an iterative adjustable list decoding scheme with soft-decision outputs for concatenated polar-coding systems, in which a log-likelihood-ratio update strategy is elaborately designed. It can achieve much better error-control performance compared with the existing iterative decoding schemes, such as the belief propagation (BP) decoding, and soft cancellation (SCAN) decoding. As the number of iterations increases, the decoding performance gradually improves, but the complexity increases little due to efficient complexity control designs.
The flooding belief propagation (FO-BP) and the soft-cancelation (SCAN) algorithms are the two most popular soft-output BP algorithms for the decoding of capacity-achieving polar codes. The FO-BP algorithm has high throughput at the cost of performance degradation in high signal-to-noise ratio (SNR) region or with large block length. The SCAN algorithm has much better decoding performance while suffering from long decoding latency and low throughput. In this paper, an improved BP algorithm, named reduced complexity soft-cancelation (RCSC) algorithm, is proposed. Compared with the SCAN algorithm, the number of memory entries required by the RCSC algorithm is reduced by more than 50% in general, while achieving comparable or even better (e.g., when block size N = 215) decoding performance. When block size is large (e.g., N ≥ 215), the proposed RCSC algorithm reduces the required memory entries by more than 23% compared with the state-of-the-art FO-BP algorithm. The numerical results show that the error performance improvement of the RCSC algorithm is more significant when the SNR increases. For a different tradeoff, a reduced latency soft-cancelation (RLSC) algorithm is proposed to reduce the decoding latency and increase the throughput of the RCSC algorithm while slightly sacrificing decoding performance. Finally, the optimized VLSI architectures are presented for the RCSC and RLSC algorithms, respectively. The synthesis results demonstrate the efficiency of the proposed algorithms and architectures.
In this paper we propose an enhanced soft cancellation (SCAN) decoder for polar codes based on decoding stages permutation. The proposed soft cancellation list (SCANL) decoder runs L independent SCAN decoders, each one relying on a different permuted factor graph. The estimated bits are selected among the L candidates through a dedicated metric provided by the decoders. Furthermore, we introduce an early-termination scheme reducing decoding latency without affecting error correction performance. We investigate the error-correction performance of the proposed scheme under various combinations of number of iterations used, permutation set and early-termination condition. Simulation results show that the proposed SCANL provides similar results when compared with belief propagation list, while having a smaller complexity. Moreover, for large list sizes, SCANL outperforms non-CRC aided successive cancellation list decoding.
For polar codes, perturbing received information can enhance the error-correction performance of successive cancellation (SC) decoding. This is an effective approach for realizing low-latency yet high decoding performance for long polar codes, since each perturbation-enhanced SC (PSC) decoding can be performed in parallel. This paper provides theoretical insights into the soft information perturbation. It first reveals that the PSC decoding can be equivalently viewed as perturbing the SC decoding a posteriori log-likelihood ratio (LLR) of the information bits. Such a revelation enables us to reduce the perturbation complexity by only targeting the information bits, resulting in an improved PSC (IPSC) decoding. By better utilizing the a posteriori LLRs, a set of possibly erroneous estimations can be formed to be perturbed, further reducing the perturbation complexity. Our simulation results show that, for various codeword lengths, the proposed IPSC decoding can achieve a similar performance as the PSC decoding, while yielding significant perturbation complexity reduction.
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.