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.

$\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$ 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
    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$ 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
    Jun 4, 2012 at 17:50
  • $\begingroup$ quoth the FAQ: "research level math questions" Doesn't this belong on math.SE? $\endgroup$ Jun 4, 2012 at 20:13

1 Answer 1

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 .

$\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
    Jun 5, 2012 at 0:26

Your Answer

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

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