An 8 Input Butterfly
Here is an example of an 8 input butterfly:
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 >>|