3.1 Channel polarization

Channel polarization is a transformation of N independent copies of a channel W into a new set of N channels $\mathit{\{}{W}_N^{\left(i\right)}:\mathrm{1}\le i\le N\mathit{\}}$ , where, for large N, the symmetric channel capacity $I\left(W_N^{\left(i\right)}\right)$ approaches either 0 (completely noisy) or 1 (completely error-free). Figure 1 shows an example for a set of two channels before and after the polarization. The channel with decreased capacity is called W⁻ (red), and the other with the improved capacity is called W⁺ (blue).

3.2 Code construction

The butterfly structure in Fig. 1b represents the smallest possible Polar Code with N=2. Larger codes can be built by recursively combining two codes of length N∕2 to a new code of length N. Therefore, to create a code of length N, ${\mathrm{2}}^{{\log }_{\mathrm{2}}N}$ steps of combining are necessary. The code rate N∕K is then selected by setting the least reliable channels to fixed known values, e.g., 0 (called frozen bits), and using the more reliable channels to transmit the information bits. Figure 2 shows the structure of a Polar Code of length N=8 and K=4 information bits u_1…4. The frozen bits are set to 0.

Polar Codes are defined with a generator matrix G_N that is built by using the Kronecker power ${\mathbf{F}}_{\mathbf{2}}^{\otimes {\log }_{\mathbf{2}}\mathbf{N}}$ of ${\mathbf{F}}_{\mathbf{2}}=\left[\begin{array}{ll}\mathrm{1}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}\end{array}\right]$. Note that F₂ represents the butterfly structure of Fig. 1b, and the Kronecker power equals the combination of smaller codes into bigger ones.

3.3 Encoding

The encoding is shown in Fig. 2a for a $N=\mathrm{8}/K=\mathrm{4}$ Polar Code. A sequence of information bits u_1…4 and frozen bits is passed through the code structure from left to right to get a codeword x_1…8 of length N=8. Formally, the encoding is x=uG_N with G_N being the generator matrix and u the information vector that includes the frozen bits.

3.4 Decoding

The decoding of Polar Codes can be seen as the reversal of the encoding. Thus, decoding passes the received channel values y from left to right as shown in Fig. 2b.

But while the encoding is simply a linear transformation, the decoding is the estimation of the originally transmitted information bits $\widehat{\mathit{u}}$ from the received channel values y, commonly represented as Log Likelihood Ratios (LLRs). LLRs are a measure of the probability of a received value corresponding to either 0 or 1 and are defined as $\mathrm{LLR}\left(y_i\right)=\log \left(\frac{P\left(y_i\right|\mathrm{1})}{P\left(y_i\right|\mathrm{0})}\right)$. This estimation can be done by different algorithms.

The most popular decoding algorithm for Polar Codes is the Successive Cancellation (SC) algorithm that was presented by Arikan (2009) in his original paper. SC passes the received channel values from left to right over the Polar Factor Graph in Fig. 2b. Four types of operations have to be performed for every butterfly structure (see Sect. 4.1). The decoding of the individual bits is performed in a recursive manner on the Polar Factor Graph.

An extension of SC is the Successive Cancellation List (SCL) algorithm. In this algorithm a list of L most probable decisions are considered, i.e., L codewords are decoded. The final codeword is selected out of the list by, e.g., the highest overall probability or by other checks like a Cyclic Redundancy Check (CRC). The SC and SCL are sequential algorithms.

An inherently parallel decoding algorithm is the Belief Propagation (BP) algorithm for Polar Codes. It iterates from left to right and reverse over the Polar Code Factor Graph from Fig. 2b. Thus, the bits are decoded in an iterative manner similar to the BP for Low Density Parity Check (LDPC) codes. However, Abbas et al. (2017) showed that up to 100 iterations are necessary to match the error correcting performance of the SC algorithm.

The SCAN algorithm (Fayyaz and Barry, 2014) uses the general processing order of the SC algorithm in combination with the exchange of soft values from the BP algorithm. The SCAN decoding algorithm is highly parameterizable in terms of processing order of the nodes and allows various trade-offs.

