FPGA Central

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?

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.

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.

[email protected] 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

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

Michel Rouzic wrote:
> [email protected] 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?

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.

[email protected] wrote:
> 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