Constructing A 4 Input Butterfly Diagram
Here I will show you step-by-step how to construct a 4 input Butterfly Diagram.
Next extend lines and connect upper and lower butterflies.
Finally, labeling the butterfly.
Note the order of input values is "reverse bit" order. The Butterfly uses the natural expansion order of the Danielson-Lanczos Lemma, which is why the input is ordered that way. This was described earlier.
The four output equations for the butterfly are derived below.
The N Log N savings
Remember, for a straight DFT you needed N*N multiplies. The N Log N savings comes from the fact that there are two multiplies per Butterfly. In the 4 input diagram above, there are 4 butterflies. so, there are a total of 4*2 = 8 multiplies. 4 Log(4) = 8. This is how you get the computational savings in the FFT! The log is base 2, as described earlier. See equation 1.
In the next part I provide an 8 input butterfly example for completeness.