editor's blog
Subscribe Now

A Faster Fourier Transform

We all had to learn about Fourier transforms in college. That scared some of us away to the safe, contained world of digital logic. But many of you carried on with it, and the Fast Fourier Transform (FFT) became one of your basic tools.

In fact, at least in the FPGA world, it became the poster child for, “Look what we can do!” Whether it was IP or C-to-RTL or speed, it was always demonstrated on an FFT. Which makes sense, since many digital signal processing functions were moving into FPGAs for performance.

That worked ok for a while – impressive at first, standard later on, and then… well, apparently it just got old. With erstwhile marketing hats on, I’ve been in meetings that went more like, “OK, so you can do an FFT. Can you do anything serious?”

And so the FFT has become somewhat more like a basic logic gate. Just bigger and less intuitive.

Well, apparently, this logic gate just got faster (FerFT?). MIT announced a new algorithm that promises to be 10 times faster than the current algorithm. They do this by noting that most real-world signals have a few dominant components; their algorithm is most valuable for such “sparse” signals. They divide up the frequency range into slices, each of which has a single dominant component, and then iteratively try to zero in on those primary components.

Apparently we’ll have to wait for the best zeroing-in algorithm; it has yet to be published.

More info in their release

Leave a Reply

featured blogs
May 2, 2025
I can safely say that I've never seen a wheeled-legged robot that can handle rugged terrains, muddy wetlands, and debris-strewn ruins like this...

featured paper

How Google and Intel use Calibre DesignEnhancer to reduce IR drop and improve reliability

Sponsored by Siemens Digital Industries Software

Through real-world examples from Intel and Google, we highlight how Calibre’s DesignEnhancer maximizes layout modifications while ensuring DRC compliance.

Click here for more information

featured chalk talk

Solutions for General Precision Location Tracking
In this episode of Chalk Talk, Arnaud Le Lannic from u-blox, Greg Makar from the YAGEO Group and Amelia Dalton explore the benefits of GNSS for general precision location tracking. They investigate the biggest challenges associated with these kinds of designs, the solutions best suited for vehicular asset tracking and the mounting options available for these solutions.
Apr 21, 2025
14,744 views