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
Apr 4, 2020
That metaphorical '€œboing'€ sound you hear, figuratively speaking, is a symbolical ball allegorically landing on Chewy'€™s side of the illusory net....
Apr 3, 2020
Mentor’s Xpedition® IC Packaging design tools bridge the gap between engineering teams for IC layout, package substrate design, and PCB layout with solutions for Chip/Package/PCB prototyping and co-design. They also deliver a complete solution for High Density Advan...
Apr 3, 2020
[From the last episode: We saw some of the mistakes that can cause programs to fail and to breach security and/or privacy.] We'€™ve seen how having more than one program or user resident as a '€œtenant'€ in a server in the cloud can create some challenges '€“ at leas...
Apr 2, 2020
There are many historical innovations that are the product of adversity, and the current situation is an extreme example.  While it is not the first time that humanity has faced a truly global challenge like the COVID-19 pandemic, this time the world is connected by tech...

Featured Video

Automotive Trends Driving New SoC Architectures -- Synopsys

Sponsored by Synopsys

Today’s automotive trends are driving new design requirements for automotive SoCs targeting ADAS, gateways, connected cars and infotainment. Find out why it is essential to use pre-designed, pre-verified, reusable automotive-optimized IP to meet such new requirements and accelerate design time.

Drive Your Next Design to Completion Today with DesignWare IP® for Automotive SoCs