FFFFT (the fast fast fast Fourier transform)

No, it’s not the sound of the air being let out of your tires!

Researchers at the Massachusetts Institute of Technology have just published a ground-breaking computational method for analyzing digital signals, including sounds and images.

The Fourier Transform is a way to break a complicated signal down into its most basic components, and it’s how computers manipulate things like acoustic and visual information—everything from your jpeg and mp3 files up to complicated acoustic measurement and analysis gear that consultants like ourselves use daily.

Fourier Transform

The last major improvement in the efficiency of the Fourier Transform came in the 1960s, with the advent of the “Fast” Fourier Transform (often denoted FFT).  That was a long time ago, but the FFT is still the method of choice for on-the-fly number crunching in everything from cellphones to video games to high-end audio and graphics workstations.

The new algorithm that MIT has devised (a “nearly optimal sparse Fourier transform”) is substantially faster than the FFT for a large range of realistic and useful cases—up to 10 times faster.  It isn’t hard to imagine that such a major leap in efficiency will lead to smaller, cheaper, and more powerful electronics, since the work they do under the hood just got a whole lot easier!

[via MIT News. Graphic: Christine Daniloff]

Tags: ,