An Improved Acquisition Algorithm for GPS Signals Guoliang Zhu, Xiaohui Chen
College of Automation, Nanjing University of Posts& Telecommunications, Nanjing 210003, China
Received: September 25, 2009 / Accepted: October 27, 2009 / Published: January 25, 2010.
Abstract: In GNSS software receiver, the performance of the software receiver such as acquisition time is of importance. Conventional
GNSS signal acquisition techniques are considered inadequate in real-time software receiver. In this paper a traditional circular
correlation algorithm is analyzed and then we improve this traditional algorithm on the basis of analysis on power spectrum of the local
generated code. In terms of analysis, the power spectrum of the local generated code is asymmetrical. So only the first-half spectrum
lines were used in improved circular correlation algorithm. The experimental results show that the speed of the improved circular
correlation algorithm nearly doubles that of traditional circular correlation algorithm and the improved algorithm has good acquisition
performance. The improved circular correlation algorithm is more suitable than the traditional one in software receiver.
Key words: GPS, signal acquisition, signal power spectrum.
;frequency domain, and then improve the circular 1. Introduction
correlation algorithm. The experimental results prove GPS software receiver research has drawn more and that the improved circular correlation algorithm is more attention in recent years due to its numerous more suitable in the software receiver. The paper is advantages . Many research works focus on organized as follows: Section 2 discusses the base-band signal processing in the software receivers. traditional acquisition. Section 3 introduces the In signal processing algorithm, the speed of acquisition improved acquisition. Section 4 is fine frequency is very important. estimation. Section 5 introduces signal tracking. There are several acquisition algorithms for GPS Section 6 presents results and discussions. Section 7 signals introduced in recent years. These algorithms are gives conclusions. Section 8 presents future work. often implemented in time domain and frequency
domain. Among these algorithms, serial search 2. Traditional Acquisition
acquisition is a traditional method for acquisition in The purpose of acquisition is to determine coarse CDMA system, but it is time-consuming and values of carrier frequency and code phase of the performed through hardware in the time domain. In satellite signals . Fig. 1 gives structure of contrast, the conventional circular correlation conventional circular correlation algorithm. algorithm increases the speed of acquisition by As seen from the above diagram, the intermediate transforming correlation calculation into the frequency xnfrequency signal can be written as .The local ；？
domain through DFT calculation [2-3]. signal ln can be written as eq. (1): ；？siIn this paper, we analyze the characteristics of signal lnCnjfnt！exp2， (1) ；？；？；？sisispower spectrum of the local generated code in the
Cn；？fWhere represents the C/A code, is the s iCorresponding author: Guoliang Zhu(1985-), graduate tintermediate frequency, is the sample time interval. sstudent, research fields: GPS/Galileo software receiver, signal
processing. Email: firstname.lastname@example.org. NThe DFT of with length is calculated as ln；？siXiaohui Chen(1961- ), Ph.D., professor, research fields: eq. (2): signal processing, information fusion, target tracking.
IAnd the execution time of the method of acquiring *xnrnXkXk；？；？；？；？siComplexone satellite is 0.47s. The results prove that circular IDFTDFTconjugatecorrelation acquisition is suitable for software receiver. Q
But the algorithm acquiring 32 satellites needs 15s and
it is not real-time. So the traditional algorithm should DFT
be improved to speed up. There are two factors ln；？siaffecting the speed of acquisition, which are DFT exp2jfnt，Cn；？；？issC/A code Localgenerationoscillatorcalculation and size of two-dimension search space. Fig. 1 Structure of conventional circular correlation
algorithm. 3. Improved Acquisition
In terms of our analysis on the local generated code LkDFTln！?，；？；？ (2) sisi??
*, the spectrum is asymmetrical, which is shown in ln；？siMultiplication of and can be written XkLk；？；？si
Fig. 3. It is seen that the information is mainly as eq. (3):
contained in the first-half spectrum lines. The *RkXkLk！(3) ；？；？；？sisi second-half spectrum lines contain very little
At last, the result in time domain can be written as eq. information .
(4): As equations discussed above, only the first-half N，1spectrum is used when rnxmlnm！？；？；？；？；sisi*m！0RkXkLk！(5) ；？；？；？sisi (4) ；？！IDFTRk?， and ??siThe absolute value of can be written as rn；？sirnIDFTRk！?，；？；？(6) sisi?? rnf. The can be obtained by finding out andn；？siare calculated. Obviously, only half points are i
1msperformed instead of the full points in data. rnthe maximum of . ；？si
When acquisition is performed on 1ms data to In our implementation, conventional circular acquire one satellite, a total of 29 circulations are correlation algorithm output of a visible satellite is needed. Each circulation includes two DFT and one shown as follow (see Fig. 2): IDFT, the total operations of each circulation can be
Spectrum of the local C/A code 1400The first-half spectrum linesThe second-half spectrum lines
0020004000600080001000012000140001600018000Frequency Fig. 2 Output from conventional circular correlation Fig. 3 Spectrum of the local code. algorithm.
calculated. In terms of DSP theory, calculation of n 4. Fine Frequency Estimation
length DFT needs multiplies and nn；nn；，1；？The frequency resolution obtained from 1ms data is adds. about 1KHz, which is too coarse for the tracking loop In comparison with conventional circular correlation . Using the DFT or FFT to find fine frequency is not algorithm, the computational burden can be cut to two a suitable approach, because increasing the length of
the data for acquisition will spend more time. The third in the improved circular correlation algorithm.
approach to find the fine frequency resolution is The equation is as follows:
through phase relation. If the highest frequency theoperationsofimprovedaorithmlgP%1！，theoperationsoftraditionalaorithmlgXm；？component in 1ms data at time is , mm
216368；！DFTn；？krepresents the frequency component of the input ！，1216368116368；！？；！DFTnIDFTn；？；？(k；？signal. The initial phase of the input can be m18184；！IDFTn；？found from the FFT outputs as: ，216368116368；！？；！DFTnIDFTn；？；？~(ImXk；？；？m，12(k！tan?)；？?，21636816368163681；？；，；？m?)??ReXk；？；？(8) ！，1m??2 ?，316368163681636；？；81，；？??Where ‘Im’ and ‘Re’ represent the imaginary and 28184818481841？；，n；？real parts, respectively. Let us assume that at time , a ，2?，31636816368163681；？；，m；？Xkshort time after , the FFT component of ；？n??
11ms data is also the strongest component, because the ： (7) 3input frequency will not change that rapidly during a In our implementation, improved circular correlation short time. The initial phase angle of the input signal at algorithm output of a visible satellite is shown as nktime and frequency component is
follow (see Fig. 4): ~(ImXk；？；？n，1(k！tan?)；？nAnd the execution time of the method of acquiring ?)ReXk；？；？(9) n?? one satellite is 0.25 s. The improved algorithm Eq. (8) and eq. (9) can be used to find the fine acquiring 32 satellites needs 7 seconds. In comparison frequency as with the traditional algorithm, the time of acquisition ((kk，；？；？nmf！decreases from 0.47 s to 0.25 s. (10) 2nm，；？，
Eq. (10) provides a much finer frequency resolution
than the result obtained from FFT.
5. Signal Tracking
After performing the acquisition, control is handed
over to the tracking loops, which are used to refine the
frequency and code phase parameters. The main
purpose of tracking is to refine the carrier frequency
and code phase parameters, keep track, and demodulate
the navigation data .
A combination of code tracking loop and carrier
tracking loop is used in tracking procedure. Fig. 5
shows a complete tracking loop. Fig. 4 Output from improved acquisition algorithm.
PRN code Incoming LIntegrategeneratorsignal&dump
Fig. 5 Structure of a complete tracking loop. Carrier loopNCOThe carrier tracking loop is to keep track of the values, the tracking loop can keep track and filter
carrier frequency of a specific satellite. Due to demodulate the navigation data correctly, which are
navigation bit transitions, a Costas loop was used in shown in Fig. 6~Fig. 7. software receiver. 7. Conclusions The code tracking loop is to keep track of the code phase of a specific code. The code tracking loop uses a By comparison with traditional algorithm, improved
delay lock loop called an early-late tracking loop . algorithm has three advantages, which are as follows:
， The computational burden of DFT and IDFT can 6. Results and Discussion be cut to two third in the improved acquisition. The performance of signal acquisition algorithm was Table 1 Results from traditional acquisition. analyzed using the real GPS IF data, which were PRN Frequency(Hz) Doppler(Hz) Code offset collected by the NewStar210 GPS Signal Digitizer. 4 4.123475e+006 -520.433 13793 The Signal Digitizer was stationary, and the 2 4.1254e+006 1405.15 3919 intermediate frequency is 4.123968 MHz and the 10 4.12681e+006 2841.79 8317 sampling frequency is 16.367667 MHz . 17 4.12149e+006 -2475.86 440 The execution time of acquisition decreases from 13 4.123296e+006 -671.527 10181
0.47 s to 0.25 s when acquiring one satellite. From Table 2 Results from improved acquisition. Table 1~Table 2, we can see that the results from PRN Frequency(Hz) Doppler(Hz) Code offset traditional and improved acquisition have slight 4 4.12347e+006 -499.881 6896 differences. 2 4.1254e+006 1429.91 1960 After performing improved acquisition, these values 10 4.12678e+006 2811.79 4159
17 4.12146e+006 -2505.71 220 in Table 2 are passed into tracking loop. With these
13 4.12332e+006 -651.225 5090
-320 ， The improved algorithm has good acquisition -340performance and these values obtained from it can
initialize the tracking loop. -360In conclusion, the speed of improved acquisition
doubles that of traditional acquisition. The traditional -380
algorithm can be instead of improved algorithm. -400First, we could improve acquisition method to Dopper-frequency offset/Hzincrease the GPS receiver sensibility. Second, new -420
acquisition algorithm needs to be developed for future -440signal, such as L2 and L5. 01002003004005006007008009001000time/ms References Fig. 6 Tracking result for Doppler-frequency offset with
Costas loop.  D. Lei, C. L. Ma and G. Lachapelle, Implementation and Navigation Dataverification of a software-based IF GPS signal simulator, 4000
National Technical Meeting, Institute of Navigation, San 3000Diego (2004).
2000 T. Jin and Y. Liu, A novel GNSS weak signal acquisition
using wavelet denoising method, ION NTM, San Diego, 1000CA (2008). 0 B. Y. T. James, Fundamentals of global positioning
system receivers a software approach, A John Wiley&sons, -1000
New York (2004). -2000 P. Lian, G. Lachapelle and C. L. Ma, Improving tracking
performance of PLL in high dynamics applications, ION -3000
NTM (2005) 1042-1052. -4000 R. Peter and B. Nicolaj, Design of a single frequency GPS 1002003004005006007008009001000software receiver, Aalborg University (2004) 31-35. Time (s)  Available at http://www.oLinkStar.com. Fig. 7 Navigation data demodulated by tracking loop.
， The size of two-dimension search space decreases
from to , which can decrease 2916368；298184；
the search time.