# Improvement of Fast Simplified Successive-Cancellation Decoder for Polar Codes
## 2 Background  
A polar code is defined by three parameters, \((N,R,\mathcal{A})\), where the code length \(N=2^{m}\), cardinality of information set \(\mathcal{A}\) is \(K\), and rate \(R=K/N\). The set of the frozen bits indices are denoted by \(\mathcal{A}^{c}\), and all frozen bits \(u_{\mathcal{A}_{c}}\) are set to zero. For simplicity, we denote \((u_{1},u_{2},...,u_{N})\) as \(u_{1}^{N}\).  
The original SC decoding graph can be converted to a message-passing algorithm executed on a full binary tree. The SC decoding process is executed sequentially and each leaf node is activated. The SC decoding tree for an (16,8) polar code (P(16, 8)) is shown in Figure 2a. The R-0 and R-1 nodes are shown as white and black circles, respectively, and the R-other nodes are represented by squares. The messages passed to child nodes are log-likelihood ratios (LLRs) denoted \(\boldsymbol{\alpha}_{v}\), while those passed to parent nodes are bit estimates denoted \(\boldsymbol{\beta}_{v}\). Messages to a left child node are calculated using the sum-product update rules [12]:  
\[\boldsymbol{\alpha}_{v_{l}}[i]=2\tanh^{-1}(\tanh(\frac{\boldsymbol{\alpha}_{v }[2i-1]}{2})\tanh(\frac{\boldsymbol{\alpha}_{v}[2i]}{2})),for\;\;i=1:2^{m-d_{v }-1} \tag{1}\]  
where \(d_{v}\) is the depth of the current constituent code.  
Messages to a right child node are calculated using the formula  
\[\boldsymbol{\alpha}_{v_{l}}[i]=\boldsymbol{\alpha}_{v}[2i-1](1-2\boldsymbol{ \beta}_{v_{l}}[i])+\boldsymbol{\alpha}_{v}[2i],for\;\;i=1:2^{m-d_{v}-1} \tag{2}\]  
where \(\boldsymbol{\beta}_{v_{l}}\) is the bit estimate from the left child.  
The locations of some frozen bits indices are special, and these can be utilized to reduce the decoding latency. This concept was first employed by the SSC decoder to reduce the latency. For a sub-tree rooted at node \(v\), \(I_{v}\) denotes the set of all leaf nodes indices. A node \(v\) is a R-1 (R-0) node if \(I_{v}\subset\mathcal{A}(I_{v}\subset[N]\setminus\mathcal{A})\). A sub-tree corresponding to the R-0 and R-1 nodes can be cut, removing the need to traverse the sub-tree [4]. The R-other nodes still follow the original SC decoder rule. The SSC pruned tree is shown in Figure 2b, corresponding to the same code as for Figure 2a. The SSC decoder reduces the latency and number of calculations for the real value vector \(\boldsymbol{\alpha}_{v}\). As the gains of the latency reduction are obviously large, many studies have been conducted to improve the SSC decoder [5; 6; 7; 8; 9; 10; 11].  
The Fast-SSC decoder recognizes the other two constituent codes, namely, the Rep codes, for which only the last leaf is not a frozen bit, and the SPC codes, for which only the first leaf is a frozen bit [5]. A node \(v\), corresponding to a constituent code of length \(N_{v}\), receives the soft-message vector \(\boldsymbol{\alpha}_{v}\) to the constituent decoder; the Rep and SPC codes can provide an codeword estimate \(\boldsymbol{\beta}_{v}\) in parallel using low-complexity algorithms [5]. The output for a Rep code is  
\[\boldsymbol{\beta}_{v}[i]=\begin{cases}0,&\sum_{i}\boldsymbol{\alpha}_{v}[i] \geq 0,\\ 1,&\text{otherwise}.\end{cases} \tag{3}\]  
Figure 2: Decoder trees corresponding to (**a**) SC and (**b**) SSC decoding algorithms for P(16, 8).  
The output of the SPC code is  
\[\beta_{v}[i]=\begin{cases}\beta_{v}[i]\oplus\text{parity},&i=\arg\min_{i}\lvert \boldsymbol{\alpha}_{v}[i]\rvert\,,\\ \beta_{v}[i],&\text{otherwise}.\end{cases} \tag{4}\]  
The parity of a SPC code is calculated as  
\[\text{parity}=\bigoplus_{t=0}^{N_{v}-1}\beta_{v}[i], \tag{5}\]  
\[\beta_{v}[i]=\text{h}(\boldsymbol{\alpha}_{v}[i])=\begin{cases}0,&\boldsymbol {\alpha}_{v}[i]\geq 0,\\ 1,&\text{otherwise}.\end{cases} \tag{6}\]  
where \(\text{h}(\boldsymbol{\alpha}_{v}[i])\) is the hard-decision function based on \(\boldsymbol{\alpha}_{v}[i]\).  
The Fast-SSC decoder provides a significant latency reduction compared to the SC decoder. However, the decoding latency of the Fast-SSC decoder is constant without the influence of the channel condition.