## 3 System Design
### Acquisition in High-Sensitivity Mode
#### 3.4.2 Computation of Large FFTs in the FPGA  
When working in high-sensitivity mode, the acquisition hardware accelerator computes the circular cross-correlation between the received signals and a local replica of the Galileo tiered codes over a time span of 100 ms. The circular cross-correlation is computed in the frequency domain, enabling efficient implementation within parallel processing architectures. This approach is particularly advantageous for applications requiring real-time signal processing. Many HS-GNSS receivers compute the CAF in the frequency domain using FFT-based techniques for their computational efficiency [7]. Performing circular correlations over a duration of 100 ms requires the use of very large FFTs, with sizes on the order of at least several hundred thousand samples. However, FPGA FFT IP cores are limited in length, requiring the FFT length to be a power of two. For this reason, the proposed FPGA implementation computes large FFTs by combining multiple smaller FFTs with complex exponentials. This approach is extended to IFFTs, following a similar procedure. To elaborate, this approach can be explained as follows: a large \(N\)-point Discrete Fourier Transform (DFT) can be computed by utilizing two smaller DFTs, each of \(\frac{N}{2}\) points. This is achieved by separating the input sequence into even samples (\(x_{2n}\)) and odd samples (\(x_{2n+1}\)), as shown in Equation (4) [24]. \[X_{k} =\sum_{n=0}^{N-1}x_{n}e^{-\frac{2\pi\ln(2n)}{N}} \tag{4}\] \[=\sum_{n=0}^{\frac{N}{2}-1}x_{2n}e^{-\frac{2\pi\ln(2n)}{N/2}}+e^{- \frac{2\pi\ln}{N}-1}x_{2n+1}e^{-\frac{2\pi\ln(2n+1)}{N}}\] \[=\sum_{n=0}^{\frac{N}{2}-1}x_{2n}e^{-\frac{2\pi\ln n}{N/2}}+e^{- \frac{2\pi\ln}{N}}\sum_{n=0}^{\frac{N}{2}-1}x_{2n+1}e^{-\frac{2\pi\ln n}{N/2}}\]  
In this computation, the N-point DFT is conceptually divided into two halves. The first half of the DFT corresponds to samples \(k=0\) to \(k=\frac{N}{2}-1\) and is computed as the addition of two DFTs, each of \(\frac{N}{2}\) points, combined with complex exponentials, as shown in Equation (4) [24]. The second half of the DFT corresponds to samples \(k=\frac{N}{2}\) to \(k=N-1\) and is also computed as the addition of the same two \(\frac{N}{2}\)-point DFTs, but combined with different complex exponentials. This is shown in Equation (5), where \(k=\frac{N}{2}+t\), \(0\leq t<\frac{N}{2}\)[24]. \[ \begin{split} X_{k}=X_{N/2+t}&=\sum_{n=0}^{\frac{N }{2}-1}x_{2n}e^{-\frac{(2\pi(N/2+t)n}{N/2}}+e^{-\frac{2\pi\ln(N/2+t)}{N}}\sum_{ n=0}^{\frac{N}{2}-1}x_{2n+1}e^{-\frac{2\pi(N/2+t)n}{N/2}}\\ &=\sum_{n=0}^{\frac{N}{2}-1}x_{2n}e^{-\frac{2\pi\ln n}{N/2}}-e^{ -\frac{2\pi t}{N}}\sum_{n=0}^{\frac{N}{2}-1}x_{2n+1}e^{-\frac{2\pi\ln n}{N/2}} \end{split}  \tag{5}\]  
In a generalization of this approach, the computation of an \(N\)-point DFT involves combining \(P\) DFTs, each of \(\frac{N}{P}\) points, as illustrated in Equation (6). \[X_{k}=\sum_{p=0}^{p-1}(e^{-\frac{2\pi\ln p}{N}}\sum_{n=0}^{\frac{N}{2}-1}x_{( Pn+p)}e^{-\frac{2\pi\ln n}{(N/P)}}) \tag{6}\]  
This method conceptualizes the computation of the \(N\)-point DFT in \(P\) sections: from samples \(k=0\) to \(k=\frac{N}{P}-1\), then from samples \(k=\frac{N}{P}\) to \(k=2\frac{N}{P}-1\), and so forth, up to the section comprising samples \(k=(P-1)\frac{N}{P}\) to \(k=N-1\). Each section is computed as the summation of \(P\) identical DFTs of \(\frac{N}{P}\) points, combined with different complex exponentials. This is shown by the fact that if \(k=s\frac{N}{P}+t\), where \(0\leq t<N/P\) and \(0\leq s<P\) (the \(k\)-th sample is in the \(s\)-th section), then Equation (6) can be expressed as Equation (7). \[ \begin{split} X_{k}&=X_{sN/P+t}=\sum_{p=0}^{p-1}(e^ {-\frac{2\pi(N/s+t)p}{N}}\sum_{n=0}^{\frac{N}{2}-1}x_{(Pn+p)}e^{-\frac{(2\pi(N /P)+t)n}{(N/P)}})\\ &=\sum_{p=0}^{p-1}(e^{-\frac{2\pi(N/s+t)p}{N}}\sum_{n=0}^{\frac {N}{2}-1}x_{(Pn+p)}e^{-\frac{2\pi\ln n}{N/P}})\end{split}  \tag{7}\]  
The proposed FPGA acquisition hardware accelerator uses this approach to compute large FFTs.