0
$\begingroup$

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

enter image description here

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

$\endgroup$
2
  • $\begingroup$ In your above butterfly diagram, shouldn't the indexing of your input sequence be in "bit reversed" order? $\endgroup$ – Richard Lyons Feb 24 at 9:29
  • $\begingroup$ @RichardLyons yes i didn't make the diagram it was from the internet, i have since found a 8 point FFT diagram to refer from which have the correct indices reversed for the first stage. Made it a bit less overwhelming to disset. $\endgroup$ – WDUK Feb 24 at 9:38
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ yeah, that's how I've learned it, too. Nice. $\endgroup$ – Marcus Müller Feb 22 at 13:49
  • $\begingroup$ Nice just computed the needed twiddle factors with this approach, this was so much easier. Now i just need to figure out the math to map index to correct twiddle factor for each stage for the FFT since i now only have an array of twiddles of only length 7. $\endgroup$ – WDUK Feb 22 at 23:29
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ah I see my mistake with the sign in my exponent now. Okay I understand now what k is kinda but I'm not sure I understand the pattern relating each stage to how far k iterates. That being 0 in stage 0 then 0,1 in stage 1 and 0,1,2,3 for stage 2 and so on... That's the only part that kinda remains elusive to my understanding now. $\endgroup$ – WDUK Feb 22 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.