I often see the term "butterfly" in discussion and methods relating to DSP. What is a "Butterfly?"
-
2$\begingroup$ The first Google result for "fft butterfly" describes it pretty well. $\endgroup$ – Jason R Jan 3 '17 at 1:51
-
$\begingroup$ First port of call for definitive answers is (for me at least), here. $\endgroup$ – Mark Jan 3 '17 at 2:08
-
$\begingroup$ Have you tried this ? $\endgroup$ – Tendero Jan 3 '17 at 2:11
-
$\begingroup$ Late to the party and a dollar short. $\endgroup$ – Mark Jan 3 '17 at 2:12
Wikipedia has this one covered:
In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data-flow diagram in the radix-2 case, as described below.1 The earliest occurrence in print of the term is thought to be in a 1969 MIT technical report.[2][3] The same structure can also be found in the Viterbi algorithm, used for finding the most likely sequence of hidden states.
(Source)
-
3