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.'"
Lossy compression such as MP3, AAC, and according to TFS also video compression, are all fundamentally based on FFT (fast fourier transforms). Depending on how well this new specific method works, we could see decreases in the time it takes to encode all this stuff. Which can be quite a long time... have you ever tried to do a 2-pass MPEG 4 conversion on a feature-length digital video? Video encoding doesn't scale well to multiple cores either, so nowadays when performance increases coming mostly from adding more cores... video encoding hasn't been getting faster at the same pace it used to. I'm thinking this new FFT algorithm could make a big difference in encoding speeds.
Additionally, I know lots of audio (and I'm assuming video) effects, DSPs of the kind you find in Adobe Audition, Audacity, et al., rely on FFTs. Computing such effects could get a lot faster. With increases in both the speed of adding effects, and compression afterwards, we might be seeing a significant speedup in the overall digital audio/video-editing process.
Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.
In the DFT case the signal is merely a finite number of samples, so you can forget about the time-dependence and look at it as a long vector. If you sit down and work out the maths, you find that the vectors corresponding to the constant function and the various sinusoids are linearly independent.
All you're really doing then is solving a system of linear equations---they don't just have to be sinusoids, you could find the coefficients for any linearly independent set of functions. You could just as easily replace one of the sinusoids with an exponential function and still get coefficients out such that you could do your weighted sum of vectors and get back your original function.
This isn't right. The proposed algorithm is better on sparser signals, but is a regular FFT. The point is that many things we want to compress are sparse, or at least have pieces that are sparse. In JPEG, for example, images are broken into 8x8 pixel blocks and then DCT'ed (which is similar to FFT). Many of those blocks might be sparse, and benefit from this new approach, even if the most complex blocks aren't and don't benefit.
Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.
Informative and wrong. When you calculate powers of 4096 bit numbers, the fastest way to calculate the 4096 bit products is convolution via FFT.
"Sit down and work out the maths" is really just code for "here's one I prepared earlier". If you're keen on this sort of thing, read a bit about solving systems of linear equations, and you will hopefully be able to look at the problem, exclaim "this is trivial!" and live forever happy in the knowledge that it is indeed theoretically soluble (as I tried to describe above) without having to concern ones self with the computational subtleties that suck all of the fun out of it.
MIT OCW have a set of videos on linear algebra if your curiosity is sufficient to justify chewing up some time on it. Probably some of the most useful partially-post-high-school maths that one can learn. Here is a free textbook on it.
Nope. FFTs are used in many fields, but cryptography is not one of them. Not since the old analog radio scramblers of decades past.
Informative and wrong. When you calculate powers of 4096 bit numbers, the fastest way to calculate the 4096 bit products is convolution via FFT.
These matrices are not sparse, though, and thus the algorithms under discussion are not suitable, or any faster than FFT.
The interesting thing is that the greater time window over which the FFT operates, you can observe finer frequency detail within that particular window at the expense of how quickly the graph or bars change over time (in simplistic terms). I wonder how this new algo will change the frequency detail/transient time detail trade-off. Do we see more detail in both domains? Less? The same?
This is a property of the Discrete Fourier transform itself. For a certain window size there are only a discrete number of frequencies that you can calculate.
The larger your window-> The more frequenecies you can see (at the expense of a longer sampling time)
FFT algorithms simply try to compute the DFT quickly, this advance is significant for paractical applications but doesn't change the underlying mathematics.
Multiplications in time domain = convolution in transformed domain
Sometimes it's easier to go to the transformed domain, convolute and then go back to time domain :)
Yes, FFT may be used in cryptography. But this is unrelated, as the first post in this thread talks about security. FFT has no connection to the security of cryptosystems.
As far as I'm aware, the security of *absolutely no* cryptosystem used in practice depends in any way on the FFT.
Yes, FFT gives us a way to multiply big integers quickly. But all cryptosystems that use big integers already *do* assume that everyone *can* multiply big integers quickly. Even if there was a ten-times speedup, this would mean absolutely no danger to their security.
(And one final nitpick: FFT is not the fastest way to multiply 4096-bit integers, those are still considered fairly short and you would probably gain a better performance out of some simpler-but-asymptotically-slower algorithm.)
Exactly represented, yes, but not practically so.
Often the signal you are looking for doesn't have a frequency that fits well with the FFT frequency distribution. (The sampling time is not evenly divisable by the signal period time.)
This causes a pure sinus signal at the wrong frequency to be visible as a spread of frequencies where it is almost impossible to see adjacent signals with a lower amplitude.
Being able to calculate DFT with a method that doesn't have the same requirements the FFT algorithm have might give some nice benefits to signal analysis.
I guess we will have to wait until they have presented their method until we know if it will have any practical uses.
For numbers that are small enough to fit in your processor's registers, multiplication is a constant-time process. But when dealing with numbers much larger than your processor's word-length (more than 4 bytes), you have to resort to the long-mulitplication algorithm. As it turns out, multiplying polynomials is exactly the same as convolution, and is O(n^2), and long multiplication is a special case of polynomial multiplication, where the variable is fixed:
525 * 343 = (5x^2 + 2x + 5) (3x^3 + 4x + 3), for x = 10
So for two large numbers, rather than going through the long process of convolving the digits (long-multiplying), you do the following process:
You can run the same mathematical processes on a TMS320, DSP56K, FPGA, desktop PC, GPGPU video card, embedded ARM, PIC, AVR, even a 4-bit micro if you feel the need.
You can just as well run it on vacuum tubes or relays, however there are no real-world applications for that -- and the same applies for 8-bit microcontrollers.
An AVR has no trouble doing DTMF decoding on values captured from the ADC,
DTMF is specifically designed to be easy to decode with the worst possible limitations on a decoder. Claiming that it makes a microcontroller capable of DSP would be like saying that a lightbulb can be used to calculate exponents because it can produce a close approximation of a black body radiation spectrum.
or running a few DDS channels to generate sine waves and throw them out a PWM channel, despite those being classical DSP applications.
In name only. There is no actual processing involved.
- Signed, someone who does DSP for a living.
So do I, however I don't count trivial operation on tables of precomputed values as "DSP".
Contrary to the popular belief, there indeed is no God.
I think the parent is getting at a problem I see at my job fairly frequently. Professional Firmware and DSP developers that have no knowledge about the effects or consequence of their code on the hardware itself. Ultimately re-implementing something that used to run fine in 1/10th the ram, and 1/40th the processor cycles (or less) in a brand new dual core DSP and still can't figure out why they aren't meeting performance requirements. I've seen these guys demand a bigger, faster, more power hungry CPU to run their code when a previous version that was literally a fraction of the capability ran the same algorithm.
True Story: I'm an FPGA dev, and I was helping out software guys debug why the DSP was completely missing messages and seemed to be dropping data. Turns out doing a thousand lines of heavy DSP INSIDE the interrupt handler is probably going to hang up the CPU and cause it to miss interrupts. The worst part was the blank stares we got when we told them this, and had to explain why that was a bad thing.
It seems the idea of actually writing good, fast, and power efficient code is a dying art because it's perceived as 'not necessary'. In some instances this thinking is correct (e.g. desktop computers), but in the embedded space where you're trying to keep the cost of final products down and minimize power usage, grabbing the fastest DSP part that TI makes is probably not always the best solution... but it's what you get when you think it's automatically OK/good to 'do everything in software'. There are costs and penalties to account for.
For pure hobbyists, none of this really applies, but I suspect that a good many of the people that do this stuff as a hobby are also at least tangentially involved in it in some way at their jobs, so it serves to bring up the considerations.