Slashdot Mirror
Faster-Than-Fast Fourier Transform
First time accepted submitter CanEHdian writes "MIT news reports on research done resulting in a Faster-than-fast Fourier Transform algorithm. 'At the Association for Computing Machinery's Symposium on Discrete Algorithms (SODA) this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform. Under some circumstances, the improvement can be dramatic — a tenfold increase in speed. The new algorithm could be particularly useful for image compression, enabling, say, smartphones to wirelessly transmit large video files without draining their batteries or consuming their monthly bandwidth allotments.'"
It doesn't improve the regular FFT but only sparse variants. Image or Audio compression nearly always uses the regular non-sparse FFT.
Jan
I'm sure I'm not the only person who completely understands what a FFT does but simply can't get his head around the actual implementations details. I simply don't get how a signal of many mixed frequencies which essentially means the amplitude is moving all over the place can travel through some equations and a neat list of the fundamental and harmonics can pop out. Its mathematical magic to me. Wish I could "get" it. But I guess I'll just have to settle for using it.
While I do argue with your point, there are a ton of devices that would benefit from it. Why do you think the implementations of FFT for 8/16-bit microcontrollers such as the 8051 are so popular? DSPs are popular in applications that make heavy use of FFT, but there are a ton of general purpose implementations that require FFT algoritms, ranging from multitone generation/decoding to D/A conversion. Why should I use 2 ICs (plus assorted external logic) on a given circuit, if I can easily do it in software on my general-purpose microcontroller, that besides the integrated ram and rom, also bundles me with a serial port, multiple I/O ports and a ton of "extra" features, at a fraction of the price?
Well, if for some reason someone is already using Arduino boards to do a bunch of stuff it might make sense if it was just fast enough. But yeah, if you have a choice it doesn't make much sense to pick an Arduino for this task.
So far the only "usefulness" I've seen in the Arduino has been for that retro kick, being artificially limited to the kind of environment I haven't had to work in for a long time, but if I wanted to build something useful I'd probably at least want a 16-bit processor these days, the difference in price is negligible for any hobby project (hell, a 32-bit processor probably wouldn't be a major budget concern considering what you're likely to spend on the rest of your hardware when building something)...
Greylisting is to SMTP as NAT is to IPv4
It's more than a property of the DFT - it's a much deeper mathematical truth than that. The same fundamental mathematics is used to derive the uncertainty princible in quantum mechanics: For a signal to be perfectly defined in frequency it must be infinite in time, and vice versa. When you apply the same to quantum wave-functions... the uncertainty limit isn't a limit on measurements. It's a limit on what the universe is capable of representing.
Do you have math showing the compression consumes less power than just transmitting the raw data?
Lots of it, the power budget drives the design of the entire sensor.
The micro-controller uses a lot less energy than the packet radio so it makes sense to process the raw sensor data on-board and transmit information such as fourier coefficients, integrals and other statistics. Every packet saved is another fraciton of a second the radio can be powered down.
It's a fairly common technique with sensor networks to process raw signals at the point of collection and transmit only the useful information, it makes the most use of your bandwidth and in this case energy.