2
$\begingroup$

Wikipedia presents butterfly as "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 ..."

The question is: What was the first time that FFT was represented by Butterfly Diagram ? References would be appreciated.

Improve this question
$\endgroup$
5
  • $\begingroup$ You might find the answer in the textbook "Introduction to parallel algorithms and architectures: arrays, trees, hypercubes" by Frank Thomson Leighton. He certainly discusses the FFT and butterfly diagram in the graduate course he teaches in conjunction with this book, or at least he did in the 90s. $\endgroup$
    – Patricia Hersh
    Commented Jun 4, 2012 at 12:18
  • $\begingroup$ Is the question asking for a reference to the first presentation of the butterfly diagram? Or, is it asking if the butterfly diagram was presented in the first discovery of the FFT? I believe it's the former, but I'm unsure. Regarding the latter, it seems unlikely given the FFT was known to Gauss. $\endgroup$
    – cardinal
    Commented Jun 4, 2012 at 15:07
  • 1
    $\begingroup$ The book I mentioned by Leighton indeed says on p. 778 "The butterfly network has its origins in the early work on discrete Fourier transforms". Various references for this and related networks are given in the bibliographic notes for Section 3.2 of Leighton's book. $\endgroup$
    – Patricia Hersh
    Commented Jun 4, 2012 at 15:35
  • $\begingroup$ @Patricia Hersh: Thank you! Unfortunatelly, I have no access to Leighton's book. BTW, Oppenheim and Schafer, Digital Signal Processing, Prentice Hall, 1975, Fig. 6.3, pp. 291, presents a "Flow graph of... DFT computations (N=8)". Fig. 6.8, pp. 296, "Flow graph of basic butterfly computation...". $\endgroup$
    – Papiro
    Commented Jun 4, 2012 at 17:50
  • $\begingroup$ quoth the FAQ: "research level math questions" Doesn't this belong on math.SE? $\endgroup$
    – Peter McNamara
    Commented Jun 4, 2012 at 20:13

1 Answer 1

Reset to default
3
$\begingroup$

A little idle google scholaring on "fft and butterfly" (restricted to the years 1965-1970) turned up a 1969 Lincoln Laboratory Technical Report (#468), "Quantization Effects in Digital Filters," by C.J. Weinstein, which contains the phrase,

This computation, referred to as a 'butterfly,'...

beside a figure that does indeed look like a plausible geometric sketch of a butterfly.

The report is available at http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0706862 . Portions of it, including the "butterfly" figure, reappear in a joint paper with A.V. Oppenheim, "Effects of Finite Register Length in Digital Filtering and the Fast Fourier Transform," published in 1972 in the Proceedings of the IEEE (vol. 60, no. 8, pp. 957-976, available at http://www.rle.mit.edu/dspg/documents/EffectsFFTComplete.pdf .

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the references. BTW, I have found a paper, What is the Fast Fourier Transform?, Cochran, W. et al, IEEE Trans. on Audio and Electroacoustics, Vol.15, 2, pp. 45-55. 1967 that presents several signal flow graph of DFT computations. The term "butterfly" is not used but the diagrams are identical. $\endgroup$
    – Papiro
    Commented Jun 5, 2012 at 0:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .