Acquisition is a most important process and a challenge task for identifying visible satellites, coarse values of carrier frequency, and code phase of the satellite signals in designing software defined Global positioning system (GPS) receiver. This paper presents a new, simple, efficient and faster GPS acquisition via sub-sampled fast Fourier transform (ssFFT). The proposed algorithm exploits the recently developed sparse FFT (or sparse IFFT) that computes in sub-linear time. Further it uses the property of fourier transforms (FT): Aliasing a signal in the time domain corresponds to sub-sampling it in the frequency domain, and vice versa. The ssFFT is an FFT algorithm that computes sub-sampled version of the data by an integer factor ‘d’, and hence, the computational complexity is proportionately reduced by a factor of ‘d log d’ compared to conventional FFT-based algorithms for any length of the input GPS signal. The simulation results show that the proposed ssFFT based GPS acquisition computation is 8.5571 times faster than the conventional FFT-based acquisition computation time. The implementation of this method in an FPGA provides very fast processing of incoming GPS samples that satisfies real-time positioning requirements.


Keywords:   GPS,  sub-sampling,  aliasing,  acquisition,  sub-sampled fast Fourier transform

Global positioning system (GPS) provides accurate positioning and timing information that has become a commonly used navigation device for aircraft precision approaches, missile systems, automated vehicle guidance, and other civil applications. The GPS satellites simultaneously transmit on two L-band frequencies denoted by LI and L2, which are 1575.42 and 1227.60 MHz, respectively1.

Software GPS receivers capture the RF modulated signals at the L1 frequency, down convert there to an intermediate frequency (IF), digitize there, and perform signal processing to extract position information from the navigation message. The GPS receiver consists of four modules namely RF front end, acquisition, tracking and position computation. The position fix of GPS receiver takes more time initially when the receiver is switched on. This is mainly due to identification of satellite tracking signals and decoding navigation data2. The faster GPS position fix is essential, especially in kinematic conditions, and therefore, it is necessary to improve acquisition process.

The GPS receiver demodulates the transmitted signal by synchronizing a locally generated PRN with the same PRN used to generate transmitted signal. The process in which incoming signal is correlated with a local PRN code is called signal acquisition or synchronization. Acquisition is most important process and a challenging task for identifying visible satellites, coarse values of carrier frequency, and code phase of the satellite signals. To identify each satellite, a GPS receiver conducts a search process. It computes the correlation of the PRN code with the received signal for all possible shifts of the code with respect to the signal. The correct shift is the one that maximizes the correlation3.

There are three signal acquisition or synchronization approaches mainly: the serial search algorithm, FFT-based methods, and the delay-and-multiply approach. The time domain serial search acquisition method scans all the frequency cells in the carrier frequency and PRN code space. This method is easy to implement but very time-consuming4. If any of the two parameters could be eliminated from the search procedure, or if possible implemented in parallel, the performance of the procedure could be improved significantly.

The parallel frequency space search acquisition parallelises the search for the carrier frequency parameter, and only search all the cells in PRN code space. If the PRN code is perfectly aligned with the incoming signal, the output signal will show a distinct peak in magnitude. Since this acquisition method searches through the 1023 different code phases by parallelising frequency, hence, it is faster than serial search acquisition algorithm. Frequency search resolution depends on signal length: the longer the signal, the finer is the resolution. This search is not feasible for noisy input signal.

The parallel code phase search acquisition parallelises the search for the PRN code parameter, and only searches all the cells in carrier frequency space. In this method the Doppler-frequency and code-phase searches are combined into one search, and after a fast Fourier transform (FFT) of the PRN code, all code-phase information is transformed into the frequency domain. Hence it is needed only to search the Doppler-frequency offset space, which is much smaller than the code phase space. Thereby it implements a fast and effective search. In this method for each acquisition only one PRN code is generated. That is, it is not necessary to search the 1023 different code phases space2,6,7. For the past two decades, this has been the algorithm with faster and the lowest computational complexity for synchronizing or acquisition of a GPS receiver. The delay-and-multiply approach eliminates all of the Doppler bins. From theoretically speaking, this is an efficient method, but it needs advance research for real time environment. Other acquisition methods are found5,12. But in many applications, such as high dynamics vehicles or an appliance which uses sleep mode to save power consumption, a fast acquisition of signal is strongly required.

This paper presents a novel, simple, efficient and faster GPS signal acquisition method via sub-sampled fast Fourier transform (ssFFT) that reduces the number of computations, simplifies the hardware implementation, and correspondingly decreases the acquisition time. The computational complexity of proposed algorithm is ‘d log d times faster than the conventional FFT-based acquisition algorithm, where ‘d’ is an integer down sampling factor13. The implementation of this method in an FPGA provides very fast processing of incoming GPS samples that satisfies real-time requirements.

The FFT-based or frequency domain GPS acquisition approach exploits the property of Fourier transform; convolution in the time domain corresponds to multiplication in the frequency domain. It proceeds in the following three steps, as shown in Fig.1:

(i) Computes the FFT of the received GPS signal and local PRN signals, respectively

(ii) Multiplies these two FFT signals, and

(iii) performs the inverse FFT on the resulting signal.

This three-step process is mathematically equivalent to convolving the input signal with the local PRN code; thus, the output of the inverse FFT will be a spike or an impulse at the correct shift that synchronizes the code with the received signal, as shown in Fig.1. The algorithm multiplies the FFTs of the received signal with the FFT of the locally generated PRN code, and takes the IFFT of the resulting signal. The output of the IFFT produces a single spike at the correct time shift. For the past two decades, this has been the algorithm with the lowest computational complexity for synchronizing a GPS receiver. The computational complexity of this approach is O(n log n).

Figure 1. The steps performed by the FFT-based acquisition algorithm.

This paper presents an efficient and fast acquisition process based on the following observations and properties of Fourier transform;

(i) First, we observe that the output of acquisition process produces a single major spike in the time domain. This means that the IFFT is a highly sparse signal in the time domain. Recently the research on sparse FFT has emerged in compressive sensing theory for development of new algorithms that can compute the FFT or inverse FFT in sub-linear time8,9,11. This property has been exploited to design a simple sub-linear algorithm that uses only aliasing to filter the signal and allows one to reduce the complexity of the IFFT step to sub-linear time.

(ii) Second, it was noted that the output of the inverse FFT is sparse and can be computed in less time, but the GPS signal in the frequency domain is not sparse. Hence, the computation of the forward FFT cannot be reduced by applying a sparse Fourier transform and the overall complexity of the problem is still O(n log n) due to the forward FFT. Since sparse IFFT algorithm operates only on a subset of its input signal, one does not need to compute the values of all frequencies at the output of the forward FFT. This property has been to compute only a subset of the frequencies and reduce the complexity of the FFT step.

2.1 sub-sampled FFT

ssFFT is a sub-sampled fast Fourier transform that is computed as FFT of a sub-sampled or down-sampled version of a signal by a factor ‘d’ known as decimator, where ‘d’ is an integer.

For better understanding, the decimator has been illustrated by the following example: let x[n] is discrete time sequence having the length N = 15, is given by x[n] = {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15}. The sequence is applied to a decimator by a factor d = 3 and the resultant output sequence is represented by y[m] = x[dn] = x[3n] ={1 4 7 10 13}. It has been observed that the elements in the output sequence are every third (since d=3) element of the input sequence. In practice a low-pass filter [LPF] is used prior to down-sampling to avoid aliasing in the outputs10 as shown in Fig 2(a). The main purpose of GPS acquisition is to identify the visibility of satellites but not for reconstruction on the signal. Hence, the LPF process is completely eliminated, thereby simplifying the decimator process as shown in Fig. 2(b). We referred this as an ‘Aliased decimator’ meaning that down-sampling or sub-sampling in the time domain results aliasing in the frequency domain. By duality, sub-sampling in the frequency domain results aliasing in the time domain10. Based on this background theory, we call the FFT of a sub-sampled sequence as sub-sampled fast Fourier transform ssFFT.

The main key insight to our proposed algorithm is that the IFFT performed in step 3 (Fig. 1) of the FFT-based acquisition algorithm is sparse in the time domain, i.e., it has only one spike in time domain and, hence, can be performed in sub-linear time9,11. Further, a sub-linear time algorithm for computing the sparse IFFT would require a sub-linear number of samples as input; thus, there is no need to perform a full n log n FFT on the received GPS signal and obtain all of its n frequency samples. Rather, we only need to compute the frequency samples that will be used to perform the sparse inverse FFT. The proposed GPS acquisition via sub sampled FFT algorithm is illustrated in the following steps (Fig. 3).

