Synchronization and Pattern Matching Via the Sparse Fourier Transform

Technology    

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.  

Problem Addressed

GPS is among the most widely used satellite systems, incorporated in devices ranging from smartphones, navigation systems, sensors, digital cameras, and bio chips. A GPS receiver calculates its position by locking onto and synchronizing with nearby satellite signals. This synchronization process is quite costly and requires hundreds of millions of hardware multiplications, leading to high power consumption. Many GPS-enabled devices have strict power limitations and would significantly benefit from reducing the complexity of the process. 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. The Inventors have developed an even faster GPS synchronization algorithm that 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).  

Advantages

• Invention present the fastest GPS synchronization algorithm to date, with complexity O(n√log n)
• Empirical testing shows the algorithm reduces the median number of multiplications by 2.2x in comparison to the state of the art design, for real GPS signals 

Publications

"Faster GPS via the Sparse Fourier Transform." In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, 2012, 353–364.