Faster GPS via the sparse fourier transform

Haitham Hassanieh, Fadel Adid, Dina Katabi, Piotr Indyk

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 datasets collected in the US and Europe. The results show that the new algorithm reduces the median number of multiplications by 2.2× in comparison to the state of the art design, for real GPS signals.

Original languageEnglish (US)
Title of host publicationMobiCom'12 - Proceedings of the 18th Annual International Conference on Mobile Computing and Networking
Number of pages12
StatePublished - 2012
Externally publishedYes
Event18th Annual International Conference on Mobile Computing and Networking, MobiCom 2012 - Istanbul, Turkey
Duration: Aug 22 2012Aug 26 2012

Publication series

NameProceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM


Other18th Annual International Conference on Mobile Computing and Networking, MobiCom 2012


  • GPS
  • Sparse fourier transform
  • Synchronization

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Faster GPS via the sparse fourier transform'. Together they form a unique fingerprint.

Cite this