Figure 2. Decimation process (a) Aliasing free decimator, (b) Aliased decimator.

Step 1: Down sampling: Perform down-sampling on both the input GPS signal and locally generated PRN code by a factor ‘d’. These down-sampled signals are referred to as sub-sampled signals and are aliased. The length of these sub-sampled signals is N/d, where N is the length of input signal and local d is PRN code.

Step 2: Sub-sampled FFT: Perform FFT of these sub-sampled input signals that have the length of N/d. The FFT of locally generated PRN code may be pre-computed and stored in the frequency domain.

Step 3: Multiply: Perform element wise multiplication of these FFT of sub-sampled signals that have length of N/d computed in step 2.

Step 4: Sparse IFFT: Perform the inverse FFT on the resultant multiplied signal in step 3. It is to be noted that the input to IFFT is sub-sampled and its output is aliased in the time domain.

Figure 3. The steps performed by the proposed faster acquisition algorithm via ssFFT. The algorithm first down samples by a factor ‘d’ and then multiplies the FFT of the received signal with the FFT of the locally generated PRN code, and takes the IFFT of the resulting signal. The output of the IFFT produces a single spike at the correct time shift.

Computation Complexity: Since both the forward FFT and inverse FFT are computed in sub-sampled signal of length N/d, the computation complexity of proposed algorithm is (N/d) log(N/d). Therefore, the proposed algorithm is [N logN] / [(N / d)log(N / d)] = d log d times faster than the existing FFT-based techniques. It is to be noted that this factor does depends only on the down-sampling rate and not on the length of the signal.

We have implemented the proposed algorithm on GPS signal with sampling frequency of 11.999 MHz, and carrier frequency of 3.562 MHz with various down-sampling factors from 2 to 14 with step size 2. The proposed algorithm is implemented in Matlab ver.7.11 (R2010b) under Windows Xp 32 bit operating system. The results are illustrated visually in Fig. 4 and are tabulated in Table 1. The following observations are made from the experiments results.

The proposed algorithm identifies the correct visible satellites for down-sampling factors from 2 to 12 in step size of 2. For above 14, the algorithm fails due to the noise becoming dominating.

The carrier frequencies are observed as scaled versions by a factor of ‘d’. For example for d = 4, the carrier frequency is observed in the Fig. 4 as 0.8905 MHz. But the actual carrier frequency is ‘d’ times 0.8905 MHz which coincides with the original carrier frequency 3.562 MHz. Similar arguments hold for all down-sampling factors up to 12.

As down-sampling factor ‘d’ increases, the computation complexity decreases by a factor of ‘d log d’, where d is an integer. For example in the case of down-sampling rate d = 12, the computation complexity of proposed algorithm is decreased by a factor of 43.02 as compared to the conventional FFT algorithm (Table 1 and Fig. 5(a)). The computational complexity improvement factor (‘d log d’) depends on the down sampling factor ‘d’, but does not depends on the input GPS signal length ‘n’. Hence for any length of the input signal, the proposed algorithm computational complexity improves by a factor of ‘d log d’.

As down-sampling factor ‘d’ increases, the noise contamination is linearly increasing (Fig. 4). This noise can be elimination by thresholding or using appropriate low-pass filters, but the complexity of algorithm and computation time increases correspondingly.

Table 1. Experiment results

Figure 4. 2D search for correlation. The plots of Fig. 4(a)-4(h) show the results of correlating with local PRN codes for a satellite whose signals are present at correct time shifts with down-sampling rates from 2 to 14 in step size of 2. On the x-axis, the search for code shifts and y-axis different Doppler shifts. For down-sampling factor 14, the search fails because of higher sub-sampling factor.

Figure 5. Plots of proposed algorithm computational improvements (a) Computational complexity improvement (b) Computation time improvement (c) Code Phase variations against down sampling rate.

The magnitude of the spikes at correct time shift decreases and the noise increases as the down-sampling factor decreases (Fig. 4). The main purpose of GPS acquisition is to identify the visibility of satellites but not for reconstruction of the signal. Therefore the down-sampling factor may be appropriately selected as long as the spike is identified.

