I was told from another stack exchange (stackoverflow and computer science stack exchange) to post here - so hopefully now i can get some help from people who understand the algorithm, but if this is off topic here then i am kinda running out of places to ask....
I wrote my own FFT algorithm to learn it - but i am getting a different result to what i was expecting (correct numbers but wrong signs), but i cannot figure out why.
I am hoping some one here who has a good understanding on the FFT algorithm can understand what i did wrong, i currently suspect its my twiddle factors - but i am not sure at this point...
Firstly i precompute all the twiddle factors and indices. The twiddles are calculated like this:
for (int stage = 0; stage < _passes; stage++) //log(N)/log(2)
{
for (int i = 0; i < _N; i++) //N = 2^n
{
//wing span, 2^1, 2^2 etc
float span = pow(2, stage+1);
float k = (i * _N / span) % _N;
float a = pi2 * k / _N;
//iFFT uses complex positive coefficients: exp(i*2*pi*k/N)
Vector2 twiddle = new Vector2(cos(a), sin(a));
//FFT uses complex conjugate: exp(-i*2*pi*k/N)
Vector2 twiddleConj = twiddle.ComplexConjugate();
int arrIndex = stage * _N + i;
_twiddlesR[arrIndex] = twiddle; //inverse array
_twiddlesF[arrIndex] = twiddleConj; //forward array
}
}
This was the output for N=4
:
First stage:
[0] + (1+0i)[2]
[2] +(-1+0i)[0]
[1] + (1+0i)[3]
[3] +(-1+0i)[1]
Second stage:
[0] + (1+0i)[2]
[1] + (0-i)[3]
[2] +(-1+0i)[0]
[3] + (0+i)[1]
I ran the FFT with this code:
for (int stage = 0; stage < _passes; stage++)
{
for (int k = 0; k < _N; k++)
{
PerformFft(stage, k);
}
}
My FFT function:
private void PerformFft(int stage, int k)
{
int arrIndex = stage * _N + k;
Vector2[] twiddleArr = _isForward ? _twiddlesF : _twiddlesR;
Vector2Int twiddleIndex = _twiddleIndices[arrIndex];
Vector2 twiddle = twiddleArr[arrIndex];
//ping pong between two read/write arrays by checking if stage is even or odd
Vector2[] writeArr = stage % 2 == 0 ? _complexArr2 :_complexArr1;
Vector2[] readArr = stage % 2 == 0 ? _complexArr1 :_complexArr2;
Vector2 complexA = readArr[twiddleIndex.x];
Vector2 complexB = readArr[twiddleIndex.y];
Vector2 result = complexA + complexB.ComplexMultiply(twiddle);
writeArr[k] = result;
}
For the output i get the correct numbers but i get the wrong signs, here is some data:
Input:
0 + 0i
1 + 0i
2 + 0i
3 + 0i
Forward FFT Output:
6 + 0i
2 - 2i
2 + 0i
2 + 2i
But according to this FFT calculator i am close to the correct answer but the signs are wrong: https://scistatcalc.blogspot.com/2013/12/fft-calculator.html
Can any one see what logic mistake i am doing here? Been stuck on this for a week so far.