# Energy Efficient GNSS Signal Acquisition Using Singular Value Decomposition (SVD)
## 1 Introduction
One is the actual frequency offset by a Doppler value and the offset of the local oscillator at the receiver. Therefore, an important part is the acquisition space, which occurs in 2D, is that one axis is the frequency (KHz), and the other is the code delay (chips). The search is typically done in frequency bins. This is called a frequency and code-delay search. The traditional approach convolves then the received signal with the code division multiple access (CDMA) code of each satellite in the time domain, and the correct alignment corresponds to the one that maximizes convolution. This approach has a computational complexity of \(\mathrm{O}\big{(}n^{2}\big{)}\). In the frequency domain the receiver takes the FFT of the received signal, it multiplies the output of this Fourier transform by the FFT of the CDMA code and then performs the inverse fast Fourier transform (IFFT) on the resulting signal, the output will spike at the correct shift that synchronizes the code with the received signal. The computational complexity of this approach is \(\mathrm{O}(n\log n)\)[10]. [PERSON] et al. presented an FFT-based GPS locking algorithm of complexity \(\mathrm{O}\big{(}n\sqrt{logn}\big{)}\), called QuickSync, that builds on recent developments of sparse recovery, and introduces the lowest complexity algorithm to date. The algorithm is tested on two datasets with data collected in the US using an SDR and a second one collected in Europe. Their design reduces the number of multiplications for detecting the correct shift by a median of 2.2\(\times\), the algorithm aliases the received signal in the time domain before taking its FFT, performs a subsample FFT on the aliased signal, subsamples the FFT of the satellite CDMA code, and multiplies the resulting samples with the aliased subsample FFT. Then it performs the IFFT, and the output is aliased in the time domain. Picking the shift that maximizes the correlation [11], the algorithm developed in this research does not compete with the algorithms already in the market as its main focus is on compressing the signal that is to be used for those other algorithms. Three contributors to the frequency offset to consider at the acquisition search are the frequency uncertainty and the noise in the TXCO-generated frequency, the Doppler effect for satellite motion, frequencies for rising and setting GPS satellites, and the receiver motion. For a receiver under static conditions, the most significant contributor to frequency offset is the satellite motion, which is about 4.2 KHz [1], however, under high dynamic conditions, signals produce significant Doppler frequency shifts, which hinders the fast acquisition of signals, in the case of the maximum velocity of the satellite combined with very high user velocity-approach values as high as 10 KHz [12]. The signal search and acquisition becomes important when the receiver is looking for several satellites at the same time: i.e., parallelism. A typical standalone GPS receiver can acquire signals down to about \(-\)160-decibel milliwatts (dBm) and might require a minute or more to obtain a position from a cold start. GPS receivers usually include some degree of parallelism, when considering a receiver having N channels, in which each channel is dedicated to searching for signals with a different PRN sequence. Within a channel, the frequency and code-phase search spaces are further divided into several windows [6]. Parallelism can be implemented in hardware using massively parallel correlators, or in software using fast Fourier transform-based techniques [13] where the massive parallel correlation is done by exploiting a property of the Fourier transformation. This approach requires having all the IF samples in RAM, where it can be transformed to the frequency domain, perform a simple multiplication, and finally perform an inverse transform back to the time domain. This will have the same results than using the standard hardware approach.