# Variance-Triggered Two-Step GPS Acquisition
## 1 Introduction  
The first step performed by a Global Navigation Satellite System (GNSS) receiver is the acquisition. It consists of roughly finding the phase and frequency of an incoming GNSS signal and identifying the transmitting satellite. The phase of the signal is never known prior to acquisition and, as a result of the Doppler effect, the incoming frequency changes over time. The acquisition procedure should, therefore, explore a wide spectral range to detect phase and frequency of the signal and determine which satellites are transmitting by testing all plausible hypotheses in a bi-dimensional search space. Frequency domain acquisition strategies have gained much attention [1; 2]. This type of acquisition uses a Fast Fourier Transform (FFT) block to test all phases at once while iterating over the Doppler shift space sequentially. A recent two-step method, called Multi-Peak Double-Dwell, performs the acquisition using the FFT with a coarse step and a fine step [3]. Although FFT-based methods are usually faster than conventional time domain strategies, they require supplementary hardware, which increases the project requirements and cost [4]. Thus, conventional Serial Acquisition (SA) approaches that consider the reduction of the acquisition time without compromising the hardware simplicity are very desirable. Many receiver designs explore acquisition in the time domain associated with a strategy to improve performance. In [5], a folding technique exploits the sparsity of the GNSS signal to reduce computational complexity. In this technique, the signal is folded and the correlation is performed on the folded signal. Although computationally more efficient than SA, this method ismore sensitive to the carrier-to-noise ratio (C/N0) degradation caused by an increase in the number of folds [5]. The eXtended replica Folding Acquisition Search Technique (XFAST) [6] is another folding strategy that directly reduces the code phases to look for by folding the local signal. Nevertheless, after folding, the correlation properties of the signal are degraded; hence, the detection performance for weak signals is worse than that of non-folding methods [5]. The Deterministic Compressed Sensing (DCS) is another acquisition technique based on a folding strategy that can achieve a better response in lower C/N0 [7] in comparison to conventional folding techniques. This technique also exploits the sparsity of a signal to reduce the number of measurements required for successful representation of the signal. The DCS is related to the problem of finding sparse solutions to vastly under-determined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements [8; 9; 10]. The main contribution of DCS acquisition is the use of an appropriate transformation matrix to most sparsely express the target signal and to develop a measurement matrix along with an associated efficient reconstruction algorithm. Even though this technique achieves higher noise robustness than conventional folding techniques, it still suffers from poor accuracy at low C/N0. In addition to the folding approaches that target the phase search, some techniques exploit the size of the frequency bin to improve acquisition time. In [11], a proof of the influence of the frequency bin size on the overall performance of acquisition is presented. It is shown that small Doppler bins increase the probability of a global false-positive, but increase the detection probability within the correct Doppler bin. The above mentioned time-domain techniques search for the phase and frequency pair one after each other, using all signal samples available, folded or not. This means that when the correct pair is the last one to be tested, independently of the signal quality, all other pairs had already failed, resulting in the worst case complexity.