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 20, 2018
https://youtu.be/KwrfcMtbMDM Coming from CDNLive Japan (camera Asushi Tanaka) Monday: Nicolas's Recipe for Digital Marketing in EDA Tuesday: Embargoed announcement Wednesday: Trends, Technologies, and Regulation in China's Auto Market Thursday: Breakfast Bytes Guide...
Jul 19, 2018
In the footer of Samtec.com, we'€™ve always made it easy to contact us by phone, email, or live chat (even fax back in the day!). To continue to progress this theme, you'€™ll now find a new helpful tool in the footer area of Samtec.com. This tool will match you up with yo...
Jul 16, 2018
Each instance of an Achronix Speedcore eFPGA in your ASIC or SoC design must be configured after the system powers up because Speedcore eFPGAs employ nonvolatile SRAM technology to store the eFPGA'€™s configuration bits. Each Speedcore instance contains its own FPGA configu...
Jul 12, 2018
A single failure of a machine due to heat can bring down an entire assembly line to halt. At the printed circuit board level, we designers need to provide the most robust solutions to keep the wheels...