AlwaysLearn

A DFT and FFT TUTORIAL

A DFT is a "Discrete Fourier Transform". An FFT is a "Fast Fourier Transform". An FFT is a DFT, but is much faster for calculations. The whole point of the FFT is speed in calculating a DFT.

DFT and FFT

FFT

An 8 Input Butterfly

<< Previous Next >>

Here is an example of an 8 input butterfly:

Butterfly 8 Input Example

An The 8 input butterfly diagram has 12 2-input butterflies and thus 12*2 = 24 multiplies.

N Log N = 8 Log (8) = 24. A straight DFT has N*N multiplies, or 8*8 = 64 multiplies. That's a pretty good savings for a small sample. The savings are over 100 times for N = 1024, and this increases as the number of samples increases.

 

You can keep expanding the butterfly by the same procedure.

<< Previous Next >>