## 9 Complexity Requirements of MBMF-SIC and MSCE  
The complexity of the MBMF-SIC discussed in this chapter is determined by the following parameters: the number of multi-feedback candidates \(B\), the reduced size truncated channel matrix \(Q=D\), the number of subcarriers \(N_{s}\) and the number of iterations for the cancellation \(P\). Following the description of the algorithm in Algorithm 1 with QPSK, the computation of the algorithm for the initial iteration is slightly different from that for the later iterations. However, the computational complexity of the initial iteration is almost identical to that of the later iterations. This is because the initial LLRs first need to be calculated by the output of the matched filter, rather than the direct use of the output of the channel decoder. The computational complexity comes from two aspects: (1) the multi-feedback generation; and (2) the multi-feedback cancellation. The computation of feedback symbols generation for \(k=0,1,\ldots,N_{s}-1\) in Step 11 requires a maximum of \(8N_{s}BD\) complex additions (CAs) for GSG and TSG, and the computation of the cancellation in Steps 12 and 13 for \(k=0,1,\ldots,N_{s}-1\) requires \(N_{s}B(8D^{2}+6D+1)\) complex multiplications (CMs) and \(N_{s}B(8D^{2}+6D+2)\) CAs. In Step 14, the computation of average probability of \(\text{Pr}(s_{k}(i)=+1|\mathbf{y}_{k}^{*}),i=1,2\) and \(k=0,1,\ldots,N_{s}-1\) and the corresponding LLR leads to \(N_{s}B\) CAs. Hence, the total number of complex operations for one iteration required by the MFMB-SIC is \(N_{s}(16 BD^{2}+20 BD+4B)\), and the SINR ordering requires a total of \(\mathcal{O}(N_{s}\log N_{s})+N_{s}\) complex operations [14]. The complexity comparison of ICI cancellation techniques has been made in Table 1. The complexity of MBMF-SIC and MF-PIC is moderate compared to MF-SIC and much lower than that of conventional MMSE-SIC and banded MMSE-SIC.  
Furthermore, the MSCE requires a maximum of \(\mathcal{O}(TL^{2})+\mathcal{O}(2N_{s}L)\) complex operations for each OFDM symbol in the \(p\)-th iteration. This is because the size of the matrix inversion used in Equation (60) is only related to the number of channel paths \(L\). The complexity comparison between different channel estimation techniques for rapidly time-varying channels is presented in Table 2. Note that pilot-assisted LS denotes the pilot-assisted LS channel estimation, which uses the discrete Karhueen-Loeve basis expansion model (BEM) to approximate the time-varying channels with the limited number of expansion coefficients [36]. The number of expansion coefficients is lower bounded by \(2\lceil f_{d}T_{\text{OFDM}}\rceil+1=2D-1\) as described in [35]. The significant advantage of MSCE over the method in [36] is the use of linear interpolation to approximate the channels between two segments in the OFDM symbol. Hence, the MSCE can be considered as a special representation of BEM with two expansion coefficients. Compared to SBCE, the complexity of MSCE is a bit higher; because the matrix inversion with the size \(L\) is required to estimate the channels in the mid-point of each segment.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Algorithm** & **Complex Operations** \\ \hline MMSE-SIC [37] & \(\mathcal{O}(N_{s}^{3})+\mathcal{O}(4N_{s}^{2}D^{2})+\mathcal{O}(N_{s}^{2})\) \\ banded MMSE-SIC [4] & \(N_{s}(\frac{64}{3}D^{3}+80D^{2}+\frac{104}{3}D+4)\) \\ MF-SIC [16] & \(N_{s}(32D^{2}+16D+3)\) \\ MF-PIC [17] & \(N_{s}(32D^{2}+22D+1)\) \\ RSL [3] & \(N_{s}(28D^{3}+60D^{2})\) \\ BP-MAP [15] & \(\mathcal{O}(N_{s}|\mathcal{C}|^{21/2})\)* \(|\mathcal{C}|\) denotes the number of constellation points \\ MBMF-SIC & \(N_{s}(16 BD^{2}+20 BD+4B)\) \\ MBMF-SIC + SINR ordering & \(N_{s}(16 BD^{2}+20 BD+4B)+\mathcal{O}(N_{s}\log N_{s})+N_{s}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Complexity comparison between different interference cancellation techniques for the \(p\)-th iteration. BP, belief propagation; RSL, recursive-SIC-linear-MMSE.