Fast Fourier Transform

gam3r

gam3r

gam3r

Soldato
Joined
20 Jun 2005
Posts
3,826
Location
London..
I'm having trouble with the whole concept of this. I've read my slides, books and searched the internet but still have no clue how to use it to multiply two polynomials together.

Bit of a long shot i know, but if anyone knows how this all works could you explain to me the multiplication of these two poly's step by step using the FFT?

1+x+2x^2 and
2+3x

Any help appreciated, been trying to make sense of this whole thing for ages now..
 
I wish I could help. I studied this in my 2nd year, and one of our courseworks was to write a tutorial to explain to someone what the Frequency Domain is. It took me a while to get around this concept, but I don't think we had to learn the maths behind it!
 
Ha! I thought I had a good handle on FFTs but didn't realise you could use them in the way you're describing. Reading the bottom of this page (connection to the usual Fourier transform) doesn't shed much light on the issue I must admit, but is the best I could do :o
 
gam3r said:
Well, in answer to dangerstat's q, both are current problems i'm having :(
Click to expand...

Okay well to start with the FT. The idea is best approached (IMO) is from the compression angle. You have some function and you want to reconstruct it using as little information as is possible. So in text say I have

hbob, gbob,fbob,jbob

The common component is bob right? So to compress it replace bob with say

hx,gx,fx,jx

So as long as the follow on process know's that x is bob it can reconstruct that string completely.

The only real difference with the FT is that it's not looking for strings of letters it's looking at sines and cosines and different frequencies. So it's saying, okay in this segment of a signal what frequencies are present? And that's why you get a set of coefficients which represent the contribution to a signal of sine and cosines at different frequencies. Now with almost all signals most of these coefficients are zero, so you actually only need to record very few coefficients to reconstruct the signal.
 
Nope no convolution.

dangerstat: thanks for that explanation, its a bit more clearer now, but how would i go about using that theory with the polynomial multiplication?

here is the "steps" from the book, i don't understand them!

1. Selection:
Pick some points x0; x1; : : : xn-1, where n 2d + 1
2. Evaluation:
Compute A(x0); A(x1); : : : A(xn-1), B(x0); B(x1); : : : B(xn-1)
3. Multiplication:
Compute C(xk) = A(xk)B(xk) for all k = 0; : : : n - 1
4. Interpolation: Recover C(x) = c0 + c1x + : : : + c2dx2d
Click to expand...
 
gam3r said:
here is the "steps" from the book, i don't understand them!
Click to expand...

Isn't that just saying take the FFT of A and B, multiply each of their respective frequency components together to form vector C and then IFFT(C) back out?
 
Last edited:
Are you trying to do it analytically? That's what's confusing me, as it's a doddle to do discretely in an app like matlab.
 
Well after a few months i'm still struggling to understand this!

This is how far i've got..

I've got 2 Polynomials:
3x+2
2x^2 + x + 1

Using coefficient representation:

3x+2 = (2,3,0,0)
2x^2 + x + 1 = (1,1,2,0)

Now i'm stuck. Here is the solution. I don't understand the part where it converts these two things to :

FFT(1, 1, 2, 0) = (4, 11+i, 2,−1−i)
FFT(2, 3, 0, 0) = (5, 2 + 3i,−1, 2 − 3i)

Anyone explain this? I know it's a long shot!

Here is the actual solution:

fft.JPG
 
The fact that its a polynomial basis is a red herring, it doesnt make any difference from polynomial to euclidean or any other basis. The reason that there are 4 coordinates is presumably that without some funny modification you can only FFT a signal size 2^n.
The inversion they have there is I think the iDFT inversion (does the same thing as the iFFT). If its acceptable to calculate that way you could just left multiply your polynomial vectors by the 4x4 DFT matrix.
 
dangerstat said:
Okay well to start with the FT. The idea is best approached (IMO) is from the compression angle. You have some function and you want to reconstruct it using as little information as is possible. So in text say I have

hbob, gbob,fbob,jbob

The common component is bob right? So to compress it replace bob with say

hx,gx,fx,jx

So as long as the follow on process know's that x is bob it can reconstruct that string completely.

The only real difference with the FT is that it's not looking for strings of letters it's looking at sines and cosines and different frequencies. So it's saying, okay in this segment of a signal what frequencies are present? And that's why you get a set of coefficients which represent the contribution to a signal of sine and cosines at different frequencies. Now with almost all signals most of these coefficients are zero, so you actually only need to record very few coefficients to reconstruct the signal.
Click to expand...

A better overview than any of my lecturers ever managed to put across...
 
You must log in or register to reply here.
Back
Top Bottom