## 3 Multipath Parameter Estimate Algorithm
### Computation Complexity Analysis  
As mentioned in the Introduction section, computation complexity is one of main factors that limit the practical application of parametric multipath mitigation techniques. For subspace estimation techniques, either MUSIC or ESPRT, all need singular value decomposition or eigenvalue decomposition computation, which is the key step when implemented by Field Programmable Gate Array (FPGA). Singular value decomposition includes a large amount of nonlinear computation with time complexity of \(O\left(n^{3}\right)\). However, the baseband signal is generally sampled by a relatively high sampling rate (such as 20 MHz is used in this paper). If the entire signal length is 10 ms, the total number of sample points \(N\) can be as large as 2 \(\times\) 10\({}^{5}\). Thus, it is almost impossible for hardware to process such a signal in real time. The problem of high computation complexity also plagues the maximum likelihood approach, such as MEDLL method. MEDLL estimates the multipath parameters by iteration operations. As the number of extra paths goes up, the total computational cost will increase exponentially. Motivated by the search of a simpler parametric technique for BOC signals, the frequency-domain approach we proposed in this paper does not require any eigenvalue decomposition or iteration operations. The main complexities are FFT operations and one-time IFFT operation which are easy for FPGA to fulfil. Besides, in comparison with the direct-FFT method, the proposed averaging-FFT method also excels at saving computational resources. The computation load it takes for the two stages is calculated below. Typically, for a hardware, \(N\)-point FFT operation requires \(0.5*N\log_{2}N\) times multiplication together with \(N\log_{2}N\) times addition. By recalling Figure 2, the total segment number \(M\) can be expressed as \((N-rL)/((1-r)L)\). For \(M\) times \(L\)-point FFT operation, the total computation load includes \(C_{m1}^{I}\) times multiplication and \(C_{a1}^{I}\) times addition, which is given by:  
\[ \begin{array}{l}C_{m1}^{I}=M\cdot\frac{L}{2}\cdot\log_{2}L=\frac{N-rL}{2(1-r )}\log_{2}L\\ C_{a1}^{I}=M\cdot L\cdot\log_{2}L=\frac{N-rL}{(1-r)}\log_{2}L\end{array}  \tag{21}\]  
Besides, extra computation is required to add windows and perform averaging. This part of computation amount contains \(C_{m2}^{I}\) times multiplication and \(C_{a2}^{I}\) times addition given by:  
\[ \begin{array}{l}C_{m2}^{I}=M\cdot L=\frac{N-rL}{(1-r)}\\ C_{a2}^{I}=L\ (M-1)\end{array}  \tag{22}\]  
So for state I, the total required multiplications \(C_{m}^{I}\) is \(C_{m1}^{I}+C_{m2}^{I}\), and addition \(C_{a}^{I}\) is \(C_{a1}^{I}+C_{a2}^{I}\). For stage II, total operations include one times \(L\)-point division and one times \(L\)-point IFFT operation with calculated amount of \(C_{m}^{II}\) times multiplication and \(C_{a}^{II}\) times addition given by:  
\[ \begin{array}{c}C_{a}^{II}=L+\frac{L}{2}\cdot\log_{2}L\\ C_{m}^{II}=L\cdot\log_{2}L\end{array}  \tag{23}\]  
Finally, the overall computation amount is the sum of the above two parts, namely we totally need \(C_{m}=C_{m}^{I}+C_{m}^{II}\) times multiplication and \(C_{a}=C_{a}^{I}+C_{a}^{II}\) times addition. After simplifying the equations, we have \(C_{m}\) and \(C_{a}\) as:  
\[ \begin{array}{c}C_{m}=\frac{N+L-2 rL}{2(1-r)}\log_{2}L+\frac{N+L-2 rL}{(1-r)} \\ C_{a}=ML\log_{2}L=\frac{N+L-2 rL}{(1-r)}\log_{2}L+\frac{N+L-2 rL}{(1-r)}\end{array}  \tag{24}\]  
whereas for the direct-FFT method, it totally takes one times \(N\)-point FFT, division and IFFT, so the total computation amount is \(N\cdot\log_{2}N+N\) times multiplication together with \(2N\cdot\log_{2}N\) times addition. In order to show the computation load reduction clearly, we assume the entire data length is 10 ms, sampling rate is 10 MHz and \(L\) is 128. The overlap rate \(r\) is set to 50%. Under these conditions, we compute the ratio of computation amount of two methods.