Embedded

Back to Editors' Blog

A Faster Fourier Transform

by Bryon Moyer

January 19, 2012 at 11:54 AM

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

Channels

Embedded. FPGA.

 
    submit to reddit  



Please add a comment

You must be logged in to leave a reply. Login »

Related Articles

Who Controls the Power?

Open Power Foundation Aims to Make PowerPC More Plentiful

by Jim Turley

Once upon a time, there were many little RISC processors frolicking in the deep green microprocessor forest. There was the jaunty little ARM. The bright little SPARC. The mighty little MIPS. The aristocratic little PowerPC. And so many others. They all played and laughed and had ever such a good time.

Then, one by one, the happy little RISC processors started disappearing. Were they gobbled up by the big, bad CISC processor that lurked in the woods? Did they cross over the Wheatstone Bridge and into another land? Or did they just get lost in the tall grass, wandering aimlessly until their mommies and daddies forgot about them? ...

iWatch, You Speculate Incessantly

by Bruce Kleinman, FSVadvisors

I held out as long possible before writing anything iWatch related. The irony is that I am iFatigued with everyone iGuessing about an iUnnanounced product, and yet here I am contributing to the noise. iCaramba! The proverbial last straw: I read a piece comparing Microsofts unannounced wearable to Apples unannounced wearable. OMG.

And AFTER deciding to write this piecebut before I could startanother piece appeared with the declarative headline Heres Everything We Know About the iWatch. And because I cannot make up stuff this good, apparently the things we KNOW include:...

FPGA-Prototyping Simplified

Cadence Rolls New Protium Platform

by Kevin Morris

System on Chip (SoC) design today is an incredibly complicated collaborative endeavor. By applying the label System to the chips we design, we enter a...

Dont Pass Me By

Project Ara Dev Boards and the Internet of Moving Things

by Amelia Dalton

The pedal is to the metal, our motor is running, and Fish Fry is hitting the open road. At the wheel this week is mCube...

FPGAs in the IoT

Lattice iCE40 Ultra Brings Programmability to Wearables

by Kevin Morris

In the 1960s, an electronic device was cool if it had the word transistor in it. Even though the general public didnt understand the...


Login Required

In order to view this resource, you must log in to our site. Please sign in now.

If you don't already have an acount with us, registering is free and quick. Register now.

Sign In    Register