(4) Fourier Transform in GPS Signal Acquisition

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. [1]

Apparently, the fastest known algorithm for this problem is based on the Fourier transform. A paper called “Faster GPS via the Sparse Fourier Transform” discussed about reducing complexity in relation with decreasing GPS power consumption.

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). 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. [1]

[1] http://haitham.ece.illinois.edu/Papers/QuickSync-mobicom.pdf