What is the correct order of DFT values when executing the DIT FFT algorithm?

Question

I was checking the correctness through SageMath (and later through Wolfram Alpha and Mathematica) of some simple whiteboard computations that I've done manually (namely, I have tried to compute the DFT of the simple sequence {0, 1, 2, 3} by using the recursive Decimation-in-time FFT algorithm) and I noticed I'm getting the same values, except 2nd and 4th are switched. What I get is this: {6, -2 + 2i, -2, -2 - 2i} while SageMath's result is: {6, -2 - 2i, -2, -2 + 2i}

What am I doing wrong here?

Update:

I don't think I am doing anything wrong. Here is the solution without the flow diagram, just using the equations for DIT FFT - I get the same result:

And G and H are following from this:

$$X[k] = \sum_{r=0}^{\frac{N}{2}-1} x[2r]*W_{\frac{N}{2}}^{r*k} + W_N^k*\sum_{r=0}^{\frac{N}{2}-1} x[2r+1]*W_{\frac{N}{2}}^{r*k}$$

$$X[k] = G[k] + W_N^k*H[k]$$ $$X[k + \frac{N}{2}] = G[k] - W_N^k*H[k]$$ where $$k=0,1,...,\frac{N}{2}-1$$

Answer 1

Did you end up resolving this? I'm not familiar with the DIT algorithm. Also, providing the code you use will help in debugging this (if still necessary). This is the only one I'm familiar with (see e.g. this blog post by one of the authors), and it's giving the answer on your whiteboard.

sage: IndexedSequence([0,1,2,3],list(range(4)))

Indexed sequence: [0, 1, 2, 3]
    indexed by [0, 1, 2, 3]
sage: _.fft()

Indexed sequence: [6.00000000000000, -2.00000000000000 + 2.00000000000000*I, -2.00000000000000, -2.00000000000000 - 2.00000000000000*I]
    indexed by [0, 1, 2, 3]