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.
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.
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 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.
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.
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 the context of the high-speed development of 5G communications, high-performance decoding schemes for polar codes are a hot spot in channel coding research. Shift pruning successive cancellation list (SP-SCL) decoding aims to recover the correct path by shift pruning in the extra SCL decoding. However, the current SP-SCL decoding is inflexible in determining the shift positions. In this paper, a flexible shift pruning SCL (FSP-SCL) decoding is proposed. Firstly, the reasons for movement and the eliminated states of the correct path are analyzed in detail using the path metric range (PMR), and on this basis, the validity of the method adopted in this paper for determining the shift priority of the information bits is verified. Secondly, the FSP-SCL decoding proposes two methods for determining the shift positions. One is the log-likelihood ratio (LLR) threshold method, which compares the LLR values of the eliminated paths on the shift bit with the corresponding LLR threshold to determine the shift positions. The other is the path distance method. It combines the minimum distance between the eliminated paths and the received vector with the path metrics to determine the shift positions. Both methods are more flexible and practical, as they can calculate the corresponding shift positions online based on a specific shift bit, avoiding the high complexity caused by the simulation method. Finally, this paper designs various experimental schemes to verify the decoding performance of the FSP-SCL. The experimental results show that in terms of error-correction performance, the LLR threshold-based FSP-SCL (FSPL (LLR threshold)) decoding, the path distance-based FSP-SCL (FSPL (path distance)) decoding and the existing SP-SCL decoding are roughly equal overall. In terms of decoding complexity, FSPL (LLR threshold) decoding is slightly better than FSPL (path distance) decoding, and the decoding complexity of both is lower than that of SP-SCL decoding, with the difference being more pronounced in the medium to high SNR regions.
In this paper, an improvement for SC list flip (SCL-Flip) decoding is presented for polar codes. A novel bit-selection metric for critical set (set of information symbols of polar codes being flipped during additional decoding attempts) based on path metric of successive cancellation list (SCL) decoding is suggested. With the proposed metric, the improved SCL scheme based on special nodes (SN) decoders was developed. This decoder will be denoted by GSCLF. The main idea of the proposed decoder is joint using of two approaches: first one is a fast decoding of special nodes in binary tree representation of polar code (e.g., some special nodes in tree representation of polar code that allow efficient list decoding with low complexity) and the second one is an applying of additional decoding attempts (flips) in the case when initial decoding was erroneous. The simultaneous use of these two approaches results in both a significant reduction in spatial complexity and a significant reduction in the number of computations required for decoding whereas keeping excellent performance. Simulation results presented in this paper allow us to conclude that the computational complexity of the proposed GSCLF decoder is from 66% to 80% smaller than the one of SCL-32 decoder.