Hi guys, i just don't understand how to perform a FFT on two polynomials such as X^2+1 and X+1...can anyone step by step go through the process with me?
Thanks very much
+2
A:
Just use your polynomial coefficients as input for fft:
octave:16> poly1=[1 0 1 0]
poly1 =
1 0 1 0
Note: this means x^2+1
octave:17> poly2=[1 1 0 0]
poly2 =
1 1 0 0
octave:18> ifft( fft(poly1).*fft(poly2))
ans =
1 1 1 1
This is the result. Interpret as x^3+x^2+x+1, which is the product of the two polynomials.
jpalecek
2009-04-22 12:16:04
hi thanks for your reply, but im probably being very stupid but how do you get 1 0 1 0 as the coefficients of x^2 + 1?and is this the same way as using a matrix to do it?thanks
KP65
2009-04-22 12:25:20
The first place is coefficient for x^0, second for x^1, and so on. I'm not sure what you mean by "using matrix to do it".
jpalecek
2009-04-22 13:49:46
oh right yes sorry i figured that out.i understand what you did until you did fft(poly1) * fft(poly2), but how do you finid the values of 1 1 1 1?
KP65
2009-04-22 14:36:01
The result is the result of the ifft function, which is the inverse Fourier transform. ".*" is elementwise multiplication, fft is Fourier transform. Does this help or did you want to know how to do the actual Fourier transform when you have vectors?
jpalecek
2009-04-22 17:31:35
if you could show me it with the vectors it would be exteremly helpful and i would be very greatful! i have the solution in front of me but i can't understand it for the life of me!thanks
KP65
2009-04-22 18:07:02
A:
But really what is going on here is convolution.
ifft( fft(poly1).*fft(poly2))
is the equivalent of convolution (properly padded). And convolution can be interpreted as the multiplication of two polynomials. Go look up the definition of convolution (it's very simple) and work it out by hand on paper. I expect that it will shed a lot of light on this for you...
Paul
CenterSpace Software
Paul
2009-10-27 06:41:31