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?

DIT FFT butterfly flow diagram


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:

equation form of the algorithm without a diagram

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$$


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]
  • 1
    $\begingroup$ I did resolve it. As much as I remember I used the algorithm correctly and there was a setting in Mathematica on how you want the output. When using the correct setting you'd get the same result as on the whiteboard but that wasn't the default one in Mathematica (Wolfram Cloud or whatever it's called) or SageMath. I don't think I went back to SageMath after that to resolve the correct API there, though... Sorry I should've updated this, but was in a hurry...:( $\endgroup$ – Nikolay Tsenkov Dec 21 '17 at 18:14

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.