Prev: Multipath channel and downsampling
Next: Mixing different length FFTs
From: kevin on 30 Jun 2010 02:48
On 6/29/2010 6:22 PM, onkars wrote:
> 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?
.... plus second post of 7:28 PM

4096=64x64 is not mixed radix. It's 2 stages of radix 64 butterflies,
so it's radix 64. Mixed radix would be 4096 = 128x32, or 32x128, or
256x16, or 16x256, or ... (it's a long list).

Based on some of your previous posts, I presume that you're looking to
do this in hardware. In that case, a 64x64 isn't a bad choice (there
are better ones), because you can break the 64x64 down into a 4 stage
pipeline of 8x8x8x8. Radix 8 is quite efficient in that you only have
a couple of 'difficult' internal twiddles of the +/-.707.... type, and
they can be done efficiently with a special purpose multiplier. So
you'd have 4 radix 8 butterfly stages (each with a special purpose +/-.
707... multiplier), plus 3 full scale multipliers for the inter-stage
twiddles.

There are a lot of additional concepts that could be applied, but I'm
not really sure exactly what you're trying to do, so I won't get into
them.

To get an idea of the basic concepts, you may want to look at:

L. R. Rabiner, B. Gold, Theory and Application of Digital Signal
Processing. Englewood Cliffs, NJ, Prentice-Hall, 1975.

Chapters 6 and 10 in the above deal with FFT and some basic pipeline
architectures. Although the book is out of print, you may be able to
find it at a local university library, or on EBAY.

As for the twiddles between the stages, they're fairly simple to
figure out. I could tell you what they are for a 64x64 graph, or an
8x8x8x8, but then I'd be doing all the work, and you wouldn't really
learn anything (here's a hint: note the pattern of the input/output
order and twiddle sequence of each butterfly for the 8x8 graph in Fig.
10.15 on p. 587 in Rabiner and Gold's book. Now imagine what the
graph would look like if you had 2 stages of 64x64 butterflies).

If you get through all of the above and feel a little ambitious, you
might want to take a look at:

K. J. McGee, “Comments on ‘A 64-Point Fourier Transform Chip for Video
Motion Compensation Using Phase Correlation,” IEEE J. Solid-State
Circuits, vol. 33, no. 6, June 1998, pp. 928-932.

In particular, pay attention to Section III in the above: Equivalence
of Higher and Lower Radix Graphs. It has important implications for
shuffle exchange algorithms and pipeline architectures (and, as noted,
I originally developed the concept in 1981).

Kevin McGee
From: John on 30 Jun 2010 06:31
On Jun 29, 6:22 pm, "onkars" <onkar.sarode(a)n_o_s_p_a_m.gmail.com>
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.

You need to do some reading. The following book has a good section on
this:

http://www.amazon.com/Digital-Signal-Processing-John-Proakis/dp/0131873741

It's in the older editions too.

John
From: Phil Martel on 30 Jun 2010 22:01


"Jerry Avins" <jya(a)ieee.org> wrote in message
news:hAuWn.8398$YX3.6555(a)newsfe18.iad...
> 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.
Just wait a while ;-)
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> �����������������������������������������������������������������������

From: Greg Heath on 1 Jul 2010 00:36
On Jun 30, 10:01 pm, "Phil Martel" <pomar...(a)comcast.net> wrote:
> "Jerry Avins" <j...(a)ieee.org> wrote in message
>
> news:hAuWn.8398$YX3.6555(a)newsfe18.iad...> 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.
>
> Just wait a while ;-)

It may be a long time.

However, it's still preferrable to the
stock market where having a $64 balance
after two $4096 deposits hasn't been
uncommon.

Greg
From: dvsarwate on 1 Jul 2010 06:46
On Jun 30, 11:36 pm, Greg Heath <he...(a)alumni.brown.edu> wrote:

> > > I'd like to have a bank account That gives me a $4096 balance for two $64
> > > deposits.
>
> > Just wait a while ;-)
>
> It may be a long time.
>
> However, it's still preferrable to the
> stock market where having a $64 balance
> after two $4096 deposits hasn't been
> uncommon.


About nine years ago, the following appeared on a different newsgroup.
(and no, I did not write it.....)


====================================================

While I typically do not attempt to give out investment advice, this
is
something I can really get behind.

If you bought $1000 worth of Nortel stock one year ago, it would now
be
worth $49.00.

If you bought $1000 worth of Budweiser (the beer, not the stock) one
year ago, drank all the beer, and traded in the cans for the nickel
deposit, you would have $79.00.

My advice to you is to start drinking heavily.

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