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
Nov 15, 2019
As we seek to go faster and faster in our systems, heat grows as does the noise from the cooling fans. It is because of this heat and noise, many companies are investigating or switching to submersible cooling (liquid immersion cooling) options. Over the last few years, subme...
Nov 15, 2019
Electronic design is ever-changing to adapt with demand. The industry is currently shifting to incorporate more rigid-flex circuits as the preferred interconnect technology for items that would otherwise be off-board, or require a smaller form factor. Industries like IoT, wea...
Nov 15, 2019
"Ey up" is a cheery multi-purpose greeting that basically means "Hello" and "Hi there" and "How are you?" and "How's things?" all rolled into one....
Nov 15, 2019
[From the last episode: we looked at how intellectual property helps designers reuse circuits.] Last week we saw that, instead of creating a new CPU, most chip designers will buy a CPU design '€“ like a blueprint of the CPU '€“ and then use that in a chip that they'€™re...
Nov 15, 2019
Last week , I visited the Cadathlon@ICCAD event at the 2019 International Conference on Computer Aided Design . It was my first CADathlon and I was quite intrigued , since the organizers webpage... [[ Click on the title to access the full blog on the Cadence Community site. ...