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

Questions
, ,
1

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

2

??? - But it does result in the original sequence:

ifftfft.png
ifftfft.png569×173 2.05 KB

Regards – Henrik

EDIT: Sorry, I missed that you were talking about WolframAlpha …
[1]: http://community.wolfram.com//c/portal/getImageAttachment?filename=ifftfft.png&userId=32203

3

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!

4

You can use https://www.open.wolframcloud.com

5

Hi Nikolay,

when I do that using Mathematica I get:

fft1234.png

But this result is not unique: See documentation on Fourier, in particular the infos under “Details and Options”, c.f. FourierParameters.

Regards – Henrik

6

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?

whiteboard.jpg
whiteboard.jpg1136×852 65.5 KB

Cheers.

7

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:

fft-Test.png
fft-Test.png837×331 7.13 KB

Regards – Henrik

8

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

9

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}]]

10

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.

11

Thanks so much, Leonardo!

Thanks to Henrik and Sam, also.