A New Faster Fourier Transform Can Speed One of IT's Fundamental Algorithms

Even faster than the fast Fourier transform

By Clay Dillow Posted 01.18.2012 at 4:07 pm 10 Comments

The Fast Fourier Transform From many irregular signals, one. Christine Daniloff via MIT News

An algorithm called the fast Fourier transform is one of the most important aspects of your digital life that you never think about. It’s a core concept in information technology, making possible the signal processing, image and audio compression, and other complex mathematics necessary for you to cram every episode of Breaking Bad onto your mobile device alongside every track Jay-Z ever made, and then play it all back without a hitch.

Basically, the Fourier transform turns irregular signals into pure frequencies, so the fluctuating voltage signal traveling through a wire from your MP3 player to a set of speakers can be translated on the fly into the sounds you want to hear. The algorithm does this so quickly it earned the name “fast” (as in “fast Fourier transform,” or FFT). And it’s about to get faster.

A team of MIT researchers is this week presenting a new algorithm that boosts the performance of the FFT in a large number of cases. That’s good news for you, as it spells a future where, for instance, mobile devices might transfer large video files without burning all their bandwidth and battery in the process.

Without getting too deep into the nuts and bolts (of which there are many, available for your perusal over at MIT News), FFT takes the various samples within a signal (these samples are at a range of frequencies) and expresses them as a weighted sum of those frequencies. Some of those frequencies are more important than others, and hence are weighted more heavily. In fact, many of those samples are weighted so weakly as to not be necessary at all. They can be discarded with negligible loss of quality.

The new algorithm outpaces the old FFT by slicing a signal into narrow slices of bandwidth, with each slice containing just one heavily weighted frequency. From there, via some clever filtering and further slicing of each slice into smaller slices still, the new algorithm quickly separates the low-weighted frequencies and isolates the highly-weighted signals. In “sparse” signals--those with a relatively small number of heavily-weighted frequencies--the new algorithm basically cuts to the chase more quickly than the old, extracting what you need and filtering out what you don’t.

For things like file compression, that’s key. And given that most natural signals are indeed sparse--they include few heavily weighted signals that we need and a bunch of noise that we don’t necessarily have to have--the new FFT could drastically increase the speed at which signals are processed in many cases, sometimes providing a tenfold boost in speed. Given that the current Fourier transform method was already quite fast, that’s serious improvement.

Previous Article: Newly Found Meteorites Came From Mars, Scientists Confirm

Next Article: When Seconds Count: Today's UN Debate Could Abolish the 'Leap Second'

10 Comments

Link to this comment

the_man

01/18/12 at 6:24 pm

i dont get it...

Link to this comment

eregorn8

01/18/12 at 8:07 pm

@the_man:

Imagine your playing a cord on the Piano, say C major:

C - 130hz
E - 209hz
G - 176hz

Each of those notes creates a sinusoidal curve like in the picture above, but when played as a chord, they combine and create a funky curve like the blue one on the bottom.

What this algorithm can basically do is pick out the C, E, and G faster then previous ones.

Link to this comment

turtlepokerman

01/19/12 at 1:40 pm

Does this mean I have to retake my Signals and Systems class that dealt with this subject?

Link to this comment

suddenmischief

01/20/12 at 3:08 pm

Thanks for the simplification @eregorn8. After the first two paragraphs the "clear explanation" got a bit lost.

Link to this comment

tcolguin

01/20/12 at 8:49 pm

turtlepokerman if you don't understand it maybe you should. On the other hand if you did understand the concept nothing has changed, just the method to arrive at the same results has changed.

Link to this comment

artichoke

01/22/12 at 4:39 am

6.015 (that dates me) didn't deal much in FFT techniques. More like what Fourier and z transforms are, their properties, and how to use them to analyze circuits.

The FFT method described sounds quite complicated, but specialized for cases where we expect the transform to be concentrated on a few frequencies, but we don't know much more than that (so that, for example, the input signal is not impulses in time domain.)

Reminds me of the ellipsoid method of solving linear programs. It was touted publicly as being wonderful, and for certain problems it was, but it was almost impossible for even professionals in the field to understand. The guy who designed it wrote a textbook, which was also impossible to understand. :)

Link to this comment

nicabod

01/27/12 at 5:17 pm

Nicabod

The illustration that starts the article is disgraceful; there's no way the three sinusoids could create the resultant waveform. Those fast wiggles toward the origin couldn't come from any of the three sinusoids. Furthermore, if one assumes that the first resultant cycle is valid, the resultant waveform couldn't have so much less higher-frequency content in the second cycle. The artist who created this is woefully ignorant about real-world, practical Fourier synthesis. At least, the first three surely do look like sinusoids, and color is nice.

Popular Science may adapt abstruse topics for the public, but such misleading incompetence as this is a shame.

Otoh, the diagram at the MIT page looks totally believable.

Sorry to squawk, but I expect better!

= = = = =
Midnight computer hacker (non-malicious) in 1960
Former mechanical analog computer technician

Link to this comment

nicabod

01/27/12 at 5:44 pm

Quote from the MIT article:
"It’s a method for representing an irregular signal — such as the voltage fluctuations in the wire that connects an MP3 player to a loudspeaker — as a combination of pure frequencies."

Makes sense; Fourier transforms are not new to me; I learned about mechanical harmonic analyzers (and synthesizers, especially tide predictors), in my high school days (though, for sure, not in school!)

Partial quote from this article:
"... the fluctuating voltage signal traveling through a wire from your MP3 player to a set of speakers can be translated on the fly into the sounds you want to hear."

Un believable!! Utterly munged! Signal traveling through the wire has to be translated? Seems to me that what's in the speaker wire is already what you want to hear, or have I really lost it? Do the loudspeakers, themselves, do Fourier synthesis? They do not reproduce perfectly, but they most assuredly do not do that. Sorry; this is disgracefully-poor editing!

Again, I hate to complain, but can't let this go without commenting on it.

Nicabod
Midnight computer hacker (non-malicious) in 1960
Former mechanical analog computer technician

Popular Tags

Science

All Tags All Photos All Videos

Science

+ More Photo Galleries

June 2013: American Energy Independence

Five amazing, clean technologies that will set us free, in this month's energy-focused issue. Also: how to build a better bomb detector, the robotic toys that are raising your children, a human catapult, the world's smallest arcade, and much more.