Hardware Decoders for Polar Codes: An Overview <s> II. Background <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> BIB001 </s> Hardware Decoders for Polar Codes: An Overview <s> II. Background <s> This is the first in a two-part series of papers on unrolled polar decoders. In this paper (Part I), we present a family of architectures for hardware polar decoders using a reduced-complexity successive-cancellation decoding algorithm. The resulting fully-unrolled architectures are capable of achieving a coded throughput in excess of 400 Gbps on an FPGA, two orders of magnitude greater than current state-of-the-art polar decoders. Moreover, the proposed architectures are flexible in a way that makes it possible to explore the trade-off between resource usage and throughput. <s> BIB002 </s> Hardware Decoders for Polar Codes: An Overview <s> II. Background <s> We present an LLR-based implementation of the successive cancellation list (SCL) decoder. To this end, we associate each decoding path with a metric which (i) is a monotone function of the path’s likelihood and (ii) can be computed efﬁciently from the channel LLRs. The LLR-based formulation leads to a more efﬁcient hardware implementation of the decoder compared to the known log-likelihood based implementation. Synthesis results for an SCL decoder with block-length of N = 1024 and list sizes of L = 2 and L = 4 conﬁrm that the LLR-based decoder has considerable area and operating frequency advantages in the orders of 50% and 30%, respectively. <s> BIB003
Polar codes are recursively constructed from a 2 ×2 polarizing transformation F = 0 1 1 1 : a vector u 1 0 of two bits u 0 and u 1 is encoded using F to yield a polar codeword. When estimating u 0 and u 1 using SC decoding, the probability of correctly estimating u 0 decreases while that of u 1 increases compared to an uncoded vector. This transform is recursively applied log N times to encode N bits. As N → ∞ the probability of correct detection approaches 1.0 (reliable) or 0.5 (unreliable) and the proportion of reliable bits approaches the symmetric capacity of the underlying memoryless channel. To construct an (N, k) polar code, the k most reliable bits in u N−1 0 are used to carry the information bits; while the remaining bits are frozen by setting them to a predetermined value-usually '0'. Fig. 1a shows the graph representation of an BIB002 BIB001 polar code where the frozen and information bits are labeled in gray and black, respectively. Due to the recursive nature of polar code construction, binary trees are a natural representation for these codes. In Fig. 1b , the white (black) leaf nodes correspond to frozen (information) bits; whereas the gray nodes correspond to the polar transformations encircled in Fig. 1a . Each sub-tree rooted at a node of depth log 2 N v , where leaf nodes have a depth of 0, corresponds to constituent polar codes of length N v . Quantization in hardware decoders varies based on polar code length and the decoding algorithm used. Many implementations, e.g. BIB001 , use fewer bits for channel reliability information than for internal values. SCL decoders BIB003 are less tolerant of value saturation and therefore require more quantization bits than their SC counterparts. Finally, longer codes require more integer bits to represent the wider range of their internal values.