# Improved Adaptive Successive Cancellation List Decoding of Polar Codes
## 4 Experiment and Analysis  
An adaptive segmented SCL decoding algorithm uses S as the starting bit of re-decoding in this experiment. In order to measure the computation complexity of the decoding algorithm, the average number of calculations of _PM_ value proposed in [21] is used. The segmented method is to divide the bits of information into two parts and decode them respectively, which is same as that in the SCAD-SCL algorithm. When the code length and code rate are 1024 and 0.5, respectively, the number of information bits are 512, the last 8-bit information of each segmentation are CRC bits. After adding the frozen bits, there are 748 bits at the first part of the information sequence and just 276 bits at the second part of the information sequence. There are 492 frozen bits at the first part while there are only 20 frozen bits at the second part. Because the second part of information sequence is shorter and contains more intensive information bits, the computational complexity reduction caused by adding \(S\) is not enough to compensate for its performance loss. Therefore, this experiment only adds \(S\) at the first 748 bits of information sequence. Figure 5: Modified SAD-SCL decoding process. In order to observe the change of computational complexity under different values of \(m\) more intuitively, the average number of calculations of \(PM\) values are counted when the decoding starts at \(S\)-th bit. The experimental parameters are shown in Table 1.  
Figure 6 shows the bit error rate (BER) performance curves of SAD-SCL (\(L_{max}\)) and CA-SCL (\(L=16\)) with a code length of 1024 and a code rate of 0.5 under AWGN channel and BPSK modulation. Figure 7 shows the frame error rate (FER) performance curves of SAD-SCL (\(L_{max}\)) and CA-SCL (\(L=16\)) under the same condition as Figure 6. As can be seen from Figures 6 and 7, with the increase of \(m\), the performance of adaptive algorithm designed by this experiment improves continuously. The performance of this algorithm is almost the same with that of SCL when \(m=140\)  
When the code length, the number of information bits and the length of CRC are \(N,K,M\), respectively, the AD-SCL algorithm needs to consume additional \((N-M)\times M\) times of addition calculation for CRC every decoding, while the SCAD-SCL algorithm and the SAD-SCL algorithm proposed in this paper need additional \((N/2-M)\times M\times 2\) times of addition for CRC each time. In addition, the SAD-SCL algorithm proposed in this paper needs a merge sorting of \(N/2\)-bits when choosing the starting point \(S\) of re-decoding. The merge sorting requires at most \((K/2)\log_{2}(K/2)-K+1\) additional calculations. Figure 8 shows the number of addition calculation times of CRC, two-segmentation CRC and merge sorting algorithms when the code rate is 0.5 and the code lengths are 64, 512, 1024, 2048, 4096. \begin{table}
\begin{tabular}{c c c c c c} \hline \multirow{2}{*}{\(m\)} & \multicolumn{2}{c}{_Eb/N0 = 0.5_} & _Eb/N0 = 1_ & _Eb/N0 = 1.5_ & _Eb/N0 = 2_ & _Eb/N0 = 2.5_ \\ \cline{2-6}  & _PM_ & _PM_ & _PM_ & _PM_ & _PM_ \\ \hline
50 & 16402 & 6548 & 1436 & 218 & 32 \\
80 & 16692 & 6199 & 1486 & 218 & 25 \\
100 & 16962 & 6352 & 1497 & 220 & 26 \\
140 & 17277 & 7132 & 1580 & 228 & 28 \\
256 & 19076 & 7983 & 1724 & 261 & 32 \\ \hline \end{tabular}
\end{table} 
Table 2: Calculation times of average _PM_ under different values of \(m\). Figure 7: FER Performance of SCL at \(L=16\) under different values of \(m\). It can be observed that the computation complexity of CRC and two-segmentation CRC is almost the same whatever the code length is, and the difference between them can be ignored. Compared with CRC and two-segmentation CRC, there exists an extra \(N/2\) merge sort in SAD-SCL. In [12], the calculation of CRC is almost negligible compared with the average number of calculations of value _PM_ (LLR value, etc.) each time in SCL. Therefore, the computation resource consumed by merge sort can be ignored in SCL.