Prev: Multipath channel and downsampling
Next: Mixing different length FFTs
From: onkars on 29 Jun 2010 18:22
Hi,

I am looking for an FFT algorithm that can give me a 4096 pt. FFT using two
64 pt. FFTs. Is it the mixed radix FFT?

Thank you.
From: Jerry Avins on 29 Jun 2010 18:37
On 6/29/2010 6:22 PM, onkars wrote:
> Hi,
>
> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using two
> 64 pt. FFTs. Is it the mixed radix FFT?
>
> Thank you.

I'd like to have a bank account That gives me a $4096 balance for two
$64 deposits.

Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
From: onkars on 29 Jun 2010 19:28
>On 6/29/2010 6:22 PM, onkars wrote:
>> Hi,
>>
>> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using
two
>> 64 pt. FFTs. Is it the mixed radix FFT?
>>
>> Thank you.
>
>I'd like to have a bank account That gives me a $4096 balance for two
>$64 deposits.
>
>Jerry
>--
>Engineering is the art of making what you want from things you can get.
>�����������������������������������������������������������������������
>

What i mean "using two 64 pt FFTs" is that there is some reordering and
twiddle multiplications between the 2 64 pt FFTs. And of course the whole
4096 pt. FFT will take many cycles.
I guess this can be achieved using the mixed-radix -- i.e. 4096 = 64 x 64.
Hence the 1st 64 point FFT will perform 64 number of 64 pt FFTs followed by
some reordering and twiddle factor mults (which I intend to learn about)
and then finally again 64 number of 64 pt FFTs using the 2nd 64 pt. FFT.

Is this the mixed-radix? also where can I read the theory about this mixed
radix ffts -- which will enable me to implement any N (N=P*Q) pt. FFt using
P pt and Q pt FFT engines.

Thank you.
From: Jerry Avins on 29 Jun 2010 22:12
On 6/29/2010 7:28 PM, onkars wrote:
>> On 6/29/2010 6:22 PM, onkars wrote:
>>> Hi,
>>>
>>> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using
> two
>>> 64 pt. FFTs. Is it the mixed radix FFT?
>>>
>>> Thank you.
>>
>> I'd like to have a bank account That gives me a $4096 balance for two
>> $64 deposits.
>>
>> Jerry
>> --
>> Engineering is the art of making what you want from things you can get.
>>
>
> What i mean "using two 64 pt FFTs" is that there is some reordering and
> twiddle multiplications between the 2 64 pt FFTs. And of course the whole
> 4096 pt. FFT will take many cycles.
> I guess this can be achieved using the mixed-radix -- i.e. 4096 = 64 x 64.
> Hence the 1st 64 point FFT will perform 64 number of 64 pt FFTs followed by
> some reordering and twiddle factor mults (which I intend to learn about)
> and then finally again 64 number of 64 pt FFTs using the 2nd 64 pt. FFT.
>
> Is this the mixed-radix? also where can I read the theory about this mixed
> radix ffts -- which will enable me to implement any N (N=P*Q) pt. FFt using
> P pt and Q pt FFT engines.

Perhaps there is enlightenment here:
www.vassilios-chouliaras.com/pubs/c39.pdf

Jerry
--
Engineering is the art of making what you want from things you can get.
From: dvsarwate on 29 Jun 2010 22:21
On Jun 29, 6:28 pm, "onkars" <onkar.sarode(a)n_o_s_p_a_m.gmail.com>
wrote:
> >On 6/29/2010 6:22 PM, onkars wrote:
> >> Hi,
>
> >> I am looking for an FFT algorithm that can give me a 4096 pt. FFT using
> two
> >> 64 pt. FFTs. Is it the mixed radix FFT?
>
> >> Thank you.
>
> >I'd like to have a bank account That gives me a $4096 balance for two
> >$64 deposits.
>
> >Jerry
> >--
> >Engineering is the art of making what you want from things you can get.
> >
>
> What i mean "using two 64 pt FFTs" is that there is some reordering and
> twiddle multiplications between the 2 64 pt FFTs. And of course the whole
> 4096 pt. FFT will take many cycles.

The theory says that a 4096 FFT can be done using 4096x12
multiplications.
Some savings can be achieved by careful coding, but N log_2 N is a
useful
rule of thumb.

> I guess this can be achieved using the mixed-radix -- i.e. 4096 = 64 x 64.
> Hence the 1st 64 point FFT will perform 64 number of 64 pt FFTs followed by
> some reordering and twiddle factor mults (which I intend to learn about)
> and then finally again 64 number of 64 pt FFTs using the 2nd 64 pt. FFT.

If you do 64 64-point FFTs, that is 64x64x6 = 4096x6
muiltiplications.The
next set of 64 64-point FFTs also takes 4096x6 multiplications. So,
we are
up to 4096x12 muiltipications already. Taking into account the re-
ordering
and the twiddle factors that you refer to, your proposed approach may
not
provide a significant gain. Plus, the programming is that much more
complicated, but YMMV.

--Dilip Sarwate

 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Multipath channel and downsampling
Next: Mixing different length FFTs