# GNSS Signal Acquisition Algorithm Based on Two-Stage Compression of Code-Frequency Domain
## 1 Introduction  
The global navigation satellite system (GNSS) includes constellations of satellites orbiting over the earth's surface that provide continuous positioning, navigation, and timing (PNT) services anywhere in the world or near-earth space, under any weather conditions [1; 2; 3]. The first stage of a GNSS receiver is the acquisition, which plays a very important role in signal synchronization, whose aim is to detect the signal and roughly estimate the code phase and the Doppler frequency of the satellite in the field of view. GNSS signal acquisition is a two-dimensional searching process, which needs to search all the likely spreading code phases and Doppler frequencies, including serial acquisition and parallel acquisition. The serial acquisition is a common method, which needs to reconstruct all possible code phases and Doppler frequencies and correlate with the received satellite signal one by one, and is a very time-consuming search procedure. Thus, the parallel acquisition methods are proposed, which use fast Fourier transforms (FFT) to convert the signal from time domain into frequency domain. These methods can be summarized into three categories: the parallel frequency search, which uses a FFT to search simultaneously all or a part of the Doppler frequency bins [4; 5]; the parallel code search, which uses FFTs to compute the code correlation to search all the code delay bins simultaneously [6; 7]; and the two-dimensional search where FFTs are used for both frequency and code domains [8; 9; 10; 11; 12]. The parallel acquisition methods can improve the acquisition efficiency, but they increase the complexity considerably. Furthermore, the above acquisition methods are based on the Nyquist sampling theory, which is a redundant sampling method. In recent years, as a promising theory of signal sampling, compressed sensing (CS) provides a new method to solve this dilemma [13], which can greatly reduce the sampling ratesof sparse signals and faithfully reconstruct the original signals back from fewer compressive measurements. It has been applied in many fields, including speech enhancement [14], magnetic resonance imaging [15], wireless sensor network [16], etc. Moreover, several CS-based methods have been proposed for GNSS signal acquisition. [PERSON] et al. [17] used the sparse matrix to compress the spread spectrum signal and reconstructed the compressed signal based on the greedy algorithm. [PERSON] et al. [18] proposed two-stage compression of GNSS signal by the Walsh-Hadamard matrix, which achieved fast acquisition with fewer correlators than traditional acquisition methods. [PERSON] et al. [19] combined CS with subspace to enhance the acquisition performance of GNSS signal when there are a lot of interferences. [PERSON] et al. [20] designed a sparse dictionary based on the features of the GLONASS navigation signal and modified the greedy reconstruction algorithm to achieve fast acquisition. However, the above algorithms are based on the conventional frequency search method with a fixed bandwidth, which results in low acquisition probabilities under high dynamic conditions. In this paper, a GNSS signal acquisition algorithm based on two-stage compression of the code-frequency domain is proposed, which divides the Doppler frequency offset into multiple intervals, and the multiple frequency points are compressed and searched in every interval at the same time to increase the correlation bandwidth. This method can overcome the limitations of the conventional Doppler frequency search and is suitable for fast acquisition in high dynamics. The rest of this paper is organized as follows. Section 2 introduces the compression acquisition theory and the problems of the compression acquisition algorithm in a highly dynamic environment. Section 3 proposes the model of two-stage compression and theoretically analyzes the advantages of the proposed method, including computational complexity and detection probability.