DFT Summary

The Discrete Fourier Transform (DFT) is used to produce frequency analysis of discrete non-periodic signals. The FFT is another method of achieving the same result, but with less overhead involved in the calculations..

Why the FFT ?

If you look at the equation for the Discrete Fourier Transform you will see that it is complicated to work out as it involves many additions and multiplications involving complex numbers. Even a simple eight sample signal would require 49 complex multiplications and 56 complex additions to work out the DFT. At this level it is still manageable, however a realistic signal could have 1024 samples which requires over 20,000,000 complex multiplications and additions. As you can see the number of calculations required soon mounts up to unmanageable proportions.

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