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.
Any method to FFT/DFT a long sequence
Started by ●November 27, 2008
Reply by ●November 27, 20082008-11-27
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. �����������������������������������������������������������������������
Reply by ●November 27, 20082008-11-27
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.
Reply by ●November 27, 20082008-11-27
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. �����������������������������������������������������������������������
Reply by ●November 27, 20082008-11-27
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
Reply by ●November 27, 20082008-11-27
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.
Reply by ●November 27, 20082008-11-27
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
Reply by ●November 27, 20082008-11-27
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. �����������������������������������������������������������������������
Reply by ●November 27, 20082008-11-27
>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.
Reply by ●November 27, 20082008-11-27
>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.