The Butterfly Diagram
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.
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:
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.