1
$\begingroup$

I am just learning FFTs and I am trying to debug a problem in MATLAB.

I think I don't understand how is MATLAB's FFT function handling the polynomial powers, or I am doing something wrong manually. My problem is that it seems that positions 1 .. n-1 are reversed.

OK, here is a very simple example: p(x) = x and I would like to compute the 4th order FFT

On paper it would be:

w0 = 1; w1 = i; w2 = -1; w3 = -i; p(w0) = 1; p(w1) = i; p(w2) = -1; p(w3) = -i; 

and for me it would mean the following in vector form:

p = [0,1,0,0] fft(p) = [1,i,-1,-i] 

But what happens is this:

fft(p)  ans =     1.0000                  0 - 1.0000i  -1.0000                  0 + 1.0000i 

It means that somehow MATLAB is looking at the roots of unity in a 0,3,2,1 order. Why is this happening or is it me who is doing something wrong?

Update

I'm even more confused now that I tried it in Maple and Wolfram Alpha.

In Maple it returns:

v:=Vector[row]([ 0 , 1 , 0 , 0 ], datatype=complex[8]); FourierTransform(v); Vector[row](4, {(1) = .500000000000000+0.*I, (2) = 0.-.5000000000*I, (3) = -.500000000000000+0.*I, (4) = 0.+.500000000000000*I}) 

In Wolfram Alpha it is:

fft([0,1,0,0]) returns: {0.5, 0.5 i, -0.5, -0.5 i} 

So to sum up, here is how it looks totally different by using 4 different methods:

polynomial: x^2 or [0,1,0,0] FFT on paper: [1, i, -1, -i] in MATLAB: [1, -i, -1, i] in Maple: [0.5, -0.5i, -0.5, 0.5i] in Wolfram Alpha: [0.5, 0.5i, -0.5, -0.5i] 
  • 0
    The short answer to this question: "FFT implementations vary."2011-10-17

1 Answers 1

0

Basically everything has already been said in the comments. There are two aspects of the discrete Fourier transform that require a choice of convention: where to put the minus sign in the exponent and where to put the normalization factor(s). Both can be distributed arbitrarily between the transform and its inverse; that is, the transform can be defined as

$\hat a_k=n_1\sum_{n=0}^{N-1}a_n\mathrm e^{-\sigma2\pi\mathrm i kn/N}$

and its inverse as

$a_n=n_2\sum_{k=0}^{N-1}\hat a_k\mathrm e^{\sigma2\pi\mathrm i kn/N}$

with $\sigma=\pm1$ and $n_1n_2=1/N$. Usual choices are to distribute the normalization symmetrically, that is $n_1=n_2=1/\sqrt N$, or to put it all into one of the transforms so that the other one doesn't require normalization. See also the last few paragraphs in this Wikipedia section for pros and cons of the different conventions.

  • 1
    Thanks for the explanation, now it's more clear. I found out that in Mathematica you can set it to work like in "paper", you have to set FourierParameters to 1, 1.2011-10-17