# Get the original sequence in W|A with "inverse fft of fft of {0,1,2,3}"?

GROUPS:
 Nikolay Tsenkov 1 Vote Hi,I was verifying some manual calculations (I made on a white board) of a 4-point DFT done by the recursive Decimation in Time FFT, when I noticed that 2 of my frequency-domain points are switched - while I get {X1, X2, X3, X4}, the output of Wolfram Alpha is {X1, X4, X3, X1}.I thought I made a mistake, but I checked it a couple of times and I don't think I have. So naturally I thought of getting the inverse transform, and if it doesn't produce the original sequence, then the problem would likely be in WA.Why doesn't "inverse fft of fft of {0,1,2,3}" produce the original secuence? (3 and 1 are also switched after the inverse transform)Thanks.Cheers, Nikolay
1 year ago
10 Replies
 Henrik Schachner 1 Vote ??? - But it does result in the original sequence:Regards -- HenrikEDIT: Sorry, I missed that you were talking about WolframAlpha ...
1 year ago
 Nikolay Tsenkov 1 Vote Hi Henrik,You're probably using Mathematica for this. Would you care to post what does it output for just the forward transform of {0,1,2,3}?Cheers!
1 year ago
 Sam Carrettie 1 Vote You can use https://www.open.wolframcloud.com
1 year ago
 Henrik Schachner 1 Vote Hi Nikolay,when I do that using Mathematica I get:But this result is not unique: See documentation on Fourier, in particular the infos under "Details and Options", c.f. FourierParameters.Regards -- Henrik
1 year ago
 Hi Henrik,Thanks. Yep, there is the issue - aside from not performing any scaling on my result, I get the same thing, but the 2nd and the last element are switched. What am I doing wrong in this DIT FFT butterfly?Cheers.
1 year ago
 Henrik Schachner 1 Vote Hi Nikolay,sorry, I have no idea what is going wrong. But I have written a minimal recursive fft implementation - i guess this is what you are having in mind with your sketch?!? (just for demonstration purposes, functions can digest only lists of length 2^n, not optimized in any way!). But maybe this is helpful though: ClearAll["Global*"] fourier[fl_List] := Module[{length, eleOdd, eleEven, fouOdd, fouEven, phase}, If[(length = Length[fl]) == 1, Return[Sow@fl]]; {eleOdd, eleEven} = Transpose[Partition[fl, 2]]; fouOdd = fourier[eleOdd]; fouOdd = Flatten[{fouOdd, fouOdd}]; fouEven = fourier[eleEven]; fouEven = Flatten[{fouEven, fouEven}]; phase = Table[Exp[-(2 Pi I) n/length], {n, 0, length - 1}]; Sow[fouOdd + fouEven phase] ] invfourier[fl_List] := Module[{length, eleOdd, eleEven, fouOdd, fouEven, phase}, If[(length = Length[fl]) == 1, Return[Sow@fl]]; {eleOdd, eleEven} = Transpose[Partition[fl, 2]]; fouOdd = invfourier[eleOdd]; fouOdd = Flatten[{fouOdd, fouOdd}]; fouEven = invfourier[eleEven]; fouEven = Flatten[{fouEven, fouEven}]; phase = Table[Exp[(2 Pi I) n/length], {n, 0, length - 1}]; Sow[(fouOdd + fouEven phase)/2] ] and then:Regards -- Henrik
1 year ago
 Hey Henrik,I apologise for the late response.Thanks! Just tried your forward transform code in Wolfram Open Cloud and it produces the same result as I do, when doing the manual calculation. I hope someone from Wolfram can comment on this... I suppose if the inverse transform algorithm expects the order, it's not a problem, but it is an issue if you want to know which part of the spectra is which, when you are inspecting and manipulating the DFT... Why does the default Fourier function produces the values in a different order?In any case - thanks so much for your help.Regards,Nikolay
 Leonardo Laguna Ruiz 1 Vote Seems like WA is interpreting incorrectly your input "inverse fft of fft of {0,1,2,3}".Wofram Alpha interprets it as: Fourier[{Fourier[{0,1,2,3}]}]^-1.You can get this input by doing in Mathematica == inverse fft of fft of {0,1,2,3}.which is different from InverseFourier[Fourier[{0, 1, 2, 3}]]
 Leonardo Laguna Ruiz 2 Votes Seems like the result you are getting corresponds to: Fourier[{0, 1, 2, 3}, FourierParameters -> {1, -1}], this produces the result {6. + 0. I, -2. + 2. I, -2. + 0. I, -2. - 2. I}` which is the one you have in your whiteboard.