FFT in polar coordinates

Hello everyone,
I am trying to find an FFT algorithm for polar coordinates. Actually i
have the complex input in trigonometric form and i need an efficient
algorithm for the coputation of FFT on this input vector. Is there such an
efficient algorithm or the best way is to do the polar-cartezian conversion
at the input and again at the output. I am trying to implement this in
hardware on an FPGA.
Thx a lot

vali_alex skrev:
> Hello everyone,
> I am trying to find an FFT algorithm for polar coordinates. Actually i
> have the complex input in trigonometric form and i need an efficient
> algorithm for the coputation of FFT on this input vector. Is there such an
> efficient algorithm or the best way is to do the polar-cartezian conversion
> at the input and again at the output. I am trying to implement this in
> hardware on an FPGA.

I am not sure I understand. Do you consider representing the complex
numbers as magnitude and phase, instead of real and imaginary parts?

If so, I think you ought to check the FLOP counts for the two forms.
While a multiplication of two complex numbers on polar form amounts to
one multiplication (magnitude) and one sum (phase), it might become
a bit more cumbersome to implement the sum of two complex numbers
on polar form.

I haven't seen any recipes involving complex numbers on polar form,
which might be an indication of the relative computational cost.

Rune

vali_alex wrote:
> Hello everyone,
> I am trying to find an FFT algorithm for polar coordinates. Actually i
> have the complex input in trigonometric form and i need an efficient
> algorithm for the coputation of FFT on this input vector. Is there such an
> efficient algorithm or the best way is to do the polar-cartezian conversion
> at the input and again at the output. I am trying to implement this in
> hardware on an FPGA.
> Thx a lot

Well it seems that you're looking for an implementation of FFT that
uses directly the polar form instead of the rectangular form. I'm
afraid that this can't be done directly. In order to get to the polar
form, you need to do your FFT, and then turn it to polar form, and then
before performing an IFFT you obviously have to turn back to
rectangular form.

I have only tried it on a PC, but I made sure that a FFT convolution in
the rectangular form was much faster than in the polar form, I think
the reason form that is that in order to make the rectangular-polar
conversion you have to use arc tan, sin and cos

I think that if you're looking for optimizing your algorithm, you'll
have to stick to the rectangular form, I don't think there's any case
you can find in which doing your operations in the polar form would be
faster than in the rectangular form. Maybe it would help if you could
give precisions about what you need to use polar form for

(disclaimer : I'm very far from being as experienced as the other
people who might talk to you here)

"vali_alex" <valentin@riec.tohoku.ac.jp> wrote in message 
news:yKqdnbCwpPBH16fZnZ2dneKdnZydnZ2d@giganews.com...
> Hello everyone,
> I am trying to find an FFT algorithm for polar coordinates. Actually i
> have the complex input in trigonometric form and i need an efficient
> algorithm for the coputation of FFT on this input vector. Is there such an
> efficient algorithm or the best way is to do the polar-cartezian 
> conversion
> at the input and again at the output. I am trying to implement this in
> hardware on an FPGA.
> Thx a lot

It makes one curious what the data represents / where did you get it in 
polar form?

Maybe knowing more about the data and your objectives would help you get 
better answers.

Otherwise, you've already received some good answers re: the FFT.

Fred 

>
>"vali_alex" <valentin@riec.tohoku.ac.jp> wrote in message 
>news:yKqdnbCwpPBH16fZnZ2dneKdnZydnZ2d@giganews.com...
>> Hello everyone,
>> I am trying to find an FFT algorithm for polar coordinates. Actually i
>> have the complex input in trigonometric form and i need an efficient
>> algorithm for the coputation of FFT on this input vector. Is there such
an
>> efficient algorithm or the best way is to do the polar-cartezian 
>> conversion
>> at the input and again at the output. I am trying to implement this in
>> hardware on an FPGA.
>> Thx a lot
>
>It makes one curious what the data represents / where did you get it in 
>polar form?
>
>Maybe knowing more about the data and your objectives would help you get

>better answers.
>
>Otherwise, you've already received some good answers re: the FFT.
>
>Fred 
Thx for the answers.
I am designing a communication system and the rest of the processing
(besides FFT/IFFT) is a lot easier to implement in polar coordinates and
the input data is in polar coordinates already. i have looked for in
several books and on the net but i couldn't find any algorithm for
performing FFT directly in polar coordinates rather than the cartezian
one.
The idea is that i have the input in the FFT in polar and i need the
output in polar also.Can i get away without making the polar-cartezian
conversion twice?
thx

No. FFT algorithms need to perform additions on all the data, and this
means converting to cartesian form.

Whatever you think the advantages of the polar form are, they will
almost certainly be outweighed by the cost of the conversions.  Do
yourself a favor and stick with the cartesian form.

