FFT algorithm gives wrong signs on my output numbers

Question

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.

Answer 1

Reversing the order of the input sequence would provide the same result as what the OP achieved, but not to say this is exactly why it is occurring here. Below shows the details of the DIT algorithm after each stage; comparing each element step by step with the code should reveal the actual error.

Interpreting the OP's results (I assume [x] represents the index) reveals the error is in the core 2 pt DFT butterfly operation.

While the 2 pt DFT is given as

$Y[0] = X[0] + X[1]$
$Y[1] = X[0] - X[1]$

While the OP is doing the following:

$Y[0] = X[0] + X[1]$
$Y[1] = X[1] - X[0]$

With $X[0]$ and $X[1]$ as the 2-Pt DFT input and $Y[0]$ and $Y[1]$ As the 2-Pt DFT output.

  First stage:
  [0] + (1+0i)[2]   = 0+2
  [2] +(-1+0i)[0]   = 2-0   (should be 0-2= -2!)
  [1] + (1+0i)[3]   = 1+3
  [3] +(-1+0i)[1]   = 3-1  (should be 1 -3= -2!)
  Second stage:
  [0] + (1+0i)[2]       
  [1] +  (0-i)[3]
  [2] +(-1+0i)[0]
  [3] +  (0+i)[1]