# Variance-Triggered Two-Step GPS Acquisition
## 3 Variance-Triggered Two-Step Acquisition
### The Fine Search Step  
Every time a peak is detected in the CS step, the FS step is triggered. The FS step performs a more precise search for the phase and frequency pair in a confined region of the search space around the pair estimated in the CS step.  
Besides the reduced search region, there are other two key differences between the CS step and the FS step. One difference is that while in the CS step the whole Doppler frequency range is completely covered, in the FS step only a small region around the prospecting peak is covered, namely the region between the two frequency bins around the probing frequency. Another key difference is that the search in the phase dimension is reduced to the refinement of the estimated phase using only a few intra-phase displacements, i.e., only \(2P\) phase shifts are searched for.  
Figure 5: Two-step Acquisition matrix.  
Figure 6: Illustration of the final result of a correlation matrix for a satellite search with (**a**) a fine frequency bin (500 Hz) and (**b**) a coarse frequency bin (2 kHz).  
The starting point of the fine search is the pair of phase \(\hat{\phi}\) and frequency \(\hat{f}\) estimated in the CS step that triggered the FS step. The search proceeds looking for intra-phase shifts and for a more precise estimation of the frequency shift around \(\hat{f}\). The correlation value \(R_{C_{f,\phi}}\) of the cells with probing frequency \(f\) and probing phase \(\phi\) in the fine search using 1 millisecond of signal is defined by  
\[R_{C_{f,\phi}} = \sum_{n=0}^{N-1}\left(C_{a}\left(\text{mod}\left(\frac{n}{P}+\phi,1023\right)\right)S(n)\cos\left(2\pi\frac{f}{f_{s}}n\right)\right)^{2}+\] \[\left(C_{a}\left(\text{mod}\left(\frac{n}{P}+\phi,1023\right) \right)S(n)\sin\left(2\pi\frac{f}{f_{s}}n\right)\right)^{2},\] \[\forall f \in \left\{\hat{f}+\delta_{\text{FS}}\left(x-\frac{N_{b}^{\text{FS}} -1}{2}\right)\mid x\in\mathbb{N},\ x<N_{b}^{\text{FS}}\right\},\] \[\forall\phi \in \left\{y\mid y\in\mathbb{N},\ \hat{\phi}-P\leq y\leq\hat{\phi}+P,\ y<1023 \right\},\]  
where \(N_{b}^{FS}\) is the number of frequency bins of the FS step, which should be an odd number to include \(\hat{f}\) in the middle of the range, and \(\delta_{\text{FS}}\) is the bandwidth of each of those bins.  
Algorithm 2 implements the FS step described in Equation (3).  
```
Data:\(S,N,\delta_{\text{FS}},N_{b}^{\text{FS}},\hat{f}\hat{\phi}\lambda_{FS}\) Result:[true, false] \(P=\frac{N}{1023}\)\(\text{higher}\text{Lower}\text{Peaks}[0]=1\) for\(f_{\text{index}}=0\)to\(N_{b}^{\text{FS}}-1\)do \(f=\hat{f}+\delta_{\text{FS}}\left(f_{\text{index}}-\frac{N_{b}^{\text{FS}}}{2}\right)\) for\(\phi=\hat{\phi}-P+1\)to\(\hat{\phi}+P-1\)do for\(n=0\)to\(N\)do \(R_{C}[f_{\text{index}}][\phi]\)= \(\left(C_{a}\left(\text{mod}\left(\frac{n}{P}+\phi,1023\right)\right)S(n)\cos \left(2\pi\frac{f}{f_{s}}n\right)\right)^{2}+\) \(\left(C_{a}\left(\text{mod}\left(\frac{n}{P}+\phi,1023\right)\right)S(n)\sin \left(2\pi\frac{f}{f_{s}}n\right)\right)^{2}\)  end for if\(R_{C}[f_{\text{index}}][\phi]>\text{ListOfPeaks}(\text{LowestPeak})\)then Insert(\(f_{\text{index}}\),\(\phi\), ListOfPeaks) ifSizeOf(ListOfPeaks)>MaxNumPeaksthen Delete(SmallestPeak,ListOfPeaks) LowestPeak=GetLowest(ListOfPeaks) end if
16 end if
17 end if
18
19 end for
20
21 end for
22
23 end for
24
25 end for
26
27 end for
28
29 HighestPeak = GetHighest(ListOfPeaks) \(\text{higher}\text{Lower}\text{Peaks}[1]=\text{ListOfPeaks}(\text{Shostest Peak})/\text{ListOfPeaks}(\text{HighestPeak})\) ifVariance(higherLowerPeaks)>\(\lambda_{FS}\)then return true
30 end if
29
31 end for return false
```  
**Algorithm 2**Fine Search