##
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 P^{2} 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*