Any method to FFT/DFT a long sequence

Hello,

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?

I am looking for something like the dual of the 'overlap-save/add' method
for convolution, where you can use FFT to convolve a large sequence.

Any help is greatly appreciated.

Cheers.

m26k9 wrote:
> Hello,
> 
> 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?
> 
> I am looking for something like the dual of the 'overlap-save/add' method
> for convolution, where you can use FFT to convolve a large sequence.
> 
> Any help is greatly appreciated.

256 samples is not a long FT. Do you need more RAM?

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

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. 

Thanks again.

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.

Jerry
-- 

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

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

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.

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

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.
�����������������������������������������������������������������������

>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.

>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.