I am afraid that the definition of the Fast Fourier Transform (FFT) given above is not strictly correct. The FFT is simply an algorithm for calculating the Discrete Fourier Transform with far fewer multiply-accumulates (MACs) than the direct approach.
To start at the beginning, the Fourier Transform is an integral transform that transforms from the time domain to the frequency domain, and vice versa. The transform is inherently complex (in that it uses complex numbers) even if the time domain signal consists only of real numbers. To describe a given sinusoid in the frequency domain one needs to specify amplitude and phase; which inherently leads to a complex number. Many modern systems, like your mobile 'phone, use complex time signals as well.
The Discrete Fourier Transform is simply a sampled version of the Fourier integral, where the integral is replaced by a summation sign. The output is a series of discrete frequencies, but complex as before. The DFT can also be represented as a matrix multiplication. For a input sequence of N points the DFT requires on the order of N² operations. Each operation is complex, so it requires four real multiplications and two real additions. This can get out of hand pretty quickly! Let's say we want to do a FFT of 1024 samples every 1ms for real time control. That's not particularly fast, but it will involve 1024*1024 = 1048576 operations in 1ms. That's one operation roughly every 1ns, and remember each operation is four multiplies and two additions. You ain't going to be doing that on a PIC, not even one of their mini-DSPs!
The original Fast Fourier Transform was described by Cooley and Tukey in 1965. In essence it takes the matrix form of the DFT and splits the matrix into a series of matrices, each one of which is calculated in turn. At first sight this doesn't seem to be a sensible thing to do. But it turns out that the coefficients in each of the matrices are far simpler than those in the original DFT matrix. In fact the first matrix in the FFT only involves 0, 1 and -1. The upshot is that the FFT can be used to calculate the DFT using on the order of N*log2(N) operations. So for our 1024 point DFT that is 1024 times the log base 2 of 1024, which is 2 to the power 10, so 1024 x 10 = 10240. Quite a reduction in MACs! One issue with the basic FFT is that the results come out in bit reversed order. Some DSP chips have special instructions for re-ordering bit reversed data.
There endth the lesson, as I need to get my rear in gear and tackle the jungle that is masquerading as my garden.
If anybody is interested in the mathematics I can write some of it down and post it in an album. It is not really amenable to trying to write it within a post.
Regards,
Andrew
Note: DSP = Digital Signal Processor – a processor optimised to calculation MACs and used for high end real time signal processing