Faster GPS via the sparse fourier transform
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 k...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86901 https://orcid.org/0000-0002-6689-8189 https://orcid.org/0000-0003-4854-4157 https://orcid.org/0000-0003-2593-2069 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1826203830805594112 |
|---|---|
| author | Hassanieh, Haitham Adib, Fadel M. Katabi, Dina Indyk, Piotr |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Hassanieh, Haitham Adib, Fadel M. Katabi, Dina Indyk, Piotr |
| author_sort | Hassanieh, Haitham |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:43:53Z |
| format | Article |
| id | mit-1721.1/86901 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:43:53Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/869012022-10-01T10:47:11Z Faster GPS via the sparse fourier transform Hassanieh, Haitham Adib, Fadel M. Katabi, Dina Indyk, Piotr Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Hassanieh, Haitham Adib, Fadel M. Katabi, Dina Indyk, Piotr 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. National Science Foundation (U.S.) 2014-05-09T14:47:37Z 2014-05-09T14:47:37Z 2012-08 Article http://purl.org/eprint/type/ConferencePaper 9781450311595 http://hdl.handle.net/1721.1/86901 Hassanieh, Haitham, Fadel Adib, Dina Katabi, and Piotr Indyk. “Faster GPS via the Sparse Fourier Transform.” Proceedings of the 18th Annual International Conference on Mobile Computing and Networking - Mobicom ’12 (2012). August 22–26, 2012, Istanbul, Turkey. ACM. p.353-364. https://orcid.org/0000-0002-6689-8189 https://orcid.org/0000-0003-4854-4157 https://orcid.org/0000-0003-2593-2069 https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1145/2348543.2348587 Proceedings of the 18th annual international conference on Mobile Computing and Networking - Mobicom '12 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery MIT web domain |
| spellingShingle | Hassanieh, Haitham Adib, Fadel M. Katabi, Dina Indyk, Piotr Faster GPS via the sparse fourier transform |
| title | Faster GPS via the sparse fourier transform |
| title_full | Faster GPS via the sparse fourier transform |
| title_fullStr | Faster GPS via the sparse fourier transform |
| title_full_unstemmed | Faster GPS via the sparse fourier transform |
| title_short | Faster GPS via the sparse fourier transform |
| title_sort | faster gps via the sparse fourier transform |
| url | http://hdl.handle.net/1721.1/86901 https://orcid.org/0000-0002-6689-8189 https://orcid.org/0000-0003-4854-4157 https://orcid.org/0000-0003-2593-2069 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT hassaniehhaitham fastergpsviathesparsefouriertransform AT adibfadelm fastergpsviathesparsefouriertransform AT katabidina fastergpsviathesparsefouriertransform AT indykpiotr fastergpsviathesparsefouriertransform |