As the down sampling factor ‘d’ increases, the computation time decreases exponentially as shown in Fig. 5(b). For example in the case of down-sampling factor d = 12, the proposed GPS acquisition computation time (0.032310 s) is 8.5571 times faster than that conventional FFT based acquisition computation time (0.276479 s). Further it was observed that for above down-sampling factor 6, the computation time decreases in a smaller quantity. Hence for satisfactory results, the down-sampling factor may be fixed any integer between 8 and 12.

For the down-sampling rates 2 to 12, the code phases are observed in slight variations in magnitude and the maximum deviation of code phase is approximately 1 (Tabel 1 and Fig. 5(c)). This small deviation will not deteriorate the GPS receiver performance.

The LPF part in decimator is completely eliminated, resulting in aliased output. As the inverse IFFT step required performing in sub-linear time, correspondingly the forward FFT step required sub-sampled signal. Therefore the aliased version of input signal is needed for the FFT processing step. Hence the elimination of the LPF in the decimator simplifies the proposed algorithm.

The proposed GPS acquisition can also be used for weak signal environments.

The implementation of this method in an FPGA provides very fast processing of incoming GPS samples that satisfies real-time requirements.

Truncation of PRN sequences leads to reduce the correlation of the GPS signals and may not be an appropriate solution16. The GPS received signal and replica of PRN signal will not be synchronized and reduction in processing gain due to truncation of PRN codes17.

We have presented a novel, new, simple, efficient and faster GPS acquisition (L1 signal) via sub-sampled FFT for software-defined GPS receiver design. Our algorithm exploits the properties of Fourier transform, decimator and sparse FFT, that reduces the number of computations, simplifies the hardware implementation, and decreases the acquisition time correspondingly. The computational complexity of proposed algorithm is ‘d log d’ times faster than the conventional FFT based acquisition algorithm, where ‘d’ is an integer down sampling factor. We demonstrated that computation is 8.5571 times faster than that of conventional FFT-based algorithm for down-sampling rate d = 12.

Future Scope: In spite of our fast algorithm, there is much scope for improvement. The proposed algorithm used Radix-2 FFT and IFFT computations. There is a scope for improving using faster FFT computations such as Radix-4, Cooley-Tukey FFT, etc. Further, the sparse FFT may be incorporated in place of direct FFT or inverse FFT. For determination of the optimum down-sampling factor, a mathematical analysis may be needed. The initial estimate of the preamble will be computed using an iterative process to enhance the GNSS signal acquisition process by the two-step maximum likelihood (ML) technique using the differential correlation approach in as given by Vasudevan14 or the two-step ML technique using the non-coherent approach in as given by Vasudevan15. New satellite navigation systems such as Indian Regional Navigation Satellite System (IRNSS) and COMPASS are going to be operational in future, the proposed algorithm is immensely useful for developing future satellite navigation software receiver design. The proposed algorithm would be useful for future satellite navigation signals such as L5 and L2C, etc.

The authors thank all the reviewers for giving critical comments and suggestions for improving the quality of the paper. The authors like to express their deep gratitude towards the Department of ECE and the management of K L University for their support and encouragement during this work. Authors also like to express their thanks to the Department of Science and Technology for sanchoning this project through SR/FST/ETI-316/2012 FIST program.

1. Mao, M.L.; Chen, A.B.; Tseng, Y.F.; Chang, F.R.; Tsao, H.W& Huang, W.H. Design of peak-finding algorithm on acquisition of weak GPS signals. In proceedings of IEEE International Conference on Systems, Man, and Cybernetics. Taipei, Taiwan, October 8-11, 2006. doi: 10.1109/ICSMC.2006.384994.

2. Tsui, J.B. Fundamentals of global positioning system receivers: a software approach, Ed. 2. ISBN 0-471-70647-7, John Wiley & Sons, Inc., Hoboken, New Jersey, 2005. doi: 10.1002/0471712582

3. Borre, K.; Akos, D.M.; Bertelsen, N.; Rinder, P & Jensen, S.H. A software-defined GPS and galileo receiver-A single-frequency approach. ISBN 0-8176-4390-7, 2007. doi: 10.1007/978-0-8176-4540-3

4. JianFeng W. & Yonghui, H. The study on GPS signal acquisition algorithm in time domain. In proceedings of WiCOM ‘08. 4th International Conference on Wireless Communications, Networking and Mobile Computing, 12-14 Oct, 2008, 1–3. doi: 10.1109/WiCom.2008.490.

