GNSS Signal Acquisition Algorithm Based on Two-Stage Compression of Code-Frequency Domain

Abstract

The recently-emerging compressed sensing (CS) theory makes GNSS signal processing at a sub-Nyquist rate possible if it has a sparse representation in certain domain. The previously proposed code-domain compression acquisition algorithms have high computational complexity and low acquisition accuracy under high dynamic conditions. In this paper, a GNSS signal acquisition algorithm based on two-stage compression of the code-frequency domain is proposed. The algorithm maps the incoming signal of the same interval to multiple carrier frequency bins and overlaps the mapped signal that belongs to the same code phase. Meanwhile, the code domain compression is introduced to the preprocessed signal, replacing circular correlation with compressed reconstruction to obtain Doppler frequency and code phase. Theoretical analyses and simulation results show that the proposed algorithm can improve the frequency search accuracy and reduce the computational complexity by about 50% in high dynamics.

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 rates of 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. He et al. [17] used the sparse matrix to compress the spread spectrum signal and reconstructed the compressed signal based on the greedy algorithm. Kong 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. Chang et al. [19] combined CS with subspace to enhance the acquisition performance of GNSS signal when there are a lot of interferences. He 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. Section 4 compares the performance of the proposed algorithm with other acquisition algorithms and discusses the performance with different key parameters. Section 5 concludes this paper.

2. Code-Domain Compression Acquisition Algorithm

2.1. Sparsification of GNSS Signal

The incoming digital down-converted GNSS intermediate frequency (IF) signal can be expressed as [21]

$$r\left(n\right)=Ad\left(n\right)c(n-\tau )\exp [j\left(2\pi \right(f_{\mathrm{IF}}+f_{\mathrm{d}})n{T}_{\mathrm{s}}+\phi )]+v\left(n\right)$$

(1)

where A is the signal amplitude, d is the signal data, c is the spreading code, $f_{\mathrm{IF}}$ is the intermediate frequency, $f_{\mathrm{d}}$ is the Doppler frequency offset, $T_{\mathrm{s}}$ is the sampling interval, $\tau$ is the code phase, v is the noise, and $\phi$ is the unknown carrier phase.

From the previous work, we know GNSS signal acquisition is possible at a low sampling rate by employing CS theory to compress the raw GNSS signal data using a measurement matrix [22], which can be expressed as

$$\mathbf{y}=\mathsf{\Phi }·\mathbf{x}$$

(2)

where $\mathbf{x}$ is the original signal, $\mathbf{y}$ is the measurement vector, $\mathsf{\Phi }$ $\in R^{M\times N}$ is the measurement matrix, N is the signal length, M is the measurement length, and $M<<N$.

The premise of CS is that the signal is sparse. However, most of the real signals are not sparse but can be expressed as

$$\mathbf{x}=\mathsf{\Psi }·\mathbf{a}$$

(3)

where $\mathsf{\Psi }$ is called the sparse basis of the signal, $\mathbf{a}$ is a sparse vector.

Shifting the spreading code vector $\mathbf{c}=[c\left(0\right),c\left(1\right),\cdots ,c(NK-1)]\in R^{NK\times 1}$ to get the code matrix $\mathbf{C}$

$$\mathbf{C}=[{\mathbf{c}}_0,{\mathbf{c}}_1,\cdots ,{\mathbf{c}}_{N-1}]=\left[\begin{array}{cccc}c\left(0\right)& c\left(1\right)& \cdots & c(2K-1)\\ c\left(K\right)& c(K+1)& \cdots & c(3K-1)\\ ⋮& ⋮& \ddots & ⋮\\ c\left[\right(N-1\left)K\right]& c\left[\right(N-1)K+1]& \cdots & c\left[\right(N+1)K-1]\end{array}\right]$$

(4)

where N is the amount of points in the FFT, and N = $2K$.

Padding zeros to the end of the incoming signal $r\left(n\right)$ to increase its length to $2K$, which can solve the problem of non-periodicity after block processing of spreading code and reduce computation effectively [23]. It can be described as

$$\mathbf{r}={[r\left(0\right),r\left(1\right),\cdots ,r(K-1),0_{1\times K}]}^{\mathrm{T}}$$

(5)

Then, correlating the padded signal vector $\mathbf{r}$ with the local spreading code matrix $\mathbf{C}$, we can obtain the correlation vector $\mathbf{X}$

$$\mathbf{X}=\mathbf{C}·\mathbf{r}$$

(6)

The acorrelation function (CF) of the incoming signal and the spreading code can be described as

$$X_i=<{\mathbf{c}}_n,\mathbf{r}>=\sum _{i=0}^{2K-1}c(i+n)r\left(i\right)=\left\{\begin{array}{cc}v+2AK\left(1-\frac{\left|\tau \right|}{T_{\mathrm{c}}}\right),& \left|\tau \right|\le T_{\mathrm{c}}\hfill \\ v,& \left|\tau \right|>T_{\mathrm{c}}\hfill \end{array}\right.$$

(7)

where $X_i$ is the ith element of the correlation vector $\mathbf{X}$, ${\mathbf{c}}_n$ is the nth row of the code matrix $\mathbf{C}$, $<·>$ is the discrete-time convolution operation, $T_{\mathrm{c}}$ is the chip time, $2AK$ is the maximum peak value.

As shown in Figure 1, the correlation result $\mathbf{X}$ can be considered sparse if $\left|2AK\right|>>\left|v\right|$ in Equation (7).

2.2. Code-Domain Compression Acquisition

According to Equations (2) and (6), we can use the measurement matrix $\mathsf{\Phi }$ to compresses the $N\times 1$ dimensional correlation result $\mathbf{X}$ to obtain the $M\times 1$ dimensional measurement data $\mathbf{Y}$

$$\underset{M\times 1}{\mathbf{Y}}=\underset{M\times N}{\mathsf{\Phi }}·\underset{N\times 1}{\mathbf{X}}=\underset{M\times N}{\mathsf{\Phi }}·\underset{N\times 2K}{\mathbf{C}}·\underset{2K\times 1}{\mathbf{r}}$$

(8)

The measurement matrix $\mathsf{\Phi }$ will be helpful for signal reconstruction when restricted isometry property (RIP) criteria is satisfied. In other words, each column is a unit vector, and the sum of squares of all columns meets the Welch bound [24,25]

$$\sum _{i=1}^N\sum _{j=1}^N{\left|〈{\varphi }_i,{\varphi }_j〉\right|}^2\ge \frac{N^2}{M}$$

(9)

The FFT-based parallel search engine is adopted to acquire the correlation peak, which converts time-domain convolution operation into frequency-domain multiplication. The FFT of $\mathsf{\Phi }·\mathbf{C}$ are taken and multiplied by the FFT of the $\mathbf{r}$, and then taken the inverse FFT (IFFT) to obtain $\mathbf{Y}$.

The correlation result $\mathbf{X}$ can be reconstructed from $\mathbf{Y}$ through some reconstruction algorithms, which can be described as follows

$$\min \Vert \mathbf{X}{\Vert }_0\begin{array}{ccc}& \mathrm{s}.\mathrm{t}.& \end{array}\mathbf{Y}=\mathsf{\Phi }·\mathbf{X}$$

(10)

where $\Vert ·{\Vert }_0$ means the $l_0$ norm which counts the number of nonzero elements.

The $l_0$ norm is a NP-hard problem, which can be converted into $l_2$ norm if the measurement matrix $\mathsf{\Phi }$ meets the RIP condition.

$${\min \Vert \mathbf{X}\Vert }_2^2\begin{array}{ccc}& \mathrm{s}.\mathrm{t}.& \end{array}\mathbf{Y}=\mathsf{\Phi }·\mathbf{X}$$

(11)

where $\Vert ·{\Vert }_2$ is the $l_2$ norm, also known as the Euclidean norm, which is used as a standard quantity for measuring a vector difference [26].

The least square method (LSM) is used to reconstruct the elements from the measurement data $\mathbf{Y}$ [27].

$$\mathbf{X}={\mathsf{\Phi }}^{\mathrm{T}}{\left(\mathsf{\Phi }{\mathsf{\Phi }}^{\mathrm{T}}\right)}^{-1}\mathbf{Y}$$

(12)

The correct code phase and Doppler frequency offset are determined by comparing the first K elements from the correlation result $\mathbf{X}$. Replacing the circular correlation with a compressed reconstruction in this method decreases the number of correlators from $N+1$ to $M+1$ [28].

As we know, the correlation function $R(\tau ,f_{\mathrm{d}})$ of the spreading code can be described as follows [29]

$$R(\tau ,f_{\mathrm{d}})=2AK\left(1-\frac{\left|\tau \right|}{T_{\mathrm{c}}}\right)\frac{\sin \left[\pi \left(f_{\mathrm{d}}-f_i\right)2K{T}_{\mathrm{s}}\right]}{\sin \left[\pi \left(f_{\mathrm{d}}-f_i\right)T_{\mathrm{s}}\right]}\exp \left[j\gamma \left(\phi \right)\right]$$

(13)

where $\gamma \left(\phi \right)=\pi \left(f_{\mathrm{d}}-f_i\right)\left(2K-1\right)T_{\mathrm{s}}+\phi$, $f_i$ is the Doppler frequency hypothesis.

We can find that $R(\tau ,f_{\mathrm{d}})$ is affected by the Doppler frequency as a $\mathrm{sinc}(·)$ function [29], and the zero of its main lobe is located at

$$f_{\mathrm{d}}=\frac{\pm 1}{K{T}_{\mathrm{s}}}+f_i$$

(14)

The correlation bandwidth $B_{\mathrm{c}}$ denotes

$$B_{\mathrm{c}}=\frac{2}{K{T}_{\mathrm{s}}}$$

(15)

Hence the Doppler frequency offset range in each search is obtained as

$$f_{\mathrm{d}}\in \left[\frac{-1}{K{T}_{\mathrm{s}}}+f_i,\frac{1}{K{T}_{\mathrm{s}}}+f_i\right]$$

(16)

where the search accuracy is $1/\left(K{T}_{\mathrm{s}}\right)$.

In above algorithm, the acquisition is serial in the frequency domain, and it will take a long time to acquire the Doppler frequency in high dynamics.

3. Code-Frequency Two-Stage Compression Acquisition

In this section, we introduce a new frequency domain compression to preprocess the incoming signal to reduce the influence of large Doppler frequency offset.

3.1. Frequency Domain Compression Preprocessing

The incoming signal is multiplied with $\exp \left[j2\pi (f_{\mathrm{o}}^i+f_{\mathrm{c}}^l)\right]$ to produce the mapped signal $r_l^{\prime }\left(n\right)$

$$r_l^{\prime }\left(n\right)=r\left(n\right)\exp \left[j2\pi (f_{\mathrm{o}}^i+f_{\mathrm{c}}^l)n{T}_{\mathrm{s}}\right]$$

(17)

where $f_{\mathrm{c}}^l$ is the multiple carrier frequency bins, $l\in \{0,1,2,\dots ,L-1\}$, L is the frequency compression ratio (FCR), the frequency search step $f_{\mathrm{step}}=f_{\mathrm{c}}^{l+1}-f_{\mathrm{c}}^l$, $f_{\mathrm{o}}^i$ is the starting frequency in once frequency compression search, $i\in \{0,1,2,\dots ,I-1\}$, I is the number of sub-carrier bins, the frequency compression steps $f_{\mathrm{o}}^{i+1}-f_{\mathrm{o}}^i=L·f_{\mathrm{step}}$.

Hence the Doppler frequency offset can be expressed as

$$f_{\mathrm{d}}=I·L·f_{\mathrm{step}}$$

(18)

Figure 2 shows the process of the mapping and overlapping-based carrier frequency searching technique. We divide the Doppler frequency offset $f_{\mathrm{d}}$ into I sub-carrier frequency bins and search for L sub-frequency points separated by $f_{\mathrm{step}}$ simultaneously.

From Equation (13), we can see that if the Doppler frequency is greater than the correlation bandwidth $B_{\mathrm{c}}=2/\left(K{T}_{\mathrm{s}}\right)$, the correlation value is attenuated seriously. Accordingly, the frequency search step should satisfy $f_{\mathrm{step}}\le B_{\mathrm{c}}/2$, making sure at least two neighboring acquisition frequency points are located within the correlation bandwidth $B_{\mathrm{c}}$, which is beneficial to enhancing the acquisition performance, as shown in Figure 3a. However, if $f_{\mathrm{step}}>B_{\mathrm{c}}$, the neighbor acquisition frequency exceeds the correlation bandwidth $B_{\mathrm{c}}$, causing the correlation value decrease and the acquisition failure, as illustrated in Figure 3b.

Then, the mapped signals which correspond to the same code phase are overlapped together. Consequently, we obtain the preprocessed incoming signal

$$r_l^{″}\left(n\right)=\sum _{l=0}^{L-1}{r}_l^{\prime }\left(n\right)$$

(19)

The correlation bandwidth of the comprssion acquisition is improved by frequency domain preprocessing, which can be expressed as

$$B_{\mathrm{c}}^{\prime }=(L-1)f_{\mathrm{step}}+B_{\mathrm{c}}$$

(20)

Compared with the traditional Doppler frequency search method, the L frequency bins are searched simultaneously in this method, which can reduce search number and acquisition time.

3.2. Algorithm Process

The detailed and straightforward processes of proposed GNSS acquisition algorithm are shown in Algorithm 1 and Figure 4.

Algorithm 1 The proposed GNSS acquisition algorithm.
Input: Incoming signal, $r\left(n\right)$; Spreading code vector, ${\mathbf{c}}_0$; Measurement matrix, $\mathsf{\Phi }$; Decision
	threshold, $V_{\mathrm{t}}$;
Output: Code phase, $\tau$; Doppler frequency offset, $f_{\mathrm{d}}$;
1:	Mapping incoming signal $r\left(n\right)$ to different carrier frequencies $f_o^i$;
2:	Overlapping the mapped signals to the same code phase to obtain $r_l^{″}\left(n\right)$;
3:	Padding zeros to the end of the mapped signals $r_l^{″}\left(n\right)$ to form a signal vector ${\mathbf{r}}^{″}$;
4:	Shifting spreading code vector ${\mathbf{c}}_0$ to obtain the code matrix $\mathbf{C}$;
5:	Performing FFT operation to find out the measurement data $\mathbf{Y}$;
6:	Using the greedy algorithm to obtain the correlation result $\mathbf{X}$;
7:	Comparing the first K elements from the correlation result $\mathbf{X}$ with the threshold $V_{\mathrm{t}}$ to
	obtain the code phase $\tau$ and Doppler shift $f_{\mathrm{d}}$;
8:	return$\tau$, $f_{\mathrm{d}}$;

3.3. Detection Probability Analysis

Assuming a partial Hadamard matrix is adopted as measurement matrix to assess the performance of the proposed algorithm, the following two hypotheses determine the test statistic for signal detection

$$\tilde{\mathbf{y}}=\left\{\begin{array}{cc}{\mathsf{\Phi }}_1\mathbf{w}& H_0\\ {\mathsf{\Phi }}_1(\mathbf{x}+\mathbf{w})& H_1\end{array}\right.$$

(21)

where ${\mathsf{\Phi }}_1\in {\mathbf{R}}^{\left(M{T}_{\mathrm{p}}/{\alpha }_c\right)\times N}$ denotes a random partial Hadamard matrix, ${\alpha }_c$ is the maximum subsampling factor, $T_{\mathrm{p}}$ is the spreading spectrum period, $H_1$ denotes the signal is present and correctly aligned with the local replica, $H_0$ denotes the signal is absent or not correctly aligned with local replica.

Consequently, the probability density function of $\tilde{\mathbf{y}}$ under hypothesis $H_1$ is shown as follows:

$$p\left(\tilde{\mathbf{y}}\mid \widehat{\overline{\mathbf{x}}},H_1\right)=\frac{1}{{\left(2\pi \right)}^{\left(M/{\alpha }_{\mathrm{c}}\right)/2}{\left|{\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right|}^{1/2}}\exp \left[-\frac{1}{2}{\left(\mathbf{W}\right)}^{\mathrm{T}}{\left({\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}\left(\mathbf{W}\right)\right]$$

(22)

where $\mathbf{W}=\tilde{\mathbf{y}}-\mathbf{D}\widehat{\mathbf{x}}$, $\mathbf{D}={\mathsf{\Phi }}_1·\mathsf{\Psi }$, and $\widehat{\mathbf{x}}$ denotes

$$\widehat{\mathbf{x}}={\left({\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}{\mathsf{\Phi }}_1^{\mathrm{T}}\tilde{\mathbf{y}}$$

(23)

The $\widehat{\overline{\mathbf{x}}}$ denotes the maximum likelihood estimation (MLE) of $\mathbf{x}$ under $H_1$, which is shown as

$$\widehat{\overline{\mathbf{x}}}={\left({\mathbf{D}}^{\mathrm{T}}{\left({\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}\mathbf{D}\right)}^{-1}{\mathbf{D}}^{\mathrm{T}}{\left({\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}\tilde{\mathbf{y}}$$

(24)

If the threshold $\eta$ is selected to attain the required false alarm probability, the detection performance can be obtained as

$$P_d=\mathrm{Pr}\left({\mathsf{\Gamma }}_{\tilde{\mathbf{y}}}>\eta \mid H_1\right)=Q_{{\overline{\chi }}_{M{T}_{\mathrm{p}}/{\alpha }_c}^{2\lambda }\left(\lambda \right)}\left(\eta \right)$$

(25)

where ${\mathsf{\Gamma }}_{\tilde{\mathbf{y}}}$ is a noncentral chi-squared distribution with $M{T}_{\mathrm{p}}/{\alpha }_c$ degrees of freedom, which is expressed as

$${\mathsf{\Gamma }}_{\tilde{\mathbf{y}}}={\tilde{\mathbf{y}}}^{\mathrm{T}}{\left({\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}\mathbf{D}{\left({\mathbf{D}}^{\mathrm{T}}{\left({\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}\mathbf{D}\right)}^{-1}{\mathbf{D}}^{\mathrm{T}}{\left({\sigma }^2{\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}\tilde{\mathbf{y}}$$

(26)

where $\lambda$ is a non-centrality parameter specified by

$$\lambda ={\sigma }^{-2}{\left({\mathbf{x}}^{\mathrm{T}}\right)}^{-1}{\mathsf{\Phi }}_1^{\mathrm{T}}{\left({\mathsf{\Phi }}_1{\mathsf{\Phi }}_1^{\mathrm{T}}\right)}^{-1}{\mathsf{\Phi }}_1\mathbf{x}$$

(27)

3.4. Complexity Analysis

The complexity of the proposed algorithm consists of three parts: frequency domain compression preprocessing, code domain compression, and signal reconstruction, of which the first and third are the main parts, and the second part can be ignored as the elements of the measurement matrix are −1 or 1. In this paper, we chose the orthogonal matching pursuit (OMP) algorithm for signal reconstruction, whose complexity is $O(N·{\left({\log }_2\left(N\right)\right)}^2)$ [30,31].

Table 1. Table of algorithm complexities.

Acquisition Algorithm	Complexity
Serial acquisition algorithm	$O(N^2·I·L)$
PMF-FFT acquisition algorithm	$O(N·(L·{\log }_2\left(L\right)+N))$
CC acquisition algorithm	$O(N·{\left({\log }_2\left(N\right)\right)}^2·I·L)$
CFC acquisition algorithm	$O(N·{\left({\log }_2\left(N\right)\right)}^2·I)$

gives the complexities of the serial acquisition algorithm, the PMF-FFT acquisition algorithm, the code-compression (CC) acquisition algorithm [26] and the proposed code-frequency compression (CFC) acquisition algorithm.

4. Simulation Results

The GPS L1 signal is adopted to evaluate the performance of the proposed method. Set the data rate $R_{\mathrm{b}}$ = 50 bps, the code rate $R_{\mathrm{c}}$ = 1.023 Mcps, the sampling rate $f_{\mathrm{s}}$ = 2$R_{\mathrm{c}}$, the code phase $\tau$ = 400, the code length N = 1024, the measured length M = 768, and the Doppler frequency offset range is ±80 KHz.

4.1. Results on Detection Probability

Figure 5 shows the normalized acquisition results of the proposed algorithm with different $FCR$ when $SNR$ is −12 dB. We can find that with the decrease of $FCR$, the ratio of the highest correlation peak to the second correlation peak increases, which means the detection probability increases.

Figure 6 shows the detection probabilities of the proposed algorithm with different $SNR$. We can compute that when the $SNR$ = −12 dB, the detection probabilities of $FCR$ = 2:1, 4:1, and 8:1 are 96.3%, 67.8%, and 22.4%, respectively. With the increase of $FCR$, the number of overlaps of the mapped signals with the same code phase increases, which makes it difficult to distinguish the correlation peaks and reduces the detection probability.

4.2. Results on Dynamic Acquisition

Figure 7 shows the detection probabilities of the proposed algorithm with different Doppler frequencies. When the $SNR$ = −12 dB, $FCR$ = 2:1, the Doppler frequency offsets are 0kHz, 26 kHz, 52 kHz and 78 kHz, the detection probabilities are 96.3%, 93.2%, 98.5%, and 92.3%, respectively, and their values are very close to each other. When the $FCR$ is changed to 4:1 or 8:1, we can get a similar conclusion. As analyzed in Section 3.1, the frequency-domain preprocessing improves the correlation bandwidth, keeping more neighboring acquisition frequency points within the correlation bandwidth, which greatly reduces its sensitivity to Doppler frequency.

Figure 8 compares the detection probabilities of the proposed algorithm with other traditional acquisition algorithms. With the increase of Doppler frequency, the acquisition probabilities of the PMF-FFT and the CC acquisition algorithms decrease. A large Doppler frequency restricts the matching filter length of the PMF-FFT acquisition algorithm [32] and the correlation bandwidth of the CC acquisition algorithm, which limits their application in highly dynamic situations. As we can see, when the Doppler frequency is greater than about 52 kHz, the acquisition performance of the CFC acquisition algorithm begins to surpass that of the other two algorithms.

4.3. Results on Algorithm Complexity

Figure 9 gives the complexities of the four acquisition algorithms with different $FCR$ and N. As we can see, the complexity of the proposed CFC acquisition algorithm is less than that of the other three algorithms. This advantage becomes more obvious with the increase of parameters $FCR$ and N. Specifically, as shown in Figure 9a, when the $FCR$ = 2, the code length N = 1024, the complexities of the serial, the PMF-FFT, the CC, and the CFC acquisition algorithms are $1.049\times {10}^7$, $1.114\times {10}^6$, $1.638\times {10}^6$, $8.192\times {10}^5$, respectively, and the proposed CFC acquisition algorithm is 92.19%, 26.46%, and 50% lower than the other three algorithms. As shown in Figure 9b, when the code length N = 2048, the $FCR$ = 1:2, the complexities of the four acquisition algorithms are $6.711\times {10}^7$, $4.325\times {10}^6$, $3.965\times {10}^6$, $1.982\times {10}^6$, respectively. Compared with the other algorithms, the CFC acquisition algorithm reduces 99.7%, 54.17%, and 50%. Thus, the frequency domain compression preprocessing can reduce the resource overhead, which makes the proposed CFC acquisition algorithm better adapt to high dynamic conditions.

5. Conclusions

In this paper, we proposed a GNSS signal acquisition algorithm based on two-stage compression of the code-frequency domain. The preprocessing of frequency compression is employed to reduce the computational complexities of the CC acquisition algorithm, which maps the incoming signal into different sub-carrier frequency bins, and the mapped signals are then overlapped with the same code phase, which can reduce the number of bins that should be searched. The simulation results show that when the Doppler frequency offset is greater than 52 kHz, the detection probability of the proposed algorithm is better than that of the only code-domain compression acquisition algorithms, and the computational complexity is reduced by 50% at the same time. In addition, compared with the traditional PMF-FFT and CC acquisition algorithms, the detection probability of the proposed CFC algorithm is insensitive to the Doppler frequency offsets in highly dynamic environments. In the future, the measurement matrix $\mathsf{\Phi }$ could be optimized and the reconstruction method could be explored to further improve the acquisition performance. Moreover, the impacts of multipath and non-Gaussian noise on compression acquisition are also very interesting research topics.