# DLSTM-Based Successive Cancellation Flipping Decoder for Short Polar Codes
## 4 Performance Analysis
### Decoding Complexity and Latency Analysis  
The SC flipping decoder starts with the SC decoder. The complexity of SC is \(O(N\log N)\). In constructing the flipping set, the complexity of the sorting operation on \(K\) probabilities is \(O(K\log K)\). When flipping one bit, there are no more than \(T_{1}\) additional attempts, and the complexity is \(O(T_{1}N\log N)\). When flipping two bits, the \(T_{1}\) candidate bits are sorted according to channel reliability with a complexity of \(O(T_{1}\log T_{1})\). Then, no more than \(T_{2}\) additional attempts are performed, and the complexity is \(O(T_{2}N\log N)\). Finally, if \(T_{1}>T_{2}\), the maximum complexity of the proposed algorithm is \(O(T_{1}N\log N)\). Otherwise, the maximum complexity is \(O(T_{2}N\log N)\). However, the flipping is only for the error sequence that fails the CRC detector, so the average complexity is related to the BLER. Therefore, the average complexity of the proposed algorithm is \(O((1+P_{e}(T_{1}+T_{2}))N\log N+K\log K+T_{1}\log T_{1})\), where \(P_{e}\) is the BLER of the SC decoding. As shown in Figure 14, the average decoding complexity is high because \(P_{e}\) is dramatically large at low \(E_{b}/N_{0}\). However, \(P_{e}\) decreases rapidly as \(E_{b}/N_{0}\) increases, and the average complexity rapidly decreases, finally converging to the complexity of the SC decoding. It can be noticed that the average decoding complexity is lower than the SCL decoding (\(L=4\)) and the DSCF decoding and slightly higher than the ML-MSCF decoding.  
It takes a lot of time to train an effective DLSTM network, but the whole training is done offline and can benefit from some acceleration platforms [24]. Therefore, the training process does not increase the decoding latency. However, the prediction time is calculated as part of the total decoding latency. Compared with the traditional approach, the prediction is an additional computational process. In Figure 15, the decoding latency represents the total time consumed for decoding as calculated by the CPU. The proposed algorithm consumes comparable time to the ML-MSCF decoder. When \(E_{b}/N_{0}=1.0\) dB, the consumed time is decreased by 11.41% and 27.68% compared to the DSCF decoder for both code lengths, which saves a lot of computation time by avoiding exponential and logarithmic operations, respectively. Compared to CA-SCL (\(L=2\)), the consumed time is lowered by 3.64% at \(N=32\) but comparable at \(N=64\). Compared with CA-SCL (\(L=4\)), the time consumption is reduced by 20.32% and 31.26%, respectively, and the time to try \(L\) decoding paths is reduced.  
Figure 13: Accuracy comparison of identifying the first error bit for \(P(64,32)\) at \(E_{b}/N_{0}=1.0\) dB.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Polar Codes** & **Layer** & \multicolumn{3}{c}{**Accuracy**} & **Total Param** \\ \hline \multirow{2}{*}{\(P(64,32)\)} & 2 & 57.2\% & 77.45\% & 87.4\% & 92.84\% & 68,128 \\  & 3 & 57.12\% & 77.32\% & 87.43\% & 92.94\% & 101,152 \\ \hline \multirow{2}{*}{\(P(16,8)\)} & 2 & 68.63\% & 91.8\% & 98.48\% & 99.86\% & 4360 \\  & 3 & 68.46\% & 91.81\% & 98.44\% & 99.85\% & 6472 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Comparison of two- and three-layer LSTM networks in predicting the first error bit.