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
Jul 3, 2020
[From the last episode: We looked at CNNs for vision as well as other neural networks for other applications.] We'€™re going to take a quick detour into math today. For those of you that have done advanced math, this may be a review, or it might even seem to be talking down...
Jul 2, 2020
Using the bitwise operators in general, and employing them to perform masking operations in particular, can be extremely efficacious....
Jul 2, 2020
In June, we continued to upgrade several key pieces of content across the website, including more interactive product explorers on several pages and a homepage refresh. We also made a significant update to our product pages which allows logged-in users to see customer-specifi...

Featured Video

Product Update: DesignWare® TCAM IP -- Synopsys

Sponsored by Synopsys

Join Rahul Thukral in this discussion on TCAMs, including performance and power considerations. Synopsys TCAMs are used in networking and automotive applications as they are low-risk, production-proven, and meet automotive requirements.

Click here for more information about DesignWare Foundation IP: Embedded Memories, Logic Libraries & GPIO

Featured Paper

Cryptography: How It Helps in Our Digital World

Sponsored by Maxim Integrated

Gain a basic understanding of how cryptography works and how cryptography can help you protect your designs from security threats.

Click here to download the whitepaper

Featured Chalk Talk

Accelerate HD Ultra-Dense Multi-Row Mezzanine Strips

Sponsored by Mouser Electronics and Samtec

Embedded applications are putting huge new demands on small connectors. Size, weight, and power constraints are combining with new signal integrity challenges due to high-speed interfaces and high-density connections, putting a crunch on connectors for embedded design. In this episode of Chalk Talk, Amelia Dalton chats with Matthew Burns of Samtec about the new generation of high-performance connectors for embedded design.

More information about Samtec AcceleRate® HD Ultra-Dense Mezzanine Strips: