Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]
share|improve this question
1  
Have you compared your working definition (normalization and all that) of the FFT with the definition of whatever software you're using? –  J. M. Oct 17 '11 at 10:35
    
Your "FFT on paper" is a bit suspect in that the more common formulation of the discrete Fourier Transform in engineering circles (which MATLAB caters to) gives the values of $f(x)$ at $\exp(-i 2\pi k/N)$ for $0 \leq k < N$. Your evaluation is at $\exp(+i 2\pi k/N)$ and so you get the complex conjugate of what MATLAB is giving you. The inverse discrete Fourier Transform has a factor of $1/N$, but, as J.M. has already noted, the normalization also can be different in different formulations. Maple and Wolfram Alpha probably use $1/\sqrt{N}$ in both directions instead of $1/N$ in one. –  Dilip Sarwate Oct 17 '11 at 11:02
1  
@Dilip: I know for a fact that Mathematica (and thus Wolfram Alpha) does use the $\frac1{\sqrt N}$ normalization; at least for Mathematica, you have the FourierParameters option to tweak if the default convention isn't to your liking... –  J. M. Oct 17 '11 at 11:26
    
The short answer to this question: "FFT implementations vary." –  endolith Oct 17 '11 at 13:22

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
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. –  zsero Oct 17 '11 at 21:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.