The "Twiddle Factor"
|
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.
c
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.
|