Even faster than the fast Fourier transform
Posted 01.18.2012 at 3:07 pm
10 Comments
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.
Related Articles
Tags
Science, Clay Dillow, batteries, energy, fast fourier transform, file compression, information sciencesWithout 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.
10 Comments
To comment, please Login.
Popular Tags
Science
138 years of Popular Science at your fingertips.
Innovation Challenges
Popular Science+ For iPad
Each issue has been completely reimagined for your iPad. See our amazing new vision for magazines that goes far beyond the printed page
Download Our App
Stay up to date on the latest news of the future of science and technology from your iPhone or Android phone with full articles, images and offline viewing
Follow Us On Twitter
Featuring every article from the magazine and website, plus links from around the Web. Also see our PopSci DIY feed
March 2012: The Future of Medicine
A 10,000-rpm, no-pulse heart is completely revolutionizing how we think about transplants. Plus: rapid-response virus hunters, a shocking cure for migraines, the world's youngest person to have achieved nuclear fusion (in his parents' garage!), and much more.
Popular on Popsci
Most Viewed
Science
- Bummer: Faster-Than-Light Neutrinos Weren't, and It Was the Cable Guy's Fault
- How Pigs on Antibiotics Are Making Superbugs Stronger
- Russian Scientists Grow Pleistocene-Era Plants From Seeds Buried By Squirrels 30,000 Years Ago
- How We're Creating "Terminator Vision" in Your Future Contact Lenses
- FYI: Will People Ever Evolve Out of Craving Unhealthy Food?
- FYI: Do Competitive Eaters Have Unusual Stomachs?
- Images of the Week, February 13-17, 2012
- The Most Amazing Science Images of the Week, February 13-17, 2012
- Depression Can Be Diagnosed With a Blood Test
- Tonight, We'll Be at Star Talk Live With Neil de Grasse Tyson and Eugene Mirman
Most Emailed
Science
- Bummer: Faster-Than-Light Neutrinos Weren't, and It Was the Cable Guy's Fault
- How Pigs on Antibiotics Are Making Superbugs Stronger
- Russian Scientists Grow Pleistocene-Era Plants From Seeds Buried By Squirrels 30,000 Years Ago
- How We're Creating "Terminator Vision" in Your Future Contact Lenses
- FYI: Will People Ever Evolve Out of Craving Unhealthy Food?
- FYI: Do Competitive Eaters Have Unusual Stomachs?
- Images of the Week, February 13-17, 2012
- The Most Amazing Science Images of the Week, February 13-17, 2012
- Depression Can Be Diagnosed With a Blood Test
- Tonight, We'll Be at Star Talk Live With Neil de Grasse Tyson and Eugene Mirman
Most Commented
Science
- The Boy Who Played With Fusion
- Found: The Oldest Animal Ever on Planet Earth
- Bummer: Faster-Than-Light Neutrinos Weren't, and It Was the Cable Guy's Fault
- 200,000-Year-Old Patch of Seagrass Is the World's Oldest Living Organism
- Russian Scientists Grow Pleistocene-Era Plants From Seeds Buried By Squirrels 30,000 Years Ago
- FYI: Do Competitive Eaters Have Unusual Stomachs?
- FYI: Will People Ever Evolve Out of Craving Unhealthy Food?
- Compound Reinvigorates Classic Antibiotics In Fight Against New Superbacteria
- Video: Watch Kink Instability Corkscrew a Jet of Super-Hot Argon Gas
- FYI: What Is the Oldest Toy in the World?
Today on PopSci.com
Copyright © 2009 Popular Science
A Bonnier Corporation Company. All rights reserved. Reproduction in whole or in part without permission is prohibited.
i dont get it...
F.M., Frequency Modulation Addition does a mind and Computational Brain good!
......................
SPOOKY!...... Life is
@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.
Does this mean I have to retake my Signals and Systems class that dealt with this subject?
Thanks for the simplification @eregorn8. After the first two paragraphs the "clear explanation" got a bit lost.
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.
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. :)
Ewww, I must admit, this is a game changer but using "Jay-z" as a trendy supporting fact made me cringe a little. I imaging that quantum computers will have a final say in this algorythm. I would expect that this is far from the latest and greatest we will see on this in the near future. This is definitely a field that media makers, being so concerned with piracy, would take note of.
"Do not try and bend the spoon. That's impossible. Instead... only try to realize the truth. There is no spoon."
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
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