## 2 Preliminaries
### Successive-Cancellation (SC) Decoding  
Arikan proposed a Successive cancellation (SC) decoding algorithm for polar codes [1], the SC decoder generates the estimate \(\hat{u}_{i}\) of \(i\)-th bit based on the previous \((i-1)\) estimates of \(\hat{u}^{i-1}=(\hat{u}_{1},\hat{u}_{2},...,\hat{u}_{i-1})\) and the channel output \(y^{N}=(y_{1},y_{2},...,y_{N})\), and we denote that \(y_{i}^{j}=(y_{i},y_{i+1},...,y_{j-1},y_{j})\) for \(1\leq i\leq j\leq N\). The transition probabilities \(W_{N}^{(i)}(y^{N},\hat{u}^{i-1}|u_{i})\) are used to define the \(N\) binary-input coordinate channels \(W_{N}^{(i)}\), which is denoted as follows:  
\[W_{N}^{(i)}(y^{N},\hat{u}^{i-1}|u_{i})=\sum_{u_{i+1}^{N}\in\mathcal{X}^{N-i}} \frac{1}{2^{N-1}}W_{N}(y^{N}|u^{N}), \tag{2}\]where \((y^{N},\hat{u}^{i-1})\) and \(u_{i}\) denote the output and input of \(W_{N}^{(i)}\), respectively. \(\mathcal{X}\) and \(W_{N}(y^{N}|u^{N})\) denote the input and transition probabilities of synthesized channel \(W_{N}\) after the channel combining phase [1]. Then, the log likelihood ratio (LLR) for the \(i\)-th bit is calculated by  
\[\hat{u}_{i}=\begin{cases}0,&L_{N}^{(i)}(y^{N},\hat{u}^{i-1})\geq 0,\\ 1,&\text{otherwise},\end{cases} \tag{3}\]  
where \(L_{N}^{(i)}(y^{N},\hat{u}_{i-1})\) is defined as  
\[L_{N}^{(i)}(y^{N},\hat{u}^{i-1})=\ln\frac{W_{N}^{(i)}(y^{N},\hat{u}^{i-1}|0)}{ W_{N}^{(i)}(y^{N},\hat{u}^{i-1}|1)}. \tag{4}\]  
Accordingly, each LLR can be calculated as follows:  
\[\begin{split} L_{N}^{(2i-1)}(y_{1}^{N},\hat{u}^{2i-2})=& 2\tanh^{-1}\Big{(}\tanh\big{(}\frac{L_{\frac{N}{2}}^{(i)}(y_{1}^{ \frac{N}{2}},\hat{u}_{o}^{2i-2}\oplus\hat{u}_{e}^{2i-2})}{2}\big{)}\tanh\big{(} \frac{L_{\frac{N}{2}}^{(i)}(y_{\frac{N}{2}+1}^{N},\hat{u}_{e}^{2i-2})}{2} \big{)}\Big{)},\\ L_{N}^{(2i)}(y_{1}^{N},\hat{u}^{2i-1})=& L_{\frac{N}{2}}^{(i)}(y_{ \frac{N}{2}+1}^{N},\hat{u}_{e}^{2i-2})+(-1)^{\hat{u}_{2i-1}}L_{\frac{N}{2}}^ {(i)}(y_{1}^{\frac{N}{2}},\hat{u}_{o}^{2i-2}\oplus\hat{u}_{e}^{2i-2}),\end{split} \tag{5}\]  
where \(\hat{u}_{o}^{i}\) and \(\hat{u}_{e}^{i}\) denote the sub-vectors consisting of elements of \(\hat{u}^{i}\) with odd and even indices, and \(\oplus\) denotes modulo-2 addition. According to the initial values, \(L_{1}^{(1)}(y_{i})=\ln[W(y_{i}|0)/W(y_{i}|1)]\), \(i\in 1,2,...,N\).  
In addition, the belief propagation (BP) decoding algorithm for polar codes is also proposed in [1], which can outperform the SC algorithm with higher complexity \(O(tN\log_{2}N)\), where \(t\) is the number of BP decoding iterations.  
The most effective polar decoding algorithm is the successive-cancellation list (SCL) decoding algorithm, which is proposed in [9; 10] as an upgrade version of the SC algorithm. SCL can be regarded as a joint optimization method of the SC algorithm and the maximum likelihood (ML) algorithm [34]. In the SCL decoding process, source bit is not decoded immediately at each step, instead of finding a maximum of \(l\) candidate paths. For each source bit \(u_{i}\), the SCL algorithm doubles the number of decoding paths by pursuing both \(u_{i}=0\) and \(u_{i}=1\) options, and then preserves the most likely \(l\) paths in a list and discards others. When all the source bits are traversed, the most reliable path is chosen as the output of the decoder. The complexity of SCL decoding is \(O(lN\log_{2}N)\).  
The simple successive cancellation (SSC) [35] is proposed to decrease the decoding complexity of the SC algorithm. The successive cancellation stack (SCS) [36] is proposed to reduce the complexity of SCL in some conditions. The SCL decoding can combine with cyclic redundancy check (CRC) in a concatenated coding fashion to further improve the performance of polar codes [11], which substantially outperformed the state-of-art turbo and LDCP codes.