In successive cancellation list (SCL) decoding, the list pruning operation retains the L paths with highest likelihoods. However, the correct path might be among the paths with low likelihoods due to channel noise. In this case, the correct path is eliminated from the list. In this work, we study the event of elimination of the correct path and we analyze where and how this event occurs. A modified pruning scheme named shifted-pruning over a set of low-reliability bit-channels named critical bits is proposed aiming to avoid the elimination of the correct path in additional decoding attempts after a decoding failure occurs. Shifted-pruning is realized by selecting the paths k + 1 to k + L out of the 2L ordered paths instead of the paths 1 to L. The numerical results for polar codes of length 512 and code rates 0.5 and 0.8 and list sizes L = 2, 8 and 32 show that the shifted-pruning scheme is a low-complexity equivalent to the bit-flipping scheme while it can outperform the bit-flipping method by providing 0. 25-0.5dB gain.
In successive cancellation list (SCL) decoding, the list pruning operation retains the L paths with highest likelihoods. However, the correct path might be among the paths with low likelihoods due to channel noise. In this case, the correct path is eliminated from the list. In this work, we study the event of elimination of the correct path and we analyze where and how this event occurs. A modified pruning scheme named shifted-pruning over a set of low-reliability bit-channels named critical bits is proposed aiming to avoid the elimination of the correct path in additional decoding attempts after a decoding failure occurs. Shifted-pruning is realized by selecting the paths k + 1 to k + L out of the 2L ordered paths instead of the paths 1 to L. The numerical results for polar codes of length 512 and code rates 0.5 and 0.8 and list sizes L = 2, 8 and 32 show that the shifted-pruning scheme is a low-complexity equivalent to the bit-flipping scheme while it can outperform the bit-flipping method by providing 0. 25-0.5dB gain.
In successive cancellation list (SCL) decoding, the tree pruning operation retains the L best paths with respect to metric at every decoding step. However, the correct path might be among the L worst paths due to imposed penalties. In this case, the correct path is pruned and the decoding process fails. In this work, we propose a scheme for additional decoding attempts when decoding fails, in which the pruning window does not necessarily select the L best paths, but this window is shifted between positions 1 and 2L in the sorted list. In the simplest form, the L worst paths are selected at the decoding step where the probability of elimination of the correct paths is high. Additionally, we generalize the scheme and propose a number of variants such as constrained shifting, nested shifting and shifting under segmented decoding, aiming to reduce the computational complexity. The numerical results for polar codes of length 512 with code rates 0.5 and 0.8 and list sizes L=2, 8, 32, show that the shifted-pruning scheme can provide 0.25-0.5 dB gain in error correction performance, while the average computational complexity approaches the conventional list decoding complexity at practical FER ranges.
In successive cancellation list (SCL) decoding, the tree pruning operation retains the L best paths with respect to a metric at every decoding step. However, the correct path might be among the L worst paths due to imposed penalties. In this case, the correct path is pruned and the decoding process fails. Shifted-pruning (SP) scheme can recover the correct path by additional decoding attempts when decoding fails, in which the pruning window is shifted by L over the bits with high likelihood of the elimination of the correct path, one at a time. In this work, we generalize the scheme by more freedom in shifting the pruning window, aiming to improve the error correction performance in the constrained number of decoding attempts. We also propose a metric for prioritizing the shifting positions.
In the successive cancellation (SC) list decoding, the tree pruning operation retains the L best paths with respect to a metric at every decoding step. However, the correct path might be among the L worst paths due to the imposed penalties. In this case, the correct path is pruned and the decoding process fails. shifted pruning (SP) scheme can recover the correct path by additional decoding attempts when decoding fails, in which the pruning window is shifted by κ≤L paths over certain bit positions. A special case of the shifted pruning scheme where κ=L is known as SCL-flip decoding, which was independently proposed in 2019. In this work, a new metric that performs better in particular for medium and long codes is proposed, and nested shift-pruning schemes are suggested for improving the average complexity.
Recently, a generalized successive cancellation list (SCL) decoder implemented with shifted-pruning (SP) scheme, namely the SCL-SP-ω decoder, is presented for polar codes, which is able to shift the pruning window at most ω times during each SCL re-decoding attempt to prevent the correct path from being eliminated. The candidate positions for applying the SP scheme are selected by a shifting metric based on the probability that the elimination occurs. However, the number of exponential/logarithm operations involved in the SCL-SP-ω decoder grows linearly with the number of information bits and list size, which leads to high computational complexity. In this paper, we present a detailed analysis of the SCL-SP-ω decoder in terms of the decoding performance and complexity, which unveils that the choice of the shifting metric is essential for improving the decoding performance and reducing the re-decoding attempts simultaneously. Then, we introduce a simplified metric derived from the path metric (PM) domain, and a custom-tailored deep learning (DL) network is further designed to enhance the efficiency of the proposed simplified metric. The proposed metrics are both free of transcendental functions and hence, are more hardware-friendly than the existing metrics. Simulation results show that the proposed DL-aided metric provides the best error correction performance as comparison with the state of the art.
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.
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.