The Fast Fourier Transform (FFT) is a family of numerical algorithms which has a large number of uses in many fields of computational science and in particular in signal and image processing. Typically the transformation can be thought of as taking a signal which is a function of time, for example, the amplitude of an audio track as it oscillates through time, and transforming it into an equivalent representation in the frequency domain, i.e., expressing the signal in terms of the sinusoid frequencies which it is comprised of. Sometimes the input signal describes a function not of time, but rather of space, and rather than a single-dimensional signal, the signal can be two dimensional, three dimensional or even of a higher rank. For example, jpeg and mpeg encodings transform images (two-dimensional spacial signals) into the frequency domain, using the Discrete Cosine Transform, which is a close relative of the Discrete Fourier transform.
A good FFT library is not easy to implement. Usually, algorithms aren’t dependent on the exact number of elements fed into them as input. FFT is different, in an annoying manner: an efficient FFT algorithm does look quite different for different numbers of inputs. Let’s illustrate that with an example: a sorting algorithm that works well for 1024 elements, will generally also work well for 1033 elements. However, an efficient FFT algorithm for 1024 elements typically cannot even handle 1033 elements correctly! That’s because efficient FFT algorithms depend on the prime factorization of the number of elements in the input. The best case is possible when the input size is a power of two, but that’s not always the case, and padding the data to the next power of two distorts it.
Other sources of complexity in FFT implementations come from
- The handling of multi-dimensional transforms
- Handling of forward vs. inverse FFT transforms
- Different types of transforms for real vs. complex numbers
- Numerical stability
Therefore, developing an accurate, efficient and general (i.e., one that can handle arbitrary input sizes) FFT library is not an easy task! Fortunately us, the DirectX SDK already contains such a library, which originated from a long-term and grounds-breaking Microsoft research on FFT libraries and their tuning for GPUs.
Now that we have some background on FFT, I’ll stop here and in my next post I’ll share an FFT library for C++ AMP (a wrapper over the DirectX FFT API).