# Low Complexity List Decoding for Polar Codes with Multiple CRC Codes
## 3 Low Complexity SCL Decoding with Multiple CRC Codes
### Optimization of \(J\)-Tuple CRC Positions with Respect to Complexity  
We can optimize the positions of CRCs to minimize the operational decoding complexity of the \(J\)-tuple CRC scheme. However, as mentioned above, since the decoding complexity of the \(J\)-tuple CRC scheme is variable depending on the decoding instance, we perform the optimization considering the average complexity based on the assumption that errors occur randomly in wrong paths. In order to simplify the problem, we input predetermined lengths of the \(J\)-tuple CRC codes \((p_{1},p_{2},...,p_{l})\) into the optimization. Through decoding experiments, we determine \((p_{1},p_{2},...,p_{l})\) empirically with regard to performance and complexity such that \(\sum p_{j}=P\), where \(P\) is the CRC length of the compared SCRC scheme. In addition, because the minimum distance of the CRC concatenated polar code is affected by the length of the last CRC, we allocate more bits to the last CRC code than others. Now let us first consider optimization of the positions of \(J\) CRCs under the basic SCL decoding. Note that the CRC positions are determined by the lengths of message subblocks. As mentioned, the basic SCL decoding for the \(J\)-tuple CRC scheme follows Algorithm 2 without instant bit decision. Therefore, for the \(J\)-tuple CRC scheme with a predetermined \(\mathbf{p}\), the optimization follows as:  
\[\mathbf{k}^{*}=\operatorname*{arg\,min}_{\mathbf{k}\in\mathbb{Z}^{J},\sum \
olimits_{k}j=K}C_{\mathbf{j}}^{\text{avg}},\text{ where }C_{\mathbf{j}}^{\text{avg}}\triangleq \sum(\bar{l}_{i}+\bar{l}_{i}n_{i}+\bar{s}_{i}), \tag{6}\]  
where \(\mathbb{Z}\) is the set of integers. The average temporary list \(\bar{\mathbf{i}}\) is obtained by Algorithm 3 with the input \(\mathcal{A}\), \(\mathbf{p}\) and \(\mathbf{k}\). Algorithm 3 determines the average temporary list size \(\bar{l}_{i}\) by \(f(\cdot)\) first, and when the \(j\)-th CRC is possible, reduces the \(\bar{l}_{i}\) according to the function of \(p_{j}\) as shown at line 5. Here, we assume that channel quality is high enough so that the correct path always exists in the list, and many errors randomly occur in wrong paths. Then, \(\bar{l}_{i}-1\) paths survive with probability of \(1/2^{p_{j}}\) by the \(j\)-th CRC. Through the Monte Carlo simulation introduced in Section 4, we confirmed that the estimated complexity based on this assumption is very close to the experimental one. The average sorting complexity vector \(\mathbf{\hat{s}}=(s_{1},s_{2},...,s_{N})\) is generated by Equation (3) with \(\bar{\mathbf{i}}\) obtained by Algorithm 3. Note that the optimization is appropriate for a small \(J\) because it is a joint optimization of \(J\) variables. In order to avoid high complexity search for a large \(J\), one can apply a greedy search that determines CRC positions, one after another. For a lower complexity implementation, the ID-SCL decoding is combined with the optimization of the \(J\)-tuple CRC positions of Equation (6). As mentioned in Section 3.1, the ID-SCL decoding instantly decides the information bits \(\in\mathcal{A}_{g}\), maintaining the temporary list size. Assume the good information set \(\mathcal{A}_{g}\) is defined by \(\mathcal{A}_{g}=\{i:P_{e}^{i}\leq\sigma_{\text{Th}}\}\subset\mathcal{A}\), where \(P_{e}^{i}\) is the bit error probability of the \(i\)-th split channel, and \(\sigma_{\text{Th}}\) is a certain threshold. Let us consider the effect of the ID-SCL decoding on the CRC position optimization. For example, assume there exists a burst of good split channels defined by \(\mathcal{A}_{g}\), and a CRC is located before the burst of good split channels. Then, the CRC reduces the number of decoding paths, and the number of survival paths remains until the end of the burst because of the ID-SCL decoding. Eventually, the interworking of the ID-SCL decoding and CRC position optimization will give obvious complexity reduction. A more detailed example about the temporary list size is presented in Section 4.