1
$\begingroup$

In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', which seem to refer to the fact that an algorithm takes elements that are half an array away (where the array itself is a power-of-two in size), which mean that if you want to write an iterative implementation, that you will have to bit-reverse the indices of the input (or the output).

Is this indeed what is called 'Butterfly combinations'? And why are these called 'Butterfly combinations'? What is the origin of this name?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ The article you link links to Butterfly diagram, which seems to answer your questions? $\endgroup$
    – David Richerby
    Feb 3, 2019 at 21:16
  • $\begingroup$ Yes; it does! I had missed the link there. Thank you! $\endgroup$
    – Qqwy
    Feb 4, 2019 at 6:57
  • $\begingroup$ OK -- that was easy! It would be really great if you could post a brief answer to your question, which might help others in the future. Thanks! $\endgroup$
    – David Richerby
    Feb 4, 2019 at 10:13

1 Answer 1

Reset to default
1
$\begingroup$

So, a summary of the Wikipedia page on Butterfly Diagrams:

  • In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger one.
  • This is common in Discrete Fourier Transformation algorithms, as well as in the otherwise unrelated Viterbi Algorithm for finding the most likely sequence of hidden states.
  • It is called 'Butterfly' because of how it works in the base case where you combine two single-point results: Signal flow graph for two points. (Image courtesy of Wikipedia)
  • The earliest occurrence in print of the term 'Butterfly' is thought to be in a 1969 MIT technical report: C. J. Weinstein (1969-11-21). Quantization Effects in Digital Filters.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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