Butterfly diagram

A butterfly graph (english butterfly graph ) shows how from the basic function ( the butterfly ) the Fourier transform of a fast Fourier transformer ( FFT, fast Fourier transform ) is established.

The term butterfly is derived from the data flow diagram of the representation of the two triangles that arise in the representation of the basic element (time decimation butterfly) the fast Fourier transform. A butterfly effected (each complex) multiplication, subtraction, and an addition within the FFT algorithm by Cooley and Tukey. By lines, indicating that the two outputs y0, 1 depend on both inputs x0, 1.

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

In the specific case where n = 2p inputs results in a number of graphs with the butterfly of references:

With, the index k and the imaginary unit i