# Low Complexity List Decoding for Polar Codes with Multiple CRC Codes
## 2 SCL Decoding and Its Operational Complexity
### Operational Complexity of the SCL Decoding for the SCRC Scheme  
Because our concern is related to the overall computational complexity, we first define the operational complexity of a hardware-friendly LLR-based SCL decoding algorithm for the SCRC scheme. The overall complexity is counted in the number of addition-equivalent operations or simply additions for convenience. There are three main operations that largely affect the complexity. The first operation is the LLR calculation for the information vector \(\mathbf{u}\) in terms of the split channels. The SCL decoding runs the SC algorithm for each of all \(L\) decoding paths. Therefore, two types of LLR calculations are used as in the SC decoding. Note that the exact expressions for LLR calculation exist [25], but we consider their approximations preferred in implementation:  
\[\gamma_{c} = \mathrm{sgn}(\alpha)\mathrm{sgn}(\beta)\mathrm{min}(|\alpha|,| \beta|), \tag{1}\] \[\gamma_{\sigma} = \beta+(-1)^{u}\alpha, \tag{2}\]  
where \(\alpha\) and \(\beta\) are the input LLRs, and \(u\) is the input bit, and \(\mathrm{sgn}(\cdot)\) returns the sign of the argument [25; 26; 27]. Figure 2 shows the associated graph, where squares and circles represent the check and variable nodes, respectively. Those operations are termed the \"check/variable node operation\", respectively. Each node operation can be implemented with a single addition or its equivalent [25]. Consequently, the total computational complexity can be counted in the number of additions. Note that an SC decoding requires \(N\mathrm{log}_{2}N\) additions [1]. For the SCL decoding, roughly the list size \(L\) is a linear factor in complexity. However, the list size and the number of candidate decoding paths do not need to be the maximal size \(L\) during an entire decoding. The temporary list size can be taken into account. The change in complexity calculation regarding the temporary list size is not  
Figure 1: The temporary list size growth in the successive cancellation list (SCL) decoding (\(L=4\)). negligible. Let us denote the temporary number of decoding paths of the \(i\)-th decoding step by \(l_{i}\). More precisely, \(l_{i}\) is the number of existing paths before the decoding or processing of \(u_{i}\). The temporary list size does not increase if \(u_{i}\) is a frozen bit or \(l_{i}=L\). The transience of the list size in a decoding progress is shown in Figure 1. The temporary list size may increase slowly in the beginning because the front of sequence \(\mathbf{u}\) is mostly filled with frozen bits. When the sum of the numbers of check and variable node operations at the \(i\)-th SC decoding is denoted by \(n_{i}\), the total number of node operations for an entire SCL decoding is \(\sum_{i=1}^{N}l_{i}n_{i}\). Algorithm 1 calculates \(l_{i}\), and we denote this function by \(f(\cdot)\). The function \(f(\mathcal{A},l_{i},i)\) returns \(l_{i+1}\) for \(1\leq i\leq N-1\) (set \(l_{1}=1\)). Here, \(l_{i+1}\) is computed based on the SCL algorithm by checking whether \(i\in\mathcal{A}\) or not. Furthermore, \(n_{i}\) is \(\sum_{j=0}^{t}2^{j}\) where \(t\) is the number of consecutive zeros of \((i-1)_{2}\) from the rightmost bit [1]. For example, when \(N=8\) and \(i=7\), \((i-1)_{2}=110\) and \(t\) is \(1\). ```
0:\(\mathcal{A}\), \(l_{i}\), \(i\)
0:\(l_{i+1}\)
1:if\(i\in\mathcal{A}\)then
2:if\(2l_{i}\leq L\)then
3:\(l_{i+1}\gets 2l_{i}\);
4:else
5:\(l_{i+1}\gets L\);
6:endif
7:else
8:\(l_{i+1}\gets l_{i}\);
9:endif
10:return\(l_{i+1}\);
```  
**Algorithm 1** Calculation of \(l_{i+1}\) for the SCL decoding, \(f(\mathcal{A},l_{i},i)\)  
Second, sorting of PMs is considered for complexity evaluation. When an information bit is decoded, the sorting of \(2l_{i}\leq 2L\) PMs is needed at the \(i\)-th decoding step. In this paper, the complexity of sorting is represented in the number of additions. The sorting complexity depends on the type of sorting [25].