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
Sep 21, 2020
Technology is changing the strategies we use to do things - oh so fast that 2010 seems like a distant past- within many spaces -- including the way we do our current topic of interest - Timing... [[ Click on the title to access the full blog on the Cadence Community site. ]]...
Sep 21, 2020
Semicon, the world’s largest semiconductor conference and exhibition, is September 23-25 in Taiwan. Like most shows of its size and caliber, Semicon boasts a long and illustrious list of exhibitors (500+), and countless forums, symposiums, and workshops. Of course Semic...
Sep 18, 2020
[From the last episode: We put the various pieces of a memory together to show the whole thing.] Before we finally turn our memory discussion into an AI discussion, let'€™s take on one annoying little detail that I'€™ve referred to a few times, but have kept putting off. ...
Sep 16, 2020
In addition to the Great Highland (Scottish) bagpipes, the Uilleann (Irish) bagpipes, and the Northumbrian (English) bagpipes, there are myriad other offerings spanning the globe....

Featured Video

Four Ways to Improve Verification Performance and Throughput

Sponsored by Cadence Design Systems

Learn how to address your growing verification needs. Hear how Cadence Xcelium™ Logic Simulation improves your design’s performance and throughput: improving single-core engine performance, leveraging multi-core simulation, new features, and machine learning-optimized regression technology for up to 5X faster regressions.

Click here for more information about Xcelium Logic Simulation

Featured Paper

Helping physicians achieve faster, more accurate patient diagnoses with molecular test technology

Sponsored by Texas Instruments

Point-of-care molecular diagnostics (PoC) help physicians achieve faster, more accurate patient diagnoses and treatment decisions. This article breaks down how molecular test technology works and the building blocks for a PoC molecular diagnostics analyzer sensor front end system.

Read the Article

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: