This letter proposes an efficient method to reduce path splits in the successive cancellation list (SCL) decoding. We construct the boundary consisting of single-bit and multi-bit nodes that have a low error probability within the SC-decoding tree. The nodes on the boundary are considered with only two candidates per path instead of descending to their child nodes. To establish the boundary, we investigate the error probability of multi-bit nodes in the SC-decoding tree. The proposed method reduces the overall decoding cycles by approximately 70% while maintaining almost the same error-correcting performance as the conventional SCL decoding method.
This letter proposes an efficient method to reduce path splits in the successive cancellation list (SCL) decoding. We construct the boundary consisting of single-bit and multi-bit nodes that have a low error probability within the SC-decoding tree. The nodes on the boundary are considered with only two candidates per path instead of descending to their child nodes. To establish the boundary, we investigate the error probability of multi-bit nodes in the SC-decoding tree. The proposed method reduces the overall decoding cycles by approximately 70% while maintaining almost the same error-correcting performance as the conventional SCL decoding method.
Polar codes are the first capacity-achieving error-correction code which has attracted much research attention. Among many decoding methods, successive cancellation list decoding (SCLD) is considered as a representative decoding method that can achieve a good error-correcting performance. However, the long latency of SCLD is a significant matter that hinders practical applications, which is mainly caused by two features of the SCLD process: tree traversal and path-splitting. To alleviate the main reasons, a new multi-bit SCLD algorithm is proposed in this paper to decode several bits simultaneously without conducting any tree traversal and path-splitting when a node in the decoding tree holds a specific condition. In addition, a path ignoring (PI) technique is proposed to mitigate the condition of the multi-bit SCLD, which results in an additional reduction of latency. The proposed multi-bit decoding method and the PI technique play a significant role in reducing the number of path-splitting cases, by 96% compared to the conventional SCLD method. Simulation results show that compared to the conventional SCLD with list sizes 8 and 16, the proposed multi-bit decoding associated with the PI technique reduces the overall decoding cycles by 77% and 79%, respectively, with almost no degradation of error-correcting performance.
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.
This paper focuses on low complexity successive cancellation list (SCL) decoding of polar codes. In particular, using the fact that splitting may be unnecessary when the reliability of decoding the unfrozen bit is sufficiently high, a novel splitting rule is proposed. Based on this rule, it is conjectured that, if the correct path survives at some stage, it tends to survive till termination without splitting with high probability. On the other hand, the incorrect paths are more likely to split at the following stages. Motivated by these observations, a simple counter that counts the successive number of stages without splitting is introduced for each decoding path to facilitate the identification of correct and incorrect paths. Specifically, any path with counter value larger than a predefined threshold ω is deemed to be the correct path, which will survive at the decoding stage, while other paths with counter value smaller than the threshold will be pruned, thereby reducing the decoding complexity. Furthermore, it is proved that there exists a unique unfrozen bit uN-K1+1, after which the successive cancellation decoder achieves the same error performance as the maximum likelihood decoder if all the prior unfrozen bits are correctly decoded, which enables further complexity reduction. Simulation results demonstrate that the proposed low complexity SCL decoder attains performance similar to that of the conventional SCL decoder, while achieving substantial complexity reduction.
In this paper, we propose a simplified multi-bit successive cancellation list (SMSCL) decoding method for polar codes. In the proposed SMSCL decoding, frozen bits are ignored, and multiple information bits are intermediately decoded at each decision step. In addition, a modified two-stage pruning network is proposed to reduce the complexity of path pruning in SMSCL decoding. Compared to the existing multi-bit SCL decoders, the SMSCL decoder can achieve significant latency and complexity reduction over a wide range of code rates.
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.
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.