Figure 3 shows the communications performance of the SC, SCL, and SCAN algorithms, respectively. While SC and SCAN provide similar communications performance and mostly differ in the hard or soft output, the SCL algorithm performs significantly better, but at the cost of increased decoding complexity. The SCL was simulated with list size L=4 and the SCAN algorithm with one iteration I=1 for a code of $N=\mathrm{1024},K=\mathrm{512}$ over an AWGN channel and floating-point arithmetic. The Polar Code was constructed by using the gaussian approximation method (Vangala et al., 2015) for a design Signal-to-Noise Ratio (SNR) of 0 dB.

Figure 3Error Correction Performance in Frame Error Rate (FER) over the SNR in E_b∕N₀ for a Polar Code of $N=\mathrm{1024}/K=\mathrm{512}$.

Download

Figure 4Polar Code Representations.

Download

4.1 Node operations

As said, all decoding algorithms can be mapped onto a depth- (SC, SCL, SCAN) or breadth-first search (BP) on this Polar Factor Tree. Here we focus on the first class of algorithms. The differences in the three decoding algorithm is in the node operations while the tree is traversed.

Figure 4c and d show the performed operations of one butterfly unit and one node, respectively. α_v, β_l, and β_r denote vectors that are input to a node (marked in gray). α_l, α_r, and β_v are corresponding vectors calculated by the node (marked red). The notation ${\mathit{\alpha }}_{v_i}$ with $i=\mathrm{0},\mathrm{\dots },N$ is used to address one element of the corresponding vector. The dimensions of the vectors depend on the tree level t, starting with t=0 for the root node. For the vectors α_v and β_v the length is N∕2^t and for α_l, β_l, α_r, and β_r the length is $N/{\mathrm{2}}^{t+\mathrm{1}}$.

Table 1Node operations of different decoding algorithms

$f(a,b)\approx sign\left(a\right)sign\left(b\right)min\left(\right|a|,|b\left|\right)$ (Leroux et al., 2011).

Download Print Version | Download XLSX

Every node (Fig. 4d) that is visited during depth-first search first calculates a new vector of LLRs α_l and sends it to the left child. In the backtracking phase of the search, the left child provides β_l to this node. Next, α_r is calculated and sent to the right child, awaiting the result β_r of the right child. Finally β_v is calculated and sent to its parent node. Table 1 shows the corresponding equations for the calculation of the vectors α_l, α_r, and β_v for the SC, SCL, and SCAN decoding algorithms, respectively. ⊕ denotes the binary addition and × implying that the operation has to be performed L times.

Table 2Optimized pipeline stages for different codes

Download Print Version | Download XLSX

Figure 5Architectural template for unrolled tree traversals.

Download

Figure 6Pipeline Optimization through tree minimization for a Polar Code of $N=\mathrm{16},K=\mathrm{8}$.

Download

Please note that for SCL decoding algorithm, additional effort has to be spent within the nodes for the list management, in particular the sorting and pruning of the list according to path metrics which are not shown here for simplicity. Also, the leaf operations differ slightly between SC, SCL, and SCAN. While SC and SCL decide for either 1 or 0 in the leaf node, the SCAN decoding algorithm follows the BP approach for Polar Codes and propagates constants, i.e., infinity for frozen bits and zero for information bits.

4.2 Unrolling the tree traversal

To build high-throughput decoders, pipelining is the most efficient way to gain maximal parallelism and at the same time maximized data locality. For iterative decoding algorithms like the BP, pipelining can be achieved by unrolling the iterations and pipelining the different stages. The number of pipelining stages corresponds to the number of iterations. Such an architecture was for the first time demonstrated for LDPC decoding by Schläfer et al. (2013). In their paper, a min-sum LDPC decoding algorithm was unrolled over 9 iterations for an $N=\mathrm{672},\mathrm{Rate}=\mathrm{13}/\mathrm{16}$ LDPC code, achieving an outstanding throughput and energy efficiency, but at the cost of flexibility.

Here we focus on SC, SCL, and SCAN that perform depth-first traversal of the Polar Factor Tree during decoding. Comparable to unrolled LDPC decoding, we can similarly unroll the tree traversal: Whenever a tree node is visited during the traversal, a corresponding pipeline stage is instantiated. The resulting generic architectural template is shown in Fig. 5: Panel a shows the tree traversal and panel b the corresponding pipeline stages. This model serves as a generic model for all decoding algorithms that traverse the tree, i.e., SC, SCL, and SCAN. The only difference between decoders for different algorithms is in the node operations in the pipeline stages.

