Fast Fourier Transform

The yellow 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.

·

Numbering of Input - Output:

0000 -- 0000
0001 -- 1000
0010 -- 0100
...
1110 -- 0111
1111 -- 1111

·

The image shown above is the first version of the image shown below:


That new version looks nicer, but the old version helps better to understand the numbering scheme.