Hardware Decoders for Polar Codes: An Overview <s> B. Path Metric Sorting <s> We focus on the metric sorter unit of successive cancellation list decoders for polar codes, which lies on the critical path in all current hardware implementations of the decoder. We review existing metric sorter architectures and we propose two new architectures that exploit the structure of the path metrics in a log-likelihood ratio based formulation of successive cancellation list decoding. Our synthesis results show that, for the list size of L = 32, our first proposed sorter is 14% faster and 45% smaller than existing sorters, while for smaller list sizes, our second sorter has a higher delay in return for up to 36% reduction in the area. <s> BIB001 </s> Hardware Decoders for Polar Codes: An Overview <s> B. Path Metric Sorting <s> Long polar codes can achieve the capacity of arbitrary binary-input discrete memoryless channels under a low complexity successive cancelation (SC) decoding algorithm. But for polar codes with short and moderate code length, the decoding performance of the SC decoding algorithm is inferior. The cyclic redundancy check (CRC) aided successive cancelation list (SCL) decoding algorithm has better error performance than the SC decoding algorithm for short or moderate polar codes. However, the CRC aided SCL (CA-SCL) decoding algorithm still suffer from long decoding latency. In this paper, a reduced latency list decoding (RLLD) algorithm for polar codes is proposed. For the proposed RLLD algorithm, all rate-0 nodes and part of rate-1 nodes are decoded instantly without traversing the corresponding subtree. A list maximum-likelihood decoding (LMLD) algorithm is proposed to decode the maximum likelihood (ML) nodes and the remaining rate-1 nodes. Moreover, a simplified LMLD (SLMLD) algorithm is also proposed to reduce the computational complexity of the LMLD algorithm. Suppose a partial parallel list decoder architecture with list size $L=4$ is used, for an (8192, 4096) polar code, the proposed RLLD algorithm can reduce the number of decoding clock cycles and decoding latency by 6.97 and 6.77 times, respectively. <s> BIB002 </s> Hardware Decoders for Polar Codes: An Overview <s> B. Path Metric Sorting <s> For polar codes with short-to-medium code length, list successive cancellation decoding is used to achieve a good error-correcting performance. However, list pruning in the current list decoding is based on the sorting strategy and its timing complexity is high. This results in a long decoding latency for large list size. In this work, aiming at a low-latency list decoding implementation, a double thresholding algorithm is proposed for a fast list pruning. As a result, with a negligible performance degradation, the list pruning delay is greatly reduced. Based on the double thresholding, a low-latency list decoding architecture is proposed and implemented using a UMC 90nm CMOS technology. Synthesis results show that, even for a large list size of 16, the proposed low-latency architecture achieves a decoding throughput of 220 Mbps at a frequency of 641 MHz. <s> BIB003 </s> Hardware Decoders for Polar Codes: An Overview <s> B. Path Metric Sorting <s> 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 ( $3{n}-2$ ) to ( $2{n}-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 $2^{K}$ bits simultaneously. This general approach, referred as $\textit {2}^{K}$ -bit reformulated SCL ( ${2}^{K}$ b-rSCL ) algorithm , can reduce the overall decoding latency to as short as ${n}/2^{K-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. <s> BIB004 </s> Hardware Decoders for Polar Codes: An Overview <s> B. Path Metric Sorting <s> Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes while having an explicit construction. Most existing decoding algorithms of polar codes are based on bit-wise hard or soft decisions. In this paper, we propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. First, we propose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arikan's channel transformations also helps to share hardware resources between calculating bit- and symbol-wise channel transition probabilities. Second, a two-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Third, since memory is a significant part of SCL decoders, we propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder. Finally, to evaluate the throughput advantage of our symbol-decision decoders, we design an architecture based on a semi-parallel successive cancellation list decoder. In this architecture, different symbol sizes, sorting implementations, and message scheduling schemes are considered. Our synthesis results show that in terms of area efficiency, our symbol-decision SCL decoders outperform existing bit-decision and multi-bit SCL decoders. <s> BIB005
A computationally challenging step of SCL decoding is that of path metric sorting, where the L best path metrics have to be selected among 2L possible metrics. The properties of the LLR-based path metric were exploited in BIB001 in order to significantly reduce the complexity and the critical path of the metric sorting blocks, while still performing exact sorting. In a different approach, path metrics were approximately sorted with double thresholding method proposed in BIB003 . It compares 2L path metrics with two thresholds, AT and RT . A path survives if its metric is smaller than AT . After it, the paths with metrics in between AT and RT are randomly selected to fill up the list of L surviving paths. This method significantly reduces the critical path of metric sorting, especially for a large L. The problem of path metric sorting is even more pronounced in decoders that employ multi-bit decision, such as BIB004 , BIB002 , since in this case the L best metrics out of up to 2 b L candidate metrics have to be selected, where b is the number of bits that are decoded simultaneously. To this end, an approximate twostage sorting unit was proposed in BIB005 , where the best q out of 2 b successor paths are first selected for each path, and then the best L paths are selected among the qL paths resulting from the first step. This approach reduces the sorting complexity at the cost of a small performance degradation.