Götz Kluge's photos with the keyword: Fast Fourier Transform

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.

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):