The Fast Fourier Transform is a simply a method of laying out the computation, which is much faster for large values of N, where N is the number of samples in the sequence. It is an ingenious way of achieving rather than the DFT's clumsy P2 timing.
The idea behind the FFT is the divide and conquer approach, to break up the original N point sample into two (N / 2) sequences. This is because a series of smaller problems is easier to solve than one large one. The DFT requires (N-1)2 complex multiplications and N(N-1) complex additions as opposed to the FFT's approach of breaking it down into a series of 2 point samples which only require 1 multiplication and 2 additions and the recombination of the points which is minimal.
For example Seismic Data contains
hundreds of thousands of samples and would take months to evaluate the
DFT. Therefore we use the FFT.
On to Time Decimation or back to Introduction to the FFT
or back to FFT Contents or back to Main Contents