More recent GPS receivers lock on a satellite signal using frequency domain computation. In this process, the receiver takes the Fourier transform of a received signal. Then multiplies the output of this transform a code corresponding to the specific satellite and performs the inverse FFT on the resulting signal. This 3-step process mathematically ensures that the output of the inverse FFT will spike at the correct shift that synchronizes the code with the received signal. The computational complexity of this approach is O(n log n). For the past two decades, this has been the algorithm with the lowest computational complexity for synchronizing a GPS receiver.
The Inventors’ 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. This single spike can be filtered with a simple sublinear algorithm to reduce complexity of the inverse FFT step. The algorithm proceeds by aligning several numbers into one, by summing them up, reducing the sizes of the pattern and the scene to improve algorithm efficiency. FFT is calculated for only this minimized subset of frequencies, further reducing complexity.