Fast Fourier Transform

The blue boxes do the elementary DFT (Discrete Fourier Transform). They also are called "decimation butterflies" and perform four operations: one complex multiplication, one sign inversion and two complex additions.

Usually the transformer is presented differently. This depiction of course does not change the design, but it shows the construction of the transformer using a fractal approach. In the usual presentations (of Radix-2 FFT algorithms), the butterflies cross the lines; in this presentation, lines cross lines.

The numbering of inputs and outputs is binary.

Why "fractal"?
A 2-port DFT requires one butterfly,
a 4-port DFT requires two 2-port DFTs plus two butterflies,
a 8-port DFT requires two 4-port DFTs plus four butterflies,
a 16-port DFT requires two 8-port DFTs plus eight butterflies,
and so on.

Why "butterfly"?
That is because of the two "triangles" in each box. Zoomorphism works even with engineers, and in this case the pair of triangles look like the wings of a butterfly to them.

First version (2005):