vali_alex skrev:
> >
> >"vali_alex" <valentin@riec.tohoku.ac.jp> wrote in message
> >news:yKqdnbCwpPBH16fZnZ2dneKdnZydnZ2d@giganews.com...
> >> Hello everyone,
> >> I am trying to find an FFT algorithm for polar coordinates. Actually i
> >> have the complex input in trigonometric form and i need an efficient
> >> algorithm for the coputation of FFT on this input vector. Is there such
> an
> >> efficient algorithm or the best way is to do the polar-cartezian
> >> conversion
> >> at the input and again at the output. I am trying to implement this in
> >> hardware on an FPGA.
> >> Thx a lot
> >
> >It makes one curious what the data represents / where did you get it in
> >polar form?
> >
> >Maybe knowing more about the data and your objectives would help you get
>
> >better answers.
> >
> >Otherwise, you've already received some good answers re: the FFT.
> >
> >Fred
> Thx for the answers.
> I am designing a communication system and the rest of the processing
> (besides FFT/IFFT) is a lot easier to implement in polar coordinates and
> the input data is in polar coordinates already. i have looked for in
> several books and on the net but i couldn't find any algorithm for
> performing FFT directly in polar coordinates rather than the cartezian
> one.
> The idea is that i have the input in the FFT in polar and i need the
> output in polar also.Can i get away without making the polar-cartezian
> conversion twice?


The polar format is useful for presenting the data to a human user,
since people tend to see the information contained in magnitudes
and phases more easily than in real and imaginary parts.

Stick with the carthesian format for computational work, and convert
to polar only when you need to display the result in a graph. 

Rune

In article <DfidneTHwexeoabZnZ2dnUVZ_tCdnZ2d@giganews.com>,
 "vali_alex" <valentin@riec.tohoku.ac.jp> wrote:

> >
> >"vali_alex" <valentin@riec.tohoku.ac.jp> wrote in message 
> >news:yKqdnbCwpPBH16fZnZ2dneKdnZydnZ2d@giganews.com...
> >> Hello everyone,
> >> I am trying to find an FFT algorithm for polar coordinates. Actually i
> >> have the complex input in trigonometric form and i need an efficient
> >> algorithm for the coputation of FFT on this input vector. Is there such
> an
> >> efficient algorithm or the best way is to do the polar-cartezian 
> >> conversion
> >> at the input and again at the output. I am trying to implement this in
> >> hardware on an FPGA.
> >> Thx a lot
> >
> >It makes one curious what the data represents / where did you get it in 
> >polar form?
> >
> >Maybe knowing more about the data and your objectives would help you get
> 
> >better answers.
> >
> >Otherwise, you've already received some good answers re: the FFT.
> >
> >Fred 
> Thx for the answers.
> I am designing a communication system and the rest of the processing
> (besides FFT/IFFT) is a lot easier to implement in polar coordinates and
> the input data is in polar coordinates already. i have looked for in
> several books and on the net but i couldn't find any algorithm for
> performing FFT directly in polar coordinates rather than the cartezian
> one.
> The idea is that i have the input in the FFT in polar and i need the
> output in polar also.Can i get away without making the polar-cartezian
> conversion twice?
> thx

Try googling: polar FFT.  Look at the papers by Donoho, Elad, etc..

"vali_alex" <valentin@riec.tohoku.ac.jp> wrote in message 
news:DfidneTHwexeoabZnZ2dnUVZ_tCdnZ2d@giganews.com...
> >
>>"vali_alex" <valentin@riec.tohoku.ac.jp> wrote in message
>>news:yKqdnbCwpPBH16fZnZ2dneKdnZydnZ2d@giganews.com...
>>> Hello everyone,
>>> I am trying to find an FFT algorithm for polar coordinates. Actually i
>>> have the complex input in trigonometric form and i need an efficient
>>> algorithm for the coputation of FFT on this input vector. Is there such
> an
>>> efficient algorithm or the best way is to do the polar-cartezian
>>> conversion
>>> at the input and again at the output. I am trying to implement this in
>>> hardware on an FPGA.
>>> Thx a lot
>>
>>It makes one curious what the data represents / where did you get it in
>>polar form?
>>
>>Maybe knowing more about the data and your objectives would help you get
>
>>better answers.
>>
>>Otherwise, you've already received some good answers re: the FFT.
>>
>>Fred

> Thx for the answers.
> I am designing a communication system and .....................
> the input data is in polar coordinates already.

That's where you lose me.  How did it (or what?) get to be in polar 
coordinates?  If we know the it/what then maybe we can be of greater help.

Fred 

Fred Marshall wrote:

   ...

> That's where you lose me.  How did it (or what?) get to be in polar 
> coordinates?  If we know the it/what then maybe we can be of greater help.

There may be some confusion here. I've seen the trigonometric form 
referred to (erroneously, I believe) as polar when contrasted with the 
(now more common) exponential form. That needs to be cleared up.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������