Understanding the twiddle factors

Question

So I've been looking at this butterfly diagram to try to understand it better:

And I am trying to get a good understanding of the twiddle factors.

The definition is given as:

FFT Twiddle Factor: ${e^{i2{\pi}k/N}}$ and IFFT Twiddle Factor: ${e^{-i2{\pi}k/N}}$

So k is the index number of the iteration thus $k=0,1...N$ but its $N$ that I am unsure of.

From the image is the first stage N = 8 (since there are 8 butterflies) or is N = 2 since each butterfly only spans two elements? Or is N always 16 every pass?

My guess currently is:

Stage 0 : N = 8
Stage 1 : N = 4
Stage 2 : N = 2
Stage 3 : N = 1

Am i correct in this assumption? If not i hope some one clarifying my misunderstanding here.

Thanks

Answer 1

I think there is a better way of writing the twiddle factor. Instead of using a different "basis" for each stage, you can use the FFT length as the base for all twiddle factors and the only thing that changes between stages is the step size.

Stage 0: $W_{16}^0$
Stage 1: $W_{16}^0, W_{16}^4 $
Stage 2: $W_{16}^0, W_{16}^2,W_{16}^4, W_{16}^6 $
Stage 3: $W_{16}^0, W_{16}^1, .... W_{16}^7 $

We are using the property here that for example $W_2^1 = W_4^2 = W_8^4 = W_{16}^8$ or more general $$W_a^b = W_{n \cdot a}^{n \cdot b}, n \in \mathbb{N}$$

Once you decide to using the FFT length as the basis for the twiddle factors you can just drop the $16$ from the notations and things become a lot easier to read and understand. Here is the complete list.

Stage 0: $W^0,W^0,W^0,W^0,W^0,W^0,W^0,W^0$
Stage 1: $W^0, W^4,W^0, W^4,W^0, W^4,W^0, W^4 $
Stage 2: $W^0, W^2,W^4, W^6, W^0, W^2,W^4, W^6 $
Stage 3: $W^0, W^1,W^2,W^3,W^4,W^5,W^6, W^7 $

That's actually how most code is implemented. You don't build a twiddle factor table for each stage, you just build one for the highest order and each stage uses a different step size (modulo N/2) to step through the table.

Answer 2

You got it mostly backwards, but otherwise OK :) This can be pretty directly answered by writing down what the Cooley-Tukey FFT's twiddle factor $W_N$ is:

$$W_N=e^{-i\frac{2\pi}{N}}$$

and that's it. For example, in your picture, in Stage 0, you're multiplying with $W_2^0=\left(e^{-i\frac{2\pi}{N}}\right)^0=e^{-i\frac{2\pi0}{N}}=e^0=1$.

So k is the index number of the iteration

No, $k$ is the exponent of your twiddle factors. It goes from 0 to half the size of your transform (in each stage).

From the image is the first stage N = 8 (since there are 8 butterflies) or is N = 2

Stage 0 has subtransforms of size N=2, as you can see. (Also, just write down the 2-DFT's formula and compare.)