most recent 30 from http://mathoverflow.net 2013-05-18T23:40:37Z http://mathoverflow.net/feeds/question/98759 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98759/fft-and-butterfly-diagram PaPiro 2012-06-04T10:52:05Z 2012-06-04T19:46:35Z

<p><a href="http://en.wikipedia.org/wiki/Butterfly_diagram" rel="nofollow">Wikipedia</a> 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 ..."</p> <p>The question is: What was the first time that FFT was represented by <em>Butterfly Diagram</em> ? References would be appreciated.</p>

http://mathoverflow.net/questions/98759/fft-and-butterfly-diagram/98804#98804 Barry Cipra 2012-06-04T19:46:35Z 2012-06-04T19:46:35Z

<p>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, </p> <blockquote> <p>This computation, referred to as a 'butterfly,'...</p> </blockquote> <p>beside a figure that does indeed look like a plausible geometric sketch of a butterfly. </p> <p>The report is available at <a href="http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0706862" rel="nofollow">http://www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0706862</a> . 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 <em>Proceedings of the IEEE</em> (vol. 60, no. 8, pp. 957-976, available at <a href="http://www.rle.mit.edu/dspg/documents/EffectsFFTComplete.pdf" rel="nofollow">http://www.rle.mit.edu/dspg/documents/EffectsFFTComplete.pdf</a> .</p>