Message Boards Message Boards

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

GROUPS:

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

POSTED BY: Nikolay Tsenkov
Answer
3 months ago

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

enter image description here

Regards -- Henrik

EDIT: Sorry, I missed that you were talking about WolframAlpha ...

POSTED BY: Henrik Schachner
Answer
3 months ago

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!

POSTED BY: Nikolay Tsenkov
Answer
3 months ago
POSTED BY: Sam Carrettie
Answer
3 months ago

Hi Nikolay,

when I do that using Mathematica I get:

enter image description here

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

Regards -- Henrik

POSTED BY: Henrik Schachner
Answer
3 months 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?

enter image description here

Cheers.

POSTED BY: Nikolay Tsenkov
Answer
3 months ago

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:

enter image description here

Regards -- Henrik

POSTED BY: Henrik Schachner
Answer
3 months 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

POSTED BY: Nikolay Tsenkov
Answer
3 months ago

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

Answer
3 months ago

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.

Answer
3 months ago

Thanks so much, Leonardo!

Thanks to Henrik and Sam, also.

POSTED BY: Nikolay Tsenkov
Answer
3 months ago

Group Abstract Group Abstract