Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Patricia Hersh Jun 4 '12 at 12:18
    
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. –  cardinal Jun 4 '12 at 15:07
1  
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. –  Patricia Hersh Jun 4 '12 at 15:35
    
@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...". –  Papiro Jun 4 '12 at 17:50
    
quoth the FAQ: "research level math questions" Doesn't this belong on math.SE? –  Peter McNamara Jun 4 '12 at 20:13

1 Answer 1

up vote 3 down vote accepted

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 .

share|improve this answer
    
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. –  Papiro Jun 5 '12 at 0:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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