Hardware Decoders for Polar Codes: An Overview <s> A. SC-based Decoding Algorithms <s> The serial nature of successive-cancellation decoding results in low polar decoder throughput. In this letter we present an improved version of the simplified successive-cancellation decoding algorithm that increases decoding throughput without degrading the error-correction performance. We show that the proposed algorithm has up to three times the throughput of the simplified successive-cancellation decoding algorithm and up to twenty-nine times the throughput of a standard successive-cancellation decoder while using the same number of processing elements. <s> BIB001 </s> Hardware Decoders for Polar Codes: An Overview <s> A. SC-based Decoding Algorithms <s> Polar codes provably achieve the symmetric capacity of a memoryless channel while having an explicit construction. The adoption of polar codes however, has been hampered by the low throughput of their decoding algorithm. This work aims to increase the throughput of polar decoding hardware by an order of magnitude relative to successive-cancellation decoders and is more than 8 times faster than the current fastest polar decoder. We present an algorithm, architecture, and FPGA implementation of a flexible, gigabit-per-second polar decoder. <s> BIB002 </s> Hardware Decoders for Polar Codes: An Overview <s> A. SC-based Decoding Algorithms <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> BIB003
The SC decoding algorithm traverses the entire polar code tree, e.g. Fig. 1b , depth first, visiting all leaf nodes. To reduce latency, the simplified successive-cancellation (SSC) decoding algorithm does not traverse sub-trees whose leaves all correspond to frozen or information bits. Instead, it applies a decision rule immediately  . Similarly, constrained maximumlikelihood decoding of multiple bits can be employed to trim the decoder tree BIB001 - BIB003 . The Fast-SSC decoding algorithm extends the SSC algorithm by applying low-complexity decoding rules when encountering certain types of sub-trees BIB002 ,  . Specialized decoding of repetition and single-parity-check (SPC) codes are the most notable examples and reduce the decoder-tree size, significantly reducing the number of calculations and increasing the decoding speed.