For a binary balanced tree with N leaf nodes, $\mathrm{2}\cdot (\mathrm{2}N-\mathrm{2})$ node-visits are performed during the depth-first traversal which results in $\mathrm{2}\cdot (\mathrm{2}N-\mathrm{2})$ pipeline stages, respectively.

Giard et al. (2015) have first published this concept of unrolling for Polar Codes and the SC algorithm. Later it was presented by Giard et al. (2016) also for the SCL algorithm. Our approach presented in this paper is a generalized model and valid for all decoding algorithms based on the traversal of the Polar Factor Tree.

4.3 Pipeline optimization

Since the number of traversed nodes' visits directly maps into the amount of pipeline stages, minimizing the tree corresponds to minimizing the number of pipeline stages. A smaller tree therefore leads to less pipeline stages, thus lower latency, improved area, and energy efficiency. Sarkis et al. (2014) have proposed some techniques to reduce the size of the Polar Factor Tree without a loss in error correction performance.

Figure 7Design Space (red: focus in this paper).

Download

Figure 8Polar Code decoder exploration framework.

Download

Figure 9Pipeline architectures.

Download

Table 3Implementation results for a SCAN decoder with $N=\mathrm{128}/K=\mathrm{64}$ for different architectures on a 28 nm FD-SOI technology

Download Print Version | Download XLSX

A reduction is achieved by first replacing complete subtrees with a single node that can decode the subtree in one step. Two possible subtree optimizations are shown in Fig. 6: A 4 bit subtree with three frozen and one information bit as leaves, equaling a repetition code, is replaced by a new specialized node (marked red). Similar a 4 bit subtree with only one frozen bit and three information bits as leaves, acting like a simple parity check code, is likewise replaced by a new specialized node (marked green).

The tree can be further reduced by optimizing homogeneous subtrees (composed of either completely frozen or completely information nodes) and merging them into their parent node. This is valid because a subtree with only frozen bit leaves (marked white in Fig. 6) equals a Rate-0 code, that doesn't carry any information but only noise. Accordingly a subtree with only information bits as leaves (marked blue) equals a Rate-1 code that consists of only information and no redundancy, therefore has no error correction capabilities.

Table 2 shows the number of node visits, or pipeline stages, for selected Polar Codes with different code lengths and code rates, respectively, before and after the optimization for the SCAN decoding algorithm. The numbers for the optimized pipeline stages are created by traversing the reduced tree described in this section. While the improvement in the number of pipeline stages and therefore also latency and area are significant, it also becomes obvious, that every change in the code length or code rate results in a different tree and, thus, a different architecture.

5.1 Case study

To show the performance of our framework we present as a case study, an unrolled SCAN Polar Code decoder with one iteration. We further show various design trade-offs. There are two extreme cases. We can remove all registers from the pipeline stages. This results in a pure combinatorial circuit (Fig. 9a). Advantages are low area, low power, and low latency. Main disadvantage is low throughput. The other extreme is to have a pipeline register between each stage (Fig. 9b). Advantage is high-throughput, disadvantages are high area, high power, and a high latency. Our framework allows to balance the register count between the two extrema using its internal timing engine. So, for a given throughput constraint, the number and optimum position of registers can be automatically calculated (Fig. 9c). Table 3 shows the various trade-offs. Results are after place&route and worst case Process-Voltage-Temperature (PVT) on a 28 nm FD-SOI technology. Throughput refers to coded bits.

The first two columns show the pure combinatorial and fully pipelined architecture, respectively. Column 3 shows the architecture for a throughput constraint of 100 Gbps. All three architectures were automatically generated with our framework. The last column shows the fastest SCAN decoder implementation published (Lin et al., 2017). However, their decoder uses a sequential processing, a different code and a different technology. To give at least a first estimate we scaled the decoder down to 28 nm. Our architecture is more than 40 times faster and shows a much better area efficiency,

To the best of our knowledge, this fully pipelined architecture is the fastest SCAN Polar Code decoder, while the partially pipelined architecture is the most area efficient published so far.