High-throughput implementation of a million-point sparse Fourier Transform

Abhinav Agarwal, Haitham Hassanieh, Omid Abari, Ezz Hamed, Dina Katabi, Arvind

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The emergence of data-intensive problems in areas like computational biology, astronomy, medical imaging, etc. has emphasized the need for fast and efficient very large Fourier Transforms. Recent work has shown that we can compute million-point transforms efficiently provided the data is sparse in the frequency domain. Processing input samples at rates approaching 1 GHz would allow real-time processing in several such applications. In this paper, we present a high-throughput FPGA implementation that performs a million-point sparse Fourier Transform on frequency-sparse input data, generating the largest 500 frequency component locations and values every 1.16 milliseconds. This design can process streamed input data at 0.86 Giga samples per second, and does not make any assumptions of the distribution of the frequency components beyond sparsity.

Original languageEnglish (US)
Title of host publicationConference Digest - 24th International Conference on Field Programmable Logic and Applications, FPL 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9783000446450
DOIs
StatePublished - Oct 16 2014
Externally publishedYes
Event24th International Conference on Field Programmable Logic and Applications, FPL 2014 - Munich, Germany
Duration: Sep 1 2014Sep 5 2014

Publication series

NameConference Digest - 24th International Conference on Field Programmable Logic and Applications, FPL 2014

Other

Other24th International Conference on Field Programmable Logic and Applications, FPL 2014
CountryGermany
CityMunich
Period9/1/149/5/14

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'High-throughput implementation of a million-point sparse Fourier Transform'. Together they form a unique fingerprint.

Cite this