# How do you map indices to twiddle factors in FFT

I am kinda lost on how to map my indices for each stage to my look up array of precomputed twiddle factors.

For an $$N=8$$ point FFT i have $$N/2$$ twiddle factors in total:

$${ [0] = W_8^0, [1] = W_8^1, [2] = W_8^2, [3] = W_8^3 }$$

With this look up table available how do you calculate, which index matches with each other and which twiddle factor index in the array is needed and whether its negative or positive.

I want to be able to recalculate all of this.

For example:

Lets say as a random choice, I'm on the second stage and on index 3. From this map it shows that:

Stage 2 :: Index 3:: $$[1] - W_8^2 * [3]$$

So i need to know that I pair with index 1, the twiddle array index is [2] and that the sign for it is negative since i am on the bottom half of the wing.

The butterfly images that every website shows - seems to gloss right over how you actually calculate the mapping of it all.

Does any one know the math that links it up as you iterate the indices for each stage?

• Perhaps the information at the following web page would be of some interest to you: dsprelated.com/showarticle/107.php – Richard Lyons Feb 23 at 8:30
• I made a comment on the article without realising you wrote the article lol but yeah that article is helpful but not quite what I was asking for 😊 – WDUK Feb 23 at 12:02

Here is C++ code snippet that shows a relatively efficient way of doing it. The idea here is that the step size is always half the previous step and that the index wraps around if it exceeds N/2 which we can implement very efficiently with a bit masking operation (if it's a power of two).

constant int N = 8; // FFT size

// loop over all stages
int stepSize = N;  // initial step size if FFT length
for (int i = 0; i < numStages; i++)
{
int twiddleIndex = 0;
stepSize >>= 1;   // divide by two, it's half of the previous stage
for (int b = 0; b < numButterflies)
{
currentTwiddle = W[twiddleIndex];  // current twiddle factor from table
// update the index: add step size and warp it around if it exceeds N/2
twiddleIndex= (twiddleIndex+ stepSize) & moduloMask ;
}
}

• Although this still does not map each index to a particular twiddle or finds the corresponding index that you sum with so this isn't quite what i need either now that i've tried the code. Say i'm at X(3) stage 2 in the image i posted, i need to calculate from that, the other index i need, the twiddle factor and the sign i need but only from knowing the index X(3) and the stage i'm in. Doesn't seem any one does it this though. – WDUK Feb 23 at 21:03