Butterfly graph

Data flow diagram from the two inputs x _0.1 to the two outputs y _0.1 , which corresponds to the contour of a butterfly

A butterfly diagram (English butterfly graph shows), such as from the basic function (the butterfly ) of the Fourier transformation , a Fast Fourier Transformer (FFT, fast Fourier transform ) is established.

The term butterfly is derived in the data flow diagram from the representation of the two triangles that arise when the basic element ( time decimation butterfly ) of the fast Fourier transform is represented. A butterfly accomplishes (each complex) a multiplication, a subtraction and an addition within the framework of the FFT algorithm by Cooley and Tukey. By lines, indicating that the two outputs y _0.1 of the two inputs x _0.1 dependent.

In the simplest case (radix-2 Cooley and Tukey FFT algorithm) the butterfly graph only consists of the two inputs and outputs shown:

${\displaystyle y_{0}=x_{0}+x_{1}}$

${\displaystyle y_{1}=x_{0}-x_{1}}$

In the general case with n = 2 ^p inputs this results in a number of butterfly graphs with the references: ${\displaystyle O(n\log n)}$

${\displaystyle y_{0}=x_{0}+x_{1}\omega ^{k}}$

${\displaystyle y_{1}=x_{0}-x_{1}\omega ^{k}}$

with , the index k and the imaginary unit i. ${\displaystyle \omega =\exp \left(-{\frac {2\pi i}{n}}\right)}$

literature

• Alan V. Oppenheim, Ronald W. Schafer: Discrete-time signal processing . 3. Edition. R. Oldenbourg, 1999, ISBN 3-486-24145-1 .
• Steven W. Smith: The Scientist and Engineer's Guide to Digital Signal Processing . 1st edition. Elsevier Ltd, Oxford, 2002, ISBN 978-0-7506-7444-7 , chap. 18 (English, dspguide.com ).