The successive cancellation list (SCL) decoding is used to achieve good error-correcting performance for practical finite-length polar codes. However, the metric sorting that is repeatedly performed in SCL decoding increases the overall decoding latency as the list size increases, making it difficult to apply the SCL decoding to the applications with limited processing time. To reduce the latency of the metric sorting, this paper proposes a new sorting method derived by analyzing path extension cases encountered in SCL decoding. The proposed method can avoid unnecessary sorting operations by adaptively determining the sorting size, and can be combined with other metric sorting methods. Simulation results show that the proposed method significantly reduces the decoding latency for various list sizes and code rates without degrading the error-correcting performance. The proposed method also becomes more effective as the code rate or the list size increases. Combined with the state-of-the-art sorting method, the proposed method reduces the average SCL decoding latency for a (1024, 512) polar code by 33.1% when the list size is 8.
The successive cancellation list (SCL) decoding is used to achieve good error-correcting performance for practical finite-length polar codes. However, the metric sorting that is repeatedly performed in SCL decoding increases the overall decoding latency as the list size increases, making it difficult to apply the SCL decoding to the applications with limited processing time. To reduce the latency of the metric sorting, this paper proposes a new sorting method derived by analyzing path extension cases encountered in SCL decoding. The proposed method can avoid unnecessary sorting operations by adaptively determining the sorting size, and can be combined with other metric sorting methods. Simulation results show that the proposed method significantly reduces the decoding latency for various list sizes and code rates without degrading the error-correcting performance. The proposed method also becomes more effective as the code rate or the list size increases. Combined with the state-of-the-art sorting method, the proposed method reduces the average SCL decoding latency for a (1024, 512) polar code by 33.1% when the list size is 8.
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.
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.
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.
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.
In order to achieve a magnificent error-correcting performance Successive Cancellation List (SCL) decoding is a powerful and excellent method which considers L decoding paths at each decoding stage concurrently. However, the conventional SCL decoder uses L copies of Successive Cancellation (SC) decoder for a list size of L thereby resulting in a massive increase in the hardware as the list size increases which is one of the major drawbacks of SCL decoder. One more drawback of SCL decoder architecture is the long latency of the architecture. Using the proposed efficient utilization of existing hardware architecture, there is a reduction in the number of Merged Processing Elements (MPE) by 39% for a list size of 2 and 45% for a list size of 4 when compared to the existing architectures and a vast reduction compared to conventional SCL decoder. The partial pipelining considered in this work can reduce the latency compared to conventional SCL multi-bit architecture to a greater extent.