Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <s> A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity $I(W)$ of any given binary-input discrete memoryless channel (B-DMC) $W$. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of $N$ independent copies of a given B-DMC $W$, a second set of $N$ binary-input channels $\{W_N^{(i)}:1\le i\le N\}$ such that, as $N$ becomes large, the fraction of indices $i$ for which $I(W_N^{(i)})$ is near 1 approaches $I(W)$ and the fraction for which $I(W_N^{(i)})$ is near 0 approaches $1-I(W)$. The polarized channels $\{W_N^{(i)}\}$ are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC $W$ with $I(W)>0$ and any target rate $R<I(W)$, there exists a sequence of polar codes $\{{\mathscr C}_n;n\ge 1\}$ such that ${\mathscr C}_n$ has block-length $N=2^n$, rate $\ge R$, and probability of block error under successive cancellation decoding bounded as $P_{e}(N,R) \le \bigoh(N^{-\frac14})$ independently of the code rate. This performance is achievable by encoders and decoders with complexity $O(N\log N)$ for each. <s> BIB001 </s> Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <s> Polar codes, introduced recently by Arikan, are the first family of codes known to achieve capacity of symmetric channels using a low complexity successive cancellation decoder. Although these codes, combined with successive cancellation, are optimal in this respect, their finite-length performance is not record breaking. We discuss several techniques through which their finite-length performance can be improved. We also study the performance of these codes in the context of source coding, both lossless and lossy, in the single-user context as well as for distributed applications. <s> BIB002 </s> Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <s> We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, up to L decoding paths are considered concurrently at each decoding stage. Simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of L. Thus it appears that the proposed list decoder bridges the gap between successive-cancellation and maximum-likelihood decoding of polar codes. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the L “best” paths. In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, straightforward implementation still requires O(L · n2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only O(L · n log n) time and O(L · n) space. <s> BIB003 </s> Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <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> BIB004 </s> Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <s> A 1.48mm 2 1024-bit belief propagation polar decoder is designed in 65nm CMOS. A unidirectional processing reduces the memory size to 45Kb, and simplifies the processing element. A double-column 1024-parallel architecture enables a 4.68Gb/s throughput. A bit-splitting latch-based register file accommodates logic in memory for an 85% density. The architecture and circuit techniques reduce the power to 478mW for an efficiency of 15.5pJ/b/iteration at 1.0V. At 475mV, the efficiency is improved to 3.6pJ/b/iteration for a throughput of 780Mb/s. <s> BIB005 </s> Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <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> BIB006 </s> Hardware Decoders for Polar Codes: An Overview <s> I. Introduction <s> Consider the transmission of a polar code of block length $N$ and rate $R$ over a binary memoryless symmetric channel $W$ and let $P_{\mathrm{ e}}$ be the block error probability under successive cancellation decoding. In this paper, we develop new bounds that characterize the relationship of the parameters $R$ , $N$ , $P_{\mathrm{ e}}$ , and the quality of the channel $W$ quantified by its capacity $I(W)$ and its Bhattacharyya parameter $Z(W)$ . In previous work, two main regimes were studied. In the error exponent regime, the channel $W$ and the rate $R are fixed, and it was proved that the error probability $P_{\mathrm{ e}}$ scales roughly as $2^{-\sqrt {N}}$ . In the scaling exponent approach, the channel $W$ and the error probability $P_{\mathrm{ e}}$ are fixed and it was proved that the gap to capacity $I(W)-R$ scales as $N^{-1/\mu }$ . Here, $\mu $ is called scaling exponent and this scaling exponent depends on the channel $W$ . A heuristic computation for the binary erasure channel (BEC) gives $\mu =3.627$ and it was shown that, for any channel $W$ , $3.579 \le \mu \le 5.702$ . Our contributions are as follows. First, we provide the tighter upper bound $\mu \le 4.714$ valid for any $W$ . With the same technique, we obtain the upper bound $\mu \le 3.639$ for the case of the BEC; this upper bound approaches very closely the heuristically derived value for the scaling exponent of the erasure channel. Second, we develop a trade-off between the gap to capacity $I(W)-R$ and the error probability $P_{\mathrm{ e}}$ as the functions of the block length $N$ . In other words, we neither fix the gap to capacity (error exponent regime) nor the error probability (scaling exponent regime), but we do consider a moderate deviations regime in which we study how fast both quantities, as the functions of the block length $N$ , simultaneously go to 0. Third, we prove that polar codes are not affected by error floors . To do so, we fix a polar code of block length $N$ and rate $R$ . Then, we vary the channel $W$ and study the impact of this variation on the error probability. We show that the error probability $P_{\mathrm{ e}}$ scales as the Bhattacharyya parameter $Z(W)$ raised to a power that scales roughly like ${\sqrt {N}}$ . This agrees with the scaling in the error exponent regime. <s> BIB007
Polar codes are the first codes with an explicit construction to asymptotically achieve the symmetric capacity of memoryless channels using a low-complexity, successive-cancellation (SC), decoding algorithm BIB001 . Additionally, they were shown to be free of error floors when used with binary-input symmetric memoryless channel, and are therefore attractive for wired communications and storage systems BIB007 . The serial nature of SC decoding limits the throughput of its implementations. Two approaches are used in literature to overcome the sequential nature of SC: exploiting the polar code structure to estimate multiple bits in parallel while still using SC-based algorithms  , BIB004 , and using the belief propagation (BP) decoding algorithm with parallel message passing BIB002 , BIB005 . Hardware decoders implementing these algorithms reach throughputs of multiple Gbps and can exceed 100 Gbps when unrolling is used  , BIB006 . While SC and BP based decoders are fast and efficient, their error-correction performance can be inferior to that of other modern codes such as low-density parity-check (LDPC) codes. However, when polar codes are decoded using the successive cancellation list (SCL) decoding algorithm BIB003 , their errorcorrection performance was shown to exceed that of LDPC codes used in recent wireless communication standards BIB003 . In this paper, we review the state of the art in hardware polar decoder implementations. We start with a review of polar codes in Section II. SC-based implementations are discussed in Section III and BP-based decoders in Section IV. Finally, SCL decoder implementations are reviewed in Section V.