Slashdot Mirror
FFTs Using AltiVec on Linux and Mac OS X
GregAllen writes "After searching for a good open-source AltiVec implementation of the Fast Fourier Transform (FFT), I have put together the AltiVec FFT page. It has all of the source, some benchmarks, and runs on Mac OS X or LinuxPPC. I even compared it to the venerable (but scalar) FFTW."
an fft is a fast fourier transform. It is commonly used to transform data from the time domain to the frequency domain.
.jpg, or listen to an .mp3, or watch a dvd, etc. Lots of uses for them, and that doesn't even get into the engineering/scientific uses...
What this means is that is if you have a time-varying signal like audio for example, you can run an fft on it and get a frequency analysis on the sound. i.e. from the sound in a waveform format, after an fft, you can pick out which are the dominant frequencies, and what the relationship between frequencies are.
Although the fft is strictly not necessary because it is, after all, just a transform, it turns out that many media compression techniques use them because humans aren't as discriminating in the frequency domain so if you do lossy compression in the frequency domain, we won't notice/mind as much.
fyi, you do an fft any time you view a
You use a FFT anytime you ENCODE a .jpg, or an .mp3, or a DVD. When you view or listen or watch you are using an Inverse FFT.
And to be very specific, I think all your examples use DCT (Discrete Cosine Transform) and not FFT. JPEG definitely does. Very good overview here
It's important to point out that the "traditional way" to store complex numbers (and do an FFT) is with interleaved data. If your application uses interleaved data (and most do), then this library is for you. Split data is being used more because of the obvious performance improvements, but you have to change your code (and your mindset) to use it.
I've updated it to say: as much as twice as fast as vBigDSP on split data (but about the same on interleaved data).
I'd like to get an open-source split-data version to add to the site, so Linux users get good split-data FFTs, too.
Please help find my missing daughter: FindSabrina.org
Although people often use the terms interchangably, strictly speaking the Fourier Transform is the mathematical operation (like "sort") and the FFT is a particular way of computing it (like "quicksort").
.jpg, or an .mp3, or a DVD. When you view or listen or watch you are using an Inverse FFT.
... though again, the DCT and the FT are essentially the same operation -- the DCT is just the real part of the FT (the FT is complex).
The FFT is a particularly FAST algorithm for computing Fourier Transforms, with O(n log n) instead of O(n^2) for the naive algorithm -- thus the name. I believe that there is a comparably fast and very similar algorithm for computing the DCT, which doesn't really have a separate name.
You use a FFT anytime you ENCODE a
True, though an inverse Fourier tranform is simply the Fourier transform run through a complex complement and multiplication by a constant. The FFT and the IFFT are essentially the same algorithm.
And to be very specific, I think all your examples use DCT (Discrete Cosine Transform) and not FFT.
Right