| Author |
Message |
Michel Rouzic
Guest
|
 Posted:
Fri Dec 23, 2005 5:16 pm Post subject:
FFT convolution in the polar form |
|
|
I got a simple question about performing a FFT convolution in the polar
form, how do you do it?
I expect it to be something like this :
DC out = DC in * DC k (* meaning multiply)
Mag out = Mag in * Mag k
Phase out = Phase in + Mag k
k being the kernel (no need to explain what in and out stand for i
guess)
I suck too much at maths to make sure it is correct, can anyone out
there tell me if it's correct and if not tell me the proper way to do
it? |
|
| Back to top |
|
 |
Guest
|
| Posted:
Fri Dec 23, 2005 5:16 pm Post subject:
Re: FFT convolution in the polar form |
|
|
Michel Rouzic wrote:
| Quote: | I got a simple question about performing a FFT convolution in the polar
form, how do you do it?
I expect it to be something like this :
DC out = DC in * DC k (* meaning multiply)
Mag out = Mag in * Mag k
Phase out = Phase in + Mag k
|
You probably meant Phase out = Phase in + Phase k. By the way, DC =
Mag[0], no need for seperate variable.
Furthermore, the kernels in the frequency domain (time domain windows)
are real (because the time domain windows are symmetric). If you are
trying to create linear-phase FIR filter coefficients by windowing in
frequency domain (as in your previous posts), the FIR coeffcients in
frequency will also be real, and therefore it is more efficient to
convolve in rectangular coordinates. It also saves you the rect ->
polar transform. |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Sat Dec 24, 2005 12:50 am Post subject:
Re: FFT convolution in the polar form |
|
|
abariska@student.ethz.ch wrote:
| Quote: | Michel Rouzic wrote:
I got a simple question about performing a FFT convolution in the polar
form, how do you do it?
I expect it to be something like this :
DC out = DC in * DC k (* meaning multiply)
Mag out = Mag in * Mag k
Phase out = Phase in + Mag k
You probably meant Phase out = Phase in + Phase k. By the way, DC =
Mag[0], no need for seperate variable.
|
oh yeah that's what i meant
| Quote: | Furthermore, the kernels in the frequency domain (time domain windows)
are real (because the time domain windows are symmetric). If you are
trying to create linear-phase FIR filter coefficients by windowing in
frequency domain (as in your previous posts), the FIR coeffcients in
frequency will also be real, and therefore it is more efficient to
convolve in rectangular coordinates. It also saves you the rect -
polar transform.
|
ok, but you see, i *might* perform this convolution in the polar form
between a kernel i would create (as we talked about in another topic)
and a real-world signal. The plan is to take the real-world signal, FFT
it, turn it to the polar form, and then, convolve it hundreds of times
with different kernels (as you may have guessed, to cut the real-world
signals into frequency bands).
So the rect->polar transform doesn't matter much since it would be
performed only once, so now I got to figure out which is the more
efficient
For a sample of each part
In the polar form : 3 multiplications, 1 addition, 1 cos, 1 sin
In the rectangular form : 4 multiplications, 1 addition, 1 substraction
I'm not really sure which would be the fastest, i'm gonna have to test,
i bet on the rectangular form, but I was wondering for a long time how
to make a convolution in the polar form, and since i might need it
now..
thanks alot for help by the way |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Sat Dec 24, 2005 1:16 am Post subject:
Re: FFT convolution in the polar form |
|
|
Michel Rouzic wrote:
| Quote: | abariska@student.ethz.ch wrote:
Michel Rouzic wrote:
I got a simple question about performing a FFT convolution in the polar
form, how do you do it?
I expect it to be something like this :
DC out = DC in * DC k (* meaning multiply)
Mag out = Mag in * Mag k
Phase out = Phase in + Mag k
You probably meant Phase out = Phase in + Phase k. By the way, DC =
Mag[0], no need for seperate variable.
oh yeah that's what i meant
Furthermore, the kernels in the frequency domain (time domain windows)
are real (because the time domain windows are symmetric). If you are
trying to create linear-phase FIR filter coefficients by windowing in
frequency domain (as in your previous posts), the FIR coeffcients in
frequency will also be real, and therefore it is more efficient to
convolve in rectangular coordinates. It also saves you the rect -
polar transform.
ok, but you see, i *might* perform this convolution in the polar form
between a kernel i would create (as we talked about in another topic)
and a real-world signal. The plan is to take the real-world signal, FFT
it, turn it to the polar form, and then, convolve it hundreds of times
with different kernels (as you may have guessed, to cut the real-world
signals into frequency bands).
So the rect->polar transform doesn't matter much since it would be
performed only once, so now I got to figure out which is the more
efficient
For a sample of each part
In the polar form : 3 multiplications, 1 addition, 1 cos, 1 sin
In the rectangular form : 4 multiplications, 1 addition, 1 substraction
|
OK, I did the test. The polar form thing is about 8 times slower than
the rectangular form. Now I only gotta figure out how I'm gonna make my
kernels directly in the rectangular form. You were talking about stuff
being real only, does it mean that in order to make my FIR kernels,
i'll only need to do the same as i did, reverse every two sample, put
it in the real part and leave the imaginary part at 0? |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Dec 24, 2005 1:16 am Post subject:
Re: FFT convolution in the polar form |
|
|
Michel Rouzic wrote:
| Quote: | OK, I did the test. The polar form thing is about 8 times slower than
the rectangular form. Now I only gotta figure out how I'm gonna make my
kernels directly in the rectangular form.
|
That's easy. As the windows are time-domain symmetric, their DFT
kernels are real (remember the von Hann kernel: [1/2 1/4 0 ... 0 1/4],
no imaginary parts).
| Quote: | You were talking about stuff
being real only, does it mean that in order to make my FIR kernels,
i'll only need to do the same as i did, reverse every two sample, put
it in the real part and leave the imaginary part at 0?
|
Yes. The window kernel is real, the unwindowed FIR filter frequency
response is real, just use ordinary (real) convolution, then invert the
sign of every second coefficient for a linear-phase FIR. |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Sat Dec 24, 2005 5:16 pm Post subject:
Re: FFT convolution in the polar form |
|
|
abariska@student.ethz.ch wrote:
| Quote: | Michel Rouzic wrote:
OK, I did the test. The polar form thing is about 8 times slower than
the rectangular form. Now I only gotta figure out how I'm gonna make my
kernels directly in the rectangular form.
That's easy. As the windows are time-domain symmetric, their DFT
kernels are real (remember the von Hann kernel: [1/2 1/4 0 ... 0 1/4],
no imaginary parts).
You were talking about stuff
being real only, does it mean that in order to make my FIR kernels,
i'll only need to do the same as i did, reverse every two sample, put
it in the real part and leave the imaginary part at 0?
Yes. The window kernel is real, the unwindowed FIR filter frequency
response is real, just use ordinary (real) convolution, then invert the
sign of every second coefficient for a linear-phase FIR.
|
Ok, works very fine, thanks alot for help |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in