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

The Butterfly Diagram

<< Previous Next >>

The Butterfly Diagram builds on the Danielson-Lanczos Lemma and the twiddle factor to create an efficient algorithm. The Butterfly Diagram is the FFT algorithm represented as a diagram.

First, here is the simplest butterfly. It's the basic unit, consisting of just two inputs and two outputs.

Butterfly Diagram 2 Inputs

 

That diagram is the fundamental building block of a butterfly. It has two input values, or N=2 samples, x(0) and x(1), and results in two output values F(0) and F(1). The diagram comes form the D-L Lemma for two inputs.

This can be shown by taking equation 7 above and plugging in for values n=0 and n=1, thus:

DL Lemma and Butterfly 2 Input Match

So, the Butterfly comes from the Danielson-Lanczos Lemma, but it also uses the twiddle factor to take advantage of redundancies and symmetry in the D-L Lemma.

To get a full understanding of the Butterfly, a four input Butterfly will be required. That is described next.

<< Previous Next >>