Title
Faster GPS via the sparse fourier transform
Abstract
GPS is one of the most widely used wireless systems. A GPS receiver has to lock on the satellite signals to calculate its position. The process of locking on the satellites is quite costly and requires hundreds of millions of hardware multiplications, leading to high power consumption. The fastest known algorithm for this problem is based on the Fourier transform and has a complexity of O(n log n), where n is the number of signal samples. This paper presents the fastest GPS locking algorithm to date. The algorithm reduces the locking complexity to O(n√(log n)). Further, if the SNR is above a threshold, the algorithm becomes linear, i.e., O(n). Our algorithm builds on recent developments in the growing area of sparse recovery. It exploits the sparse nature of the synchronization problem, where only the correct alignment between the received GPS signal and the satellite code causes their cross-correlation to spike. We further show that the theoretical gain translates into empirical gains for GPS receivers. Specifically, we built a prototype of the design using software radios and tested it on two GPS data sets collected in the US and Europe. The results show that the new algorithm reduces the median number of multiplications by 2.2x in comparison to the state of the art design, for real GPS signals.
Year
DOI
Venue
2012
10.1145/2348543.2348587
MobiCom
Keywords
Field
DocType
fastest known algorithm,real gps signal,art design,n log n,new algorithm,gps data,faster gps,fastest gps,gps receiver,log n,gps signal,software radio,gps,synchronization,fourier transform,cross correlation
Binary logarithm,Synchronization,Computer science,GPS/INS,Fourier transform,Real-time computing,Global Positioning System,GPS signals,Time complexity,Assisted GPS
Conference
Citations 
PageRank 
References 
9
0.52
12
Authors
4
Name
Order
Citations
PageRank
H. Hassanieh159137.63
Fadel Adib285337.98
Dina Katabi37819453.05
Piotr Indyk410925918.34