5. Ratnam, D.V.; Pasha, A.; Swathi, P.&Rao, M.V.G. Acquisition of GPS L1 signals using Cooley-Tukey FFT algorithm. In proceedings of IEEE International Conference on Signal Processing Computing and Control, Solan, India, 26-28 Sept. 2013, 1–4. doi: 10.1109/ISPCC.2013.6663397.

6. Yuying, Z. A Software-based frequency domain parallel acquisition algorithm for GPS signal. In proceedings of International conference on Anti-counterfeiting Security and Identification in Communication (ASID), 2010, 298–301. doi: 10.1109/ICASID.2010.5551340.

7. Xiao, X. & Yijin, C. Research on acquisition method of GPS software receiver. In proceedings of Consumer Electronics, Communications and Networks (CECNet), Yichang, 2012, 2791-794. doi: 10.1109/WiCom.2008.490.

8. Gilbert, A.C.; Muthukrishnan, S.; & Strauss, M. Improved time bounds for near-optimal sparse Fourier representations. In Proceedings of SPIE Wavelets XI, 2003, doi:10.1117/12.615931.

9. Hassanieh, H.; Indyk, P.; Katabi, D. & Price, E. Nearlyoptimal sparse Fourier transform. In proceedings of STOC, 2012. arXiv:1201.2501. doi:10.1145/2213977.2214029

10. Proakis, J.G. & Manolakis, D.G. Digital signal processing: Principles, algorithms and applications pearson education, 2007.

11. Hassanieh, H.; Adib, F.; Katabi, D. & Indyk, P. Faster GPS via the sparse fourier transform. In Proceedings of Mobicom ‘12, 18th Annual International Conference on Mobile Computing and Networking, 2012. doi: 10.1145/2348543.2348587.

12. O’Mahony, N. & Cruz, F.P. A novel sequential bayesian approach to GPS acquisition, In Proceedings of 3rd International Workshop on Cognitive Incromation Processing (CIP), 2012. doi: 10.1109/cip.2012.6232921

13. Rao, M.V.G. & Ratnam, D.V. Faster GPS/IRNSS acquisition via subsampled fast Fourier transform (ssFFT) and thresholding, In Proceedings of IEEE International Conference INDICON, IIT Bombay, 2013, 1-4. doi: 10.1109/INDCON.2013.6726043.

14. Vasudevan, K. Iterative detection of turbo-coded offset QPSK in the presence of frequency and clock offsets and AWGN. Sign. Image Video Proc., Springer, 2012, 6(4), 557-567. doi: 10.1007/s11760-010-0184-6

15. Vasudevan, K. Coherent detection of turbo coded OFDM signals transmitted through frequency selective Rayleigh fading channels. In Proceedings of IEEE International Conference on Signal Processing, Computing and Control (ISPCC), 2013. doi:10.1109/ISPCC.2013.6663392.

16. Wallener, S. & Angelavila Rodriguez, J. Codes the PRN familty grows again. Sep/Oct 2011, Inside GNSS magazine. http://www.insidegnss.com/auto/sepoct11-wp.pdf.

17. Banerjee, P.; Keshwala U. & Kaushik, M. Study on potentiality of truncated PRN sequences for communication. In Proceedings of IEEE International Conference on Communications, Devices and Intelligent Systems, Kolkata. 2012, 409-412. doi: 10.1109/CODIS.2012.6422225.

Dr M. Venu Gopala Rao obtained his MTech from Regional Engineering College, Warangal, in 1999, and PhD from Osmania university, Hyderabad, in 2011. Presently, he is Professor in the Department of ECE, KL University, Guntur, A.P., India. He received a ‘Credit Award’ in Radio Servicing Theory from City and Guild’s London Institute, London, in 1978. He is a Fellow of IETE and Life Member in IAE, ISTE, SSI, and ISOI. His research interests include signal, image processing, GPS and compressive sensing. He has published more than 38 papers in various international and national journals, conferences and workshops.

Dr D. Venkata Ratnam obtained his MSc (Electronics) and MTech (Radar and Microwave Eng) from Andhra University. PhD from JNTUH, Hyderabad. Presently, Associate Professor, Dept. of Electronics and Communication Engineering, KL University, Guntur, A.P., India. Research interests: navigation electronics, global positioning system, space science, radio wave propagation, satellite communications. Publications: author of 12 international and 4 national journal papers and 23 national and international conference papers.