A 0.75-million-point fourier-transform chip for frequency-sparse signals by Omid Abari, Ezz Hamed, Haitham Hassanieh, Abhinav Agarwal, Dina Katabi, Anantha P. Chandrakasan, Vladimir Stojanovic
Applications like spectrum sensing, radar signal processing, and pattern matching by convolving a signal with a long code, as in GPS, require large FFT sizes. ASIC implementations of such FFTs are challenging due to their large silicon area and high power consumption. However, the signals in these applications are sparse, i.e., the energy at the output of the FFT/IFFT is concentrated at a limited number of frequencies and with zero/negligible energy at most frequencies. Recent advances in signal processing have shown that, for such sparse signals, a new algorithm called the sparse FFT (sFFT) can compute the Fourier transform more efficiently than traditional FFTs [1].
Faster GPS Via the Sparse Fourier Transform by Haitham Hassanieh, Fadel Adib, Dina Katabi, and Piotr Indyk. ( Slides )
GPS is one of the most widely used wireless systems. A GPS re ceiver 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(nlogn), 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√logn). Further, if the SNR is above a threshold, the algorithm becomes linther, 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 btween 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 agorithm reduces the median number of multiplications by 2.2× in comparison to the state of the art design, for real GPS signals.
these examples of applications were found in this Recent Developments in the Sparse Fourier Transform by Anna C. Gilbert, Piotr Indyk, Mark Iwen, Ludwig Schmidt
The Discrete Fourier Transform (DFT) is one of the most important discrete transformations used in many computational settings from signal or image processing to scienti c computing. The most popular approach to computing the DFT uses the Fast Fourier Transform (FFT). However, with the emergence of big data problems, in which the size of the processed data sets can easily exceed terabytes, the \Fast" in Fast Fourier Transform is not fast enough. Furthermore, in many big data applications it is hard to acquire a su cient amount of data to compute the desired Fourier transform. The Sparse Fourier Transform (SFT) can compute a compressed Fourier transform using only a subset of the input data in time considerably shorter than the data set size. The goal of this article is to survey these recent developments, to explain the basic techniques coupled with examples and applications in big data, to demonstrate trade-o ffs in empirical performance of the algorithms, and to discuss the connection between the SFT and other techniques for massive data analysis such as streaming algorithms and compressive sensing.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment