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.
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.
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.
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.
Polar codes is promising because they can provably achieve the channel capacity while having an explicit construction method. Lots of work have been done for the bit-based decoding algorithm for polar codes. In this paper, generalized symbol-based successive cancellation (SC) and SC list decoding algorithms are discussed. A symbol-based recursive channel combination relationship is proposed to calculate the symbol-based channel transition probability. This proposed method needs less additions than the maximum-likelihood decoder used by the existing symbol-based polar decoding algorithm. In addition, a two-stage list pruning network is proposed to simplify the list pruning network for the symbol-based SC list decoding algorithm.
Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2Kbits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively.
Abstract—Polar codes is promising because they can provably achieve the channel capacity while having an explicit construc-tion method. Lots of work have been done for the bit-based decoding algorithm for polar codes. In this paper, generalized symbol-based successive cancellation (SC) and SC list decoding algorithms are discussed. A symbol-based recursive channel combination relationship is proposed to calculate the symbol-based channel transition probability. This proposed method needs less additions than the maximum-likelihood decoder used by the existing symbol-based polar decoding algorithm. In addition, a two-stage list pruning network is proposed to simplify the list pruning network for the symbol-based SC list decoding algorithm. Index Terms—Error control codes, polar codes, successive cancellation decoding, list decoding I.
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.