Although the successive cancellation list (SCL) decoding of polar codes exhibits excellent performance, it retains many decoding paths in the list with negligible contribution to the final output, resulting in high sorting and computational complexity. In this letter, we propose a novel pruning strategy to mitigate the decoding complexity. By leveraging the blockwise soft output extraction process of soft-output SCL and soft-output fast SCL decoding, we provide an accurate approximation of the probability that a decoding path is correct, and thus accordingly prune the paths failing to meet a pre-defined reliability threshold. The complexity reduction achieved by the proposed soft-output-based pruned SCL (SOP-SCL) decoder and its fast version, SOP-FSCL decoder, is significant, without any compromise in error-correction performance. Meanwhile, they also prove to be more efficient than state-of-the-art pruned polar decoders.
Although the successive cancellation list (SCL) decoding of polar codes exhibits excellent performance, it retains many decoding paths in the list with negligible contribution to the final output, resulting in high sorting and computational complexity. In this letter, we propose a novel pruning strategy to mitigate the decoding complexity. By leveraging the blockwise soft output extraction process of soft-output SCL and soft-output fast SCL decoding, we provide an accurate approximation of the probability that a decoding path is correct, and thus accordingly prune the paths failing to meet a pre-defined reliability threshold. The complexity reduction achieved by the proposed soft-output-based pruned SCL (SOP-SCL) decoder and its fast version, SOP-FSCL decoder, is significant, without any compromise in error-correction performance. Meanwhile, they also prove to be more efficient than state-of-the-art pruned polar decoders.
Although the successive cancellation list (SCL) decoding of polar codes exhibits excellent performance, it retains many decoding paths in the list with negligible contribution to the final output, resulting in high sorting and computational complexity. In this letter, we propose a novel pruning strategy to mitigate the decoding complexity. By leveraging the blockwise soft output extraction process of soft-output SCL and soft-output fast SCL decoding, we provide an accurate approximation of the probability that a decoding path is correct, and thus accordingly prune the paths failing to meet a pre-defined reliability threshold. The complexity reduction achieved by the proposed soft-output-based pruned SCL (SOP-SCL) decoder and its fast version, SOP-FSCL decoder, is significant, without any compromise in error-correction performance. Meanwhile, they also prove to be more efficient than state-of-the-art pruned polar decoders.
The soft-output successive cancellation list (SOSCL) decoder provides a methodology for estimating the aposteriori probability log-likelihood ratios by only leveraging the conventional SCL decoder of polar codes. However, the sequential decoding nature of SCL introduces high decoding latency to SOSCL. In this paper, we incorporate node-based fast decoding into the SO-SCL framework. After addressing the challenge of soft output extraction in special node decoding, we proposed the soft-output fast SCL (SO-FSCL) decoding algorithm, along with its log-domain implementation and hardware-friendly version. The proposed SO-FSCL decoder can be regarded as an addon extension to FSCL decoder, enabling us to autonomously choose whether to output only hard decisions like FSCL or to provide additional soft outputs. Latency and complexity analyses demonstrate that SO-FSCL can significantly reduce, for example, decoding time steps by 81.8% (with unlimited resources), the number of additions by 41.3%, and the number of comparisons by 46.4%. Meanwhile, simulation results indicate that SO-FSCL delivers almost the same soft-output performance as SO-SCL, outperforming other soft-output polar decoders, especially in scenarios involving iterative decoding.
The soft-output successive cancellation list (SO-SCL) decoder provides a methodology for estimating the a-posteriori probability log-likelihood ratios by only leveraging the conventional SCL decoder of polar codes. However, the sequential decoding nature of SCL introduces high decoding latency to SO-SCL. In this paper, we incorporate node-based fast decoding into the SO-SCL framework. After addressing the challenge of soft output extraction in special node decoding, we proposed the soft-output fast SCL (SO-FSCL) decoding algorithm, along with its log-domain implementation and hardware-friendly version. The proposed SO-FSCL decoder can be regarded as an add-on extension to FSCL decoder, enabling us to autonomously choose whether to output only hard decisions like FSCL or to provide additional soft outputs. Latency and complexity analyses demonstrate that SO-FSCL can significantly reduce, for example, decoding time steps by 81.8\% (with unlimited resources), the number of additions by 41.3\%, and the number of comparisons by 46.4\%. Meanwhile, simulation results indicate that SO-FSCL delivers almost the same soft-output performance as SO-SCL, outperforming other soft-output polar decoders, especially in scenarios involving iterative decoding.
The soft-output successive cancellation list (SO-SCL) decoder provides a methodology for estimating the a-posteriori probability log-likelihood ratios by only leveraging the conventional SCL decoder for polar codes. However, the sequential nature of SCL decoding leads to a high decoding latency for the SO-SCL decoder. In this paper, we propose a soft-output fast SCL (SO-FSCL) decoder by incorporating node-based fast decoding into the SO-SCL framework. Simulation results demonstrate that the proposed SO-FSCL decoder significantly reduces the decoding latency without loss of performance compared with the SO-SCL decoder.
Sorting operation is one of the main bottlenecks for the successive-cancellation list (SCL) decoding. This paper introduces an improvement to the SCL decoding for polar and pre-transformed polar codes that reduces the number of sorting operations without visible degradation in the code’s error-correction performance. In an SCL decoding with an optimum metric function we show that, on average, the correct branch’s bit-metric value must be equal to the bit-channel capacity, and on the other hand, the average bit-metric value of a wrong branch can be at most zero. This implies that a wrong path’s partial path metric value deviates from the bit-channel capacity’s partial summation. For relatively reliable bit-channels, the bit metric for a wrong branch becomes very large negative number, which enables us to detect and prune such paths. We prove that, for a threshold lower than the bit-channel cutoff rate, the probability of pruning the correct path decreases exponentially by the given threshold. Based on these findings, we presented a pruning technique, and the experimental results demonstrate a substantial decrease in the amount of sorting procedures required for SCL decoding. In the stack algorithm, a similar technique is used to significantly reduce the average number of paths in the stack.
Successive cancellation list (SCL) decoding enables polar codes and their generalizations to deliver satisfactory performance in finite-length scenarios but it comes with high latency and complexity. To reduce latency, a partitioned SCL (PSCL) decoding algorithm, implemented over a PSCL decoding tree, can be utilized. In this work, we aim to lower down the complexity of the PSCL decoding, resulting in an efficient decoding algorithm with low latency and complexity for polar-like codes. To achieve this, we define two metrics at each level of the PSCL decoding tree. One is for evaluating the reliability of a path and the other is for estimating the probability of the correct path being included in a list of paths. Then, we propose a double-threshold strategy in the PSCL decoding process where unreliable valid paths are pruned based on the first metric, and then a list of surviving paths is selected based on the second metric. Simulation results demonstrate that when polar/CRC-polar/PAC codes are decoded using the proposed low-complexity PSCL decoder, both the sorting complexity and the computational complexity are reduced and significantly decrease as the signal-to-noise ratio (SNR) increases.