A DFT is a "Discrete Fourier Transform". An FFT is a "Fast Fourier Transform". An FFT is a DFT, but is much faster for calculations. The whole point of the FFT is speed in calculating a DFT.

The "Twiddle Factor"

<< Previous Next >>

The twiddle factor, W, describes a "rotating vector", which rotates in increments according to the number of samples, N. Here are graphs where N = 2, 4 and 8 samples.

cTwiddle Factor Graphed

The Redundancy and Symmetry of the "Twiddle Factor"

As shown in the diagram above, the twiddle factor has redundancy in values as the vector rotates around. For example W for N=2, is the same for n = 0, 2, 4, 6, etc. And W for N=8 is the same for n = 3, 11, 19, 27, etc.

Also, the symmetry is the fact that values that are 180 degrees out of phase are the negative of each other. So for example, W for N =4 samples, where n = 0,4,8, etc, are the negative of n = 2,6,10, etc.

The Butterfly diagram takes advantage of this redundancy and symmetry, which is part of what makes the FFT possible.

<< Previous Next >>