Fast Fourier Transform

Tokenbrit · 22 Apr 2009 at 16:01

With the correct normalisation the matrix you want to use is I think

Code:

If you make a column vector from your polynomial coefficients and multiply it on the right of that matrix you should get your fourier coefficients.

To be clear

Code:

   1  1  1  1       1       4
   1  i -1 -i   \/  1  =   -1 + i
   1 -1  1 -1   /\  2      2
   1 -i -1  i       0      -1 - i

There seems to be a typo in your solution.

gam3r · 22 Apr 2009 at 16:33

Tokenbrit said:
With the correct normalisation the matrix you want to use is I think

Code:

1 1 1 1 1 i -1 -i 1 -1 1 -1 1 -i -1 i

If you make a column vector from your polynomial coefficients and multiply it on the right of that matrix you should get your fourier coefficients.

To be clear

Code:

1 1 1 1 1 4 1 i -1 -i \/ 1 = -1 + i 1 -1 1 -1 /\ 2 2 1 -i -1 i 0 -1 - i

There seems to be a typo in your solution.

Thanks for your help buddy,
how did you determine the "correct normalisation matrix"?

Tokenbrit · 22 Apr 2009 at 16:51

If you go to the wikipedia page for Discrete Fourier Transform do a page search to the part with the "Vandermonde matrix" and the general form for an NxN matrix is there.
By normalisation I just mean the 1/4 part (1/N). You should beware in your example it seems that in fact the iDFT is used to map into the frequency domain and then the DFT back out. This doesnt make any difference really as it is still an involution but it makes a small contradiction with most of the literature.

gam3r · 22 Apr 2009 at 17:13

I see the vandermonde matrix with all the w's but i'm not sure as to how we got

1 1 1 1
1 i -1 -i
1-1 1 -1
1 -i -1 i

from the nxn vandermonde...

Django x2 · 22 Apr 2009 at 17:24

Jeez! FFT. Never thought I'd have to see or hear that again. If you're still struggling by the weekend I'll provide a solution for you although tokenbrit has it covered by the looks of things.

^^^^^^
Ultimate Cop Out

D.P. · 22 Apr 2009 at 17:35

f(x)*g(x) <==> F(X).F(X)
To efficiently convolve 2 signals.

Tokenbrit · 22 Apr 2009 at 17:36

OK
w = exp(-2*pi*i/N)

In this example N=4 (the number of data).

So
w^0 = exp(-2*pi*i/N)^0 = 1
w^1 = exp(-2*pi*i/N)^1 = exp(-2*pi*i/N) = exp(-i*pi/2) = -i
w^2 = exp(-2*pi*i/N)^2 = exp(-4*pi*i/N) = exp(-i*pi) = -1
w^3 = exp(-2*pi*i/N)^3 = exp(-6*pi*i/N) = exp(-i*3*pi/2) = i

gam3r · 22 Apr 2009 at 18:12

Lol. I'm so confused!

I thought the formula was e^2pi/n ?

aaaaaaaaaaaahhhhhhhhhh