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

Softly Defined Networks

Xilinx Punches Up the Programmability

by Kevin Morris

Programmability is a powerful concept. It allows us to build a physical machine and then modify, upgrade, repurpose, repair, and evolve it - without having...

Why Dont They Just

The Quest for Truth in Engineering

by Kevin Morris

Why dont they just put solar cells on top of cars and power them that way?

His tone implied that the engineers designing cars were just idiots, and he was sure he could do better - with just this one idea. I was going to answer with some helpful information about the amount of energy required to operate an automobile, the amount of energy collected by even idealized solar cells, and the amount of area available on top of a typical vehicle. I didnt get the chance.

His friend interrupted, Well thats just the government shutting them down. The oil companies have the government in their pocket, and theyre not about to let anyone develop technology like that. Its the same with that 200 MPG carburetor that guy in Florida invented

Now, I was more hesitant to speak. I wanted to explain that modern, sensor-driven, computer-controlled fuel injection systems did a much better job achieving near-ideal fuel-air mixtures than any carburetor could ever hope to accomplish. I didnt get the chance....

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...


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