Fast Acquisition Method of GPS Signal Based on FFT Cyclic Correlation ()
1. Introduction
Using GPS system for positioning and navigation, we need to capture the GPS signal at first. In the GPS receiver, the local generated carrier and spread spectrum code need to synchronize with the carrier and spread spectrum code in the received signal. This synchronization is generally divided into two stages: coarse synchronization and fine synchronization [1]. The acquisition process is to estimate the Doppler shift and the pseudo code phase of the received signal and initialize the tracking loop with these estimates. There are two kinds of commonly used GPS signal acquisition methods, sliding correlation method and matched filter capture method [2]. The sliding correlation method takes serial search in time domain and frequency domain, and makes correlation between 1023 code phases of each frequency. This method is simple, but the search time is too long. Although the matching filter can achieve a certain degree of parallel computing, not affected by the pseudo code cycle, but it will take up a lot of hardware resources [3]. In order to get a balance between search speed and resources, this paper uses FFT-based acquisition method, serial search in the time domain and frequency domain are in parallel, so as to improve the acquisition speed and not occupy too much resources.
2. GPS Signal Acquisition Based on Time Domain Correlation
2.1. Implementation Ideas and Processes
The signal of the GPS contains three parts: carrier signals (L1 and L2), spread spectrum sequences (C/A codes, P codes or Y codes) and navigation data (D codes) [4]. The local code is represented as a form of C/A code multiplied by an RF signal. The radio frequency signal RF is a complex number, and the local code is multiplied by the RF code and the C/A code [5]. Assuming that the L1 frequency (1575.42 MHz) is down converted to 21.25 MHz, digitized at a rate of 5 MHz to obtain an output frequency of 1.25 MHz. The frequency range of the capture program is (1250 ± 10) kHz, step 1 kHz, and a total of 21 frequency components. The local code can be expressed as:
(1)
In the above equation, the subscript s represents the satellite number, 
is the C/A code of the satellite S, 
= 1250 − 10, 1250 − 9, ・・・, 1250 + 10 kHz. The local signal must also be digitized at a 5 MHz sampling rate to produce 5000 data points.
The above 21 sets of data (only corresponding to a satellite C/A code) re- presents 21 frequencies at intervals of 1 kHz. If the C/A code and the frequency of the local signal are correct, and the C/A code phase is aligned, the output is maximized. The flow chart of the acquisition process is as shown in Figure 1:
![]()
Figure 1. Acquisition method based on time domain correlation method.
The operation of the group is as follows: the digitized input signal and the locally generated signal are multiplied by a point (5000 points in total). The square of the product is added to the square of the imaginary part and the square root is the magnitude of the output frequency. Every 200 ns carries on the above operation to the data, after the input data shift 5000 points, has completed the search to the 1ms data, altogether outputs 5000 magnitude values. 21 groups of local signals output 105,000 (5000 × 21) amplitude values. In these amplitude values, the maximum frequency component beyond the threshold corresponds to the Doppler frequency. The maximum value corresponding to the data shift K is the starting position of the C/A code [6].
2.2. Simulation Results and Analysis
When the starting position of the C/A code of the GPS signal is 1234 and the carrier frequency is 1,255,123 Hz, setting the signal-to-noise ratio to −10 dB, the simulation results of the acquisition of the No. 1 satellite signal are shown in Figures 2-4 :
![]()
Figure 2. The starting point of the C/A code of the No. 1 satellite.
![]()
Figure 3. The frequency component of the spread signal of No. 1 satellite.
![]()
Figure 4. The relationship between doppler shift step unit and correlation peak of No. 1 satellite.
This chapter briefly introduces the basic principle and implementation of GPS signal acquisition based on time domain correlation method. Through the simulation results, we can see that this method can realize GPS signal acquisition under certain SNR conditions. However, from the principle and the actual simulation we can see that the method has a lot of shortcomings in the calculation time, because it is in the time domain point-by-point correlation, the calculation is larger. Therefore, it is necessary to propose a faster GPS signal acquisition method, that is, the following GPS signal acquisition method based on FFT cyclic correlation.
3. GPS Signal Acquisition Based on FFT Cyclic Correlation
3.1. Implementation Ideas and Processes
The cyclic correlation DFT of the two sequences is equal to the conjugate of one of the sequences DFT multiplied by another sequence DFT [7]. The cyclic correlation method can be used for acquisition, and the computation time can be effectively reduced by fast Fourier transform. The specific steps are as follows:
1) FFT operation is performed on the input data x(n) of 1 ms to obtain X(k). n = k = 0, 1, 2, ・・・, 4999.
2) Take X(k) complex conjugate, get X(k)*.
3) Generate 21 local codes lsi(n), where i = 1, 2, ・・・, 21.
4) Take FFT for lsi(n) and get Lsi(k).
5) X(k)* and Lsi(k) are multiplied by point to obtain Rsi(k).
6) Take Rsi(k) inverse FFT transform, get the time domain signal rsi(n), take the absolute value, get |rsi(n)|. A total of 105,000 |rsi(n)|.
7) Give the starting position of the C/A code at a resolution of 200 ns and the carrier frequency at a frequency resolution of 1 kHz at the nth position and the maximum value of the ith frequency |rsi(n)|.
3.2. Simulation Results and Analysis
When the starting position of the C/A code of the GPS signal is 1234 and the carrier frequency is 1,255,123 Hz, setting the signal-to-noise ratio to −10 dB, the simulation results of the acquisition of the No. 6 satellite signal are shown in Figures 5-7.
This chapter gives the GPS acquisition method based on FFT cyclic correlation, introduces its basic principle and implementation process, and then gives the simulation results. In the code phase, the fast acquisition algorithm based on FFT requires only one FFT and one IFFT operation to determine the correlation value for all samples in a cycle of C/A codes. Rather than the serial search acquisition method, the code phase is gradually sliding to find the correlation value. And it greatly reduces the amount of calculation.
![]()
Figure 5. The starting point of the C/A code of the No. 6 satellite.
![]()
Figure 6. The frequency component of the spread signal of No. 6 satellite.
![]()
Figure 7. The relationship between doppler shift step unit and correlation peak of No. 6 satellite.
4. Analysis and Comparison of GPS Signal Acquisition Methods
4.1. Calculating Time
The fast acquisition algorithm based on FFT in the carrier frequency using a direct search method, but it requires only once FFT and once IFFT operation in the code phase to determine the correlation value for all samples in a cycle of C/A codes. Rather than the serial search acquisition method, the code phase is gradually sliding to find the correlation value.
Assuming that using a C/A code period of data for acquisition, the sampling points is N. When using the traditional serial search acquisition algorithm, each time of the correlation results need N times multiplication and N-1 times addition. To calculate all the N code phase, a total of N2 need to multiply. Using the fast acquisition algorithm based on FFT, the total amount of computation required is about 2 times the amount of FFT calculation, that is, 
times multiplication, reducing the amount of computation [8].
According to the actual simulation results of MATLAB, the average time of GPS signal acquisition method based on time domain correlation method is 21.124146 seconds, while the average time of GPS signal acquisition method based on FFT cyclic correlation method is only 0.261626 seconds.
4.2. Time Delay Error
According to the fact that GPS receiver receives the GPS satellite signal in actual situation, the received power typical value of C/A code is between −162.5 - 154.5 dBW, and the SNR is between −35.5 - −27.5 dB. Therefore, set the SNR range of simulation between −36 - 17 dB, and the starting position of the C/A code of the GPS signal is 1234 and the carrier frequency is 1,255,123 Hz. The simulation results of two acquisition methods of the No. 6 satellite signal are shown in Figure 8.
![]()
Figure 8. The variation of time delay error with SNR using time domain correlation method.
![]()
Figure 9. The variation of time delay error with SNR using FFT method.
As can be seen from Figure 9, the time delay error tends to decrease with the increase of SNR in the given SNR range. In the case of small SNR, because the SNR has a great impact on the GPS signal acquisition results, the results are not stable, and the curve has a floating.
It can be seen from the figure that the results obtained by using the FFT method are similar to those of the time domain correlation method. The time delay error tends to decrease with the increase of SNR in the given SNR range. In the case of small SNR, because the SNR has a great impact on the GPS signal acquisition results, the results are not stable, and the curve has a floating. However, it can be seen that the results obtained using the FFT method are more ideal than the time domain correlation method, and the floating is relatively small.
5. Conclusion
The demand of positioning and navigation has been developing with human civilization, and playing an important role in the development of human history. Not only in defense and military, but also in the civil field it has shown a huge application prospects and broad commercial market, changing everyone’s habits and ways of thinking. In order to track and decode GPS signals, GPS signals need to be captured first. In this paper, the traditional GPS signal acquisition method based on time domain correlation method is introduced, and the GPS signal acquisition method based on FFT cyclic correlation method is discussed. Through the actual simulation and analysis, it is not difficult to conclude that the GPS signal acquisition method based on FFT has more advantages than the traditional time domain correlation method in terms of calculating time and acquisition performance. Therefore, the proposed GPS signal acquisition method based on FFT is a feasible and superior GPS signal acquisition method.
Acknowledgements
This paper is funded by the International Exchange Program of Harbin Engineering University for Innovation-oriented Talents Cultivation, National Natural Science Foundation of China (No. 61401115), National Natural Science Foundation of China (No. 61301095), National Natural Science Foundation of China (No. 61671167), International Science & Technology Cooperation Program of China (2014 DFR10240), China Postdoctoral Science Foundation (2013- T60346), Harbin Science and Technology Research Projects (P083313026), Natural Science Foundation of Heilongjiang Province (P083014025).