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.


  • 3
    $\begingroup$ This should be a comment. $\endgroup$
    – Tendero
    Jan 3 '17 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.