# Low Complexity List Decoding for Polar Codes with Multiple CRC Codes
## 2 SCL Decoding and Its Operational Complexity
### Polar Encoding and SCL Decoding  
We only consider binary polar codes with the kernel matrix \(\mathbf{F}=\left[\begin{smallmatrix}1&0\\ 1&1\end{smallmatrix}\right]\) and \(n\)-fold polarization, where \(n\) is a positive integer. Then, for \(N=2^{n}\) copies of a given symmetric B-DMC \(W\), the channel combining and splitting generate \(N\) split channels whose capacities polarize to one or zero [1]. The fraction of good split channels approaches the capacity of \(W\) as \(N\) goes to infinity. This phenomenon is called the \"channel polarization\". Polar coding transmits information through the good split channels that have higher capacity. The index set of the good split channels is called the \"information set\", and is denoted by \(\mathcal{A}\). For a row vector \(\mathbf{u}=(u_{1},u_{2},...,u_{N})\) consisting of the information part \((u_{i}:i\in\mathcal{A})\) and the frozen part \((u_{i}:i\in\mathcal{A}^{c})\), the codeword vector is given as \(\mathbf{x}=(x_{1},x_{2},...,x_{N})=\mathbf{u}\mathbf{G}_{N}\) where \(\mathbf{G}_{N}=\mathbf{B}_{N}\mathbf{F}^{\otimes n}\) is the generator matrix, and \(\mathbf{B}_{N}\) is the bit-reversal permutation matrix (see [1] for more details). If \(|\mathcal{A}|=K\), the code rate \(R\) is equal to \(K/N\).  
SC decoding is the first decoding method of polar codes [1]. Each element of \(\mathbf{u}\) is successively decoded in the increasing order of index. At the \(i\)-th decoding step, if \(i\in\mathcal{A}^{c}\), \(\hat{u}_{i}\) is set as a frozen bit. Otherwise, \(u_{i}\) is decided by a maximum likelihood (ML) rule such as \(\hat{u}_{i}=\operatorname*{argmax}_{u_{i}=0,1}\Pr(y,(\hat{u}_{1},...,\hat{u}_{i -1})|u_{i})\) with the aid of the previously estimated vector \((\hat{u}_{1},...,\hat{u}_{i-1})\), where \(\mathbf{y}\) is the output of the vector channel of \(W\)When \(i=1\), \((\hat{u}_{1},...,\hat{u}_{i-1})\) is defined as a void. At last, the SC decoder outputs \(\hat{\mathbf{u}}\), which corresponds to a single decoding path.  
Later, SCL decoding was proposed to improve the error performance of finite-length polar codes [13]. The SCL decoding maintains a list of \(L\) most likely paths down to the bottom of the decoding tree as depicted in Figure 1. At the decoding step of an information \(u_{i}\), the number of decoding paths is doubled until the list size reaches \(L\) without path selection. If the number of candidate paths reached \(L\), then, in the next step, \(2L\) paths are generated and the best \(L\) paths are selected based on their PMs. For a frozen bit, the number of paths does not need to increase because we have only to take a valid child branch for each path. Finally, after decoding of all \(u_{i}\)'s, the best path is selected among \(L\) survivors.  
The CRC concatenation before polar encoding and CRC-aided SCL decoding are used to further improve the error performance [12]. In [12], the message is CRC-encoded and its parity is usually appended at the end of the message. The CRC code is used for the verification of survived decoding paths at the last stage of SCL decoding. If the CRC code of length \(P\) is concatenated, then \(|\mathcal{A}|=K+P\), but the code rate \(R\) is maintained as \(K/N\). In this paper, the polar code that uses a single CRC code is termed the \"Single CRC (SCRC) scheme\".