On Fri, 28 Nov 2008 02:29:31 -0600, "m26k9"
<maduranga.liyanage@gmail.com> wrote:

>
>
>Thanks a lot guys.
>
>Seems the number of FFT points are not a limitation since they can be fed
>serially. I will have to read about FFT first before going any further.
>
>Thanks for links Kevin. Didnt know such a 'huge' number of FFTs can be
>supported.
>
>Appreciate the help guys.

Hi,
  You might have a look at:

http://www.dsprelated.com/showarticle/63.php

Good Luck,
[-Rick-]

Thanks a lot guys.

Seems the number of FFT points are not a limitation since they can be fed
serially. I will have to read about FFT first before going any further.

Thanks for links Kevin. Didnt know such a 'huge' number of FFTs can be
supported.

Appreciate the help guys.

Glen Herrmannsfeldt wrote:
>What I am still interested in seeing is 150000000 sample
>FFT's, such as a whole CD. At that size, you have to be
>a little careful with memory usage.

Glen - three of the following might do it:

http://www.dilloneng.com/fft_ip/ulfft/ultralong-fft-ip-core-for-xilinx-fpgas

With a radix3 front end, you'd split the data into three streams and
then you could do a 64M FFT on each using three of the above. (PS: I
have no commercial interest or connection with the above company, and
have never used any of their products).

As for m26k9, of course you can combine smaller transforms into larger
ones, but I agree with Jerry that you need to do a lot more reading.
One of my favorites was an old textbook:

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

Sure, it's dated with regard to some things, but it's got several good
sections on FFT (often available at a local university library, or
used copies at amazon.com).

Kevin

m26k9 wrote:
>> The first F in FFT, the part that makes it fast, is building
>> up larger transforms from smaller ones.  Once you understand
>> that, the answer to your question is obvious.
>>
>> What I am still interested in seeing is 150000000 sample
>> FFT's, such as a whole CD.  At that size, you have to be
>> a little careful with memory usage.
>>
>> -- glen
>>
>>
> 
> Thanks a lot Glen.
> 
> I honestly have no clear understanding as to how FFT is doing the DFT. 
> I will look in to that. 
> 
> I am actually working on OFDM systems. So the transmitter is doing a the
> DFT on its N-point data by feeding these N-samples to the FFT module. My
> concern is, if the transmitter is equipped with a FFT module that takes in
> N samples (designed to take N-samples) at a time, if there is an efficient
> method to perform a 2N FFT operation with that N-point FFT module.
> 
> Maybe I am understanding this all wrong. My idea of an N-point FFT module
> is that of a DSP, with N inputs an I feed my N-points these inputs in
> parallel and I get a N outputs. I know in scalable-OFDM I can have
> different values of N(512,1024, etc.), but is there a 'maximum' number of
> inputs to an FFT module?
> 
> Thank you again. I think I will look into the internal of a FFT.

The inputs to a Fourier transform are individual samples taken at 
regular intervals in time. They are acquired as a serial stream. If fed 
to a digital-to-analog converter, they would reproduce the original 
signal. (Provided that the proper filters are used before the 
analog-to-digital converter and after the digital-to-analog converter.) 
You probably also want to read earlier chapters about sampling.

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

>You need to do some more reading. An FFT is neither more nor less than 
>an efficient way to calculate a DFT. A very good treatment, The 
>Scientist and Engineer's Guide to Digital Signal Processing, is 
>available on line. Chapters 8 through 12 may enlighten you. Come back 
>and ask for clarification as you go through them.
>
>Jerry
>-- 
>Engineering is the art of making what you want from things you can get.
>�����������������������������������������������������������������������
>

Thanks Jerry.
Found the e-book. Going through it now.

>The first F in FFT, the part that makes it fast, is building
>up larger transforms from smaller ones.  Once you understand
>that, the answer to your question is obvious.
>
>What I am still interested in seeing is 150000000 sample
>FFT's, such as a whole CD.  At that size, you have to be
>a little careful with memory usage.
>
>-- glen
>
>

Thanks a lot Glen.

I honestly have no clear understanding as to how FFT is doing the DFT. 
I will look in to that. 

I am actually working on OFDM systems. So the transmitter is doing a the
DFT on its N-point data by feeding these N-samples to the FFT module. My
concern is, if the transmitter is equipped with a FFT module that takes in
N samples (designed to take N-samples) at a time, if there is an efficient
method to perform a 2N FFT operation with that N-point FFT module.

Maybe I am understanding this all wrong. My idea of an N-point FFT module
is that of a DSP, with N inputs an I feed my N-points these inputs in
parallel and I get a N outputs. I know in scalable-OFDM I can have
different values of N(512,1024, etc.), but is there a 'maximum' number of
inputs to an FFT module?

Thank you again. I think I will look into the internal of a FFT.

Cheers.

m26k9 wrote:
> Thanks a bunch Andrew. Didnt know that part of FFT'ing.
> Actually what I am doing is theoretical and concerned about the DF
> operation. Not really the FFT implementation. But I mentioned FFT because
> it is the most common method used.
> 
> What I want to do is to DFT a sequence of N with a DFT size of 2N. The
> problem is unless there is a mathematical way of doing a 2N size DFT on a
> system designed to do N size DFT, I cannot justify my method.
> 
> I am looking for something like the 'overlap-save' method used for
> convolving a large sequence. Some block-by-block kind of method to DFT.
> Take the first N-blocks and do some operation, take the second set and so
> on, and then finally calculate the 2N/3N, etc, DFT of an original N size
> sequence.
> 
> Thanks a lot guys.

You need to do some more reading. An FFT is neither more nor less than 
an efficient way to calculate a DFT. A very good treatment, The 
Scientist and Engineer's Guide to Digital Signal Processing, is 
available on line. Chapters 8 through 12 may enlighten you. Come back 
and ask for clarification as you go through them.

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

m26k9 wrote:

> I was wondering if there is any method for performing a FFT/DFT on a large
> number of samples? For example if I have a signal with 256 samples but my
> DSP only supports 128 samples input, is there an efficient way to get the
> complete sequence FFT/DFT'ed?

The first F in FFT, the part that makes it fast, is building
up larger transforms from smaller ones.  Once you understand
that, the answer to your question is obvious.

What I am still interested in seeing is 150000000 sample
FFT's, such as a whole CD.  At that size, you have to be
a little careful with memory usage.

-- glen

Thanks a bunch Andrew. Didnt know that part of FFT'ing.
Actually what I am doing is theoretical and concerned about the DF
operation. Not really the FFT implementation. But I mentioned FFT because
it is the most common method used.

What I want to do is to DFT a sequence of N with a DFT size of 2N. The
problem is unless there is a mathematical way of doing a 2N size DFT on a
system designed to do N size DFT, I cannot justify my method.

I am looking for something like the 'overlap-save' method used for
convolving a large sequence. Some block-by-block kind of method to DFT.
Take the first N-blocks and do some operation, take the second set and so
on, and then finally calculate the 2N/3N, etc, DFT of an original N size
sequence.

Thanks a lot guys.

On Thu, 27 Nov 2008 11:48:16 -0500, Jerry Avins wrote:

> m26k9 wrote:
>> Thanks Jerry.
>> 
>> Actually that was just an example number. I want to if there is a way
>> if I want to FFT that is more than that is supported by the DSP.
>> 
>> I am looking for a mathematical method actually.
> 
> What do you mean by "supported by the DSP"? DSPs compute FFTs
> algorithmically. The hardware is not a limitation.

to the OP:

The parameters that have been known to limit the size of FFTs that can be 
done include: time available, memory available and precision the 
machine's arithmetic operations.  (The last is kind of a practical 
consideration, because you can usually burn tonnes of the first two to 
create more of the third, but that's not often a great idea.)

What Jerry's getting at here, m26k9, is that FFTs are composed of smaller 
FFTs, so if you've got small FFTs you can generally build larger ones, 
provided that you have sufficient memory and time (and enough precision 
for the result to have enough significant bits to make it worth the 
trouble.)  I've had a 56002 doing 256k-point FFTs, using off-chip DRAM 
that was accessed as a peripheral, in page-mode.  Long ago (in the 60s) 
it was not uncommon for scientists to use their little 32-kword 
mainframes and minis to compute similar sizes of FFT, streaming all of 
the data to and from disk storage.  The process and the algorithms are 
very similar.

Cheers,

-- 
Andrew