DSPRelated.com
Forums

dft general Q

Started by Vec March 21, 2005
Hello

When a statement like "take 16 point DFT" of the input x[n].
Does that mean the max value of n is 16, I mean an input sequence with 
say 40000 points, you then take the DFT of this input signal, does that 
mean you get back 40000 spectral points from the DFT, if yes, than why 
the literature say 16, or 8 or what ever number pint DFT, why not just 
say DFT if the input signal. but if no then, does that mean I can take a 
16 pint DFT for a 40000 point input signal?

Thanks


Vec wrote:
> Hello > > When a statement like "take 16 point DFT" of the input x[n]. > Does that mean the max value of n is 16,
Substitute the word "sample" for "point" and it may become clearer (even though "point" is the vernacular.) In your example, n can be of any value but if you are taking a 16 sample DFT you are chosing 16 consecutive samples from x[n] to transform.
> I mean an input sequence with > say 40000 points, you then take the DFT of this input signal, does that > mean you get back 40000 spectral points from the DFT,
If you transform all 40000 samples at once.
> if yes, than why > the literature say 16, or 8 or what ever number pint DFT, why not just > say DFT if the input signal.
Because for various reasons and in various ways, the signal is broken up into 16, or 8 or whatever sized sample blocks (which can even be overlapped in some applications.) The size is typically a power of two because the DFT can be performed much faster on such a set using the FFT method of calculation.
> but if no then, does that mean I can take a > 16 pint DFT for a 40000 point input signal?
It means you take a lot of them. Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
>Vec wrote: >> Hello >> >> When a statement like "take 16 point DFT" of the input x[n]. >> Does that mean the max value of n is 16, > >Substitute the word "sample" for "point" and it may become >clearer (even though "point" is the vernacular.) In your >example, n can be of any value but if you are taking a 16 >sample DFT you are chosing 16 consecutive samples from x[n] >to transform. > >> I mean an input sequence with >> say 40000 points, you then take the DFT of this input signal, does that
>> mean you get back 40000 spectral points from the DFT, > >If you transform all 40000 samples at once. > >> if yes, than why >> the literature say 16, or 8 or what ever number pint DFT, why not just
>> say DFT if the input signal. > >Because for various reasons and in various ways, the signal >is broken up into 16, or 8 or whatever sized sample blocks >(which can even be overlapped in some applications.) The >size is typically a power of two because the DFT can be >performed much faster on such a set using the FFT method of >calculation. > >> but if no then, does that mean I can take a >> 16 pint DFT for a 40000 point input signal? > >It means you take a lot of them. > > >Bob
Bob seems to have crisply replied to your doubts. If I can just add this one point: It is not possible for computational reasons to take 40,000 point DFT in one shot(though it would be ideal, because then the spectral resolution will be exactly 1hz- n.fs/n), hence we *divide and conquer* by taking taking 2500 frames of 16 point fft. Does that make sense? --Bhooshan This message was sent using the Comp.DSP web interface on www.DSPRelated.com
>hence we *divide and conquer* by taking >taking 2500 frames of 16 point fft.
I think I have been a little liberal with the correctness for the sake of effect. Strictly speaking the divide and conquer alogorithm is inside the FFT calculations but I kind of *implied* here as if the idea of processing DFT in terms of *frames* is the idea behind D&C, which is not true. Hope am clear with my part over-simplification there. --Bhooshan This message was sent using the Comp.DSP web interface on www.DSPRelated.com
bhooshaniyer wrote:

   ...

> Bob seems to have crisply replied to your doubts. If I can just add this > one point: It is not possible for computational reasons to take 40,000 > point DFT in one shot(though it would be ideal, because then the spectral > resolution will be exactly 1hz- n.fs/n), hence we *divide and conquer* by > taking taking 2500 frames of 16 point fft. Does that make sense?
2500 is only about half of what would be needed. It doesn't account for any necessary overlap. I suspect that FFTs as small as 16 points are used for examples. Because of the way that the expense of an FFT grows with size -- provided there is enough memory to accommodate the data, fewer large ones will be more efficient than many small ones. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Jerry Avins wrote:
> bhooshaniyer wrote: > > ... > >> Bob seems to have crisply replied to your doubts. If I can just add this >> one point: It is not possible for computational reasons to take 40,000 >> point DFT in one shot(though it would be ideal, because then the spectral >> resolution will be exactly 1hz- n.fs/n), hence we *divide and conquer* by >> taking taking 2500 frames of 16 point fft. Does that make sense? > > > 2500 is only about half of what would be needed. It doesn't account for > any necessary overlap. I suspect that FFTs as small as 16 points are > used for examples. Because of the way that the expense of an FFT grows > with size -- provided there is enough memory to accommodate the data, > fewer large ones will be more efficient than many small ones. > > Jerry
Would that imply there is a trade off between efficiency and other attributes when it comes to choosing the ratio of braking up the total sample numbers to n groups with k samples each, further more overlapping them to archive certain results? I have few books about the theory, but I seam to lack how to apply and what to expect. I would appreciate some recommendation to books about that. Thanks
bhooshaniyer wrote:
> > It is not possible for computational reasons to take 40,000 > point DFT in one shot
How in the world can you make such a blanket statement? It completely depends on the platform, datatype, and speed requirements. On my less-than-cutting-edge Athlon XP 2100+: a 40,000 point FFT can be performed in ** 4 ms by FFTW3 ( http://www.fftw.org ) ** 10 ms by KISSFFT ( http://sourceforge.net/projects/kissfft ) -- Mark
Mark--


>bhooshaniyer wrote: >> >> It is not possible for computational reasons to take 40,000 >> point DFT in one shot > >How in the world can you make such a blanket statement? It completely >depends on the platform, datatype, and speed requirements.
If one has implemented FFT in an embedded DSP system with about 100 kb internal memory, it wouldnt seem so blankety.
> >On my less-than-cutting-edge Athlon XP 2100+: a 40,000 point FFT can be >performed in >** 4 ms by FFTW3 ( http://www.fftw.org ) >** 10 ms by KISSFFT ( http://sourceforge.net/projects/kissfft )
At what sampling rate? Anyways in my limited experience of persorming FFT in an embedded DSP system(not a native machine with 40 gb hard disk and 256mb of RAM but less than 1mb of RAM and about 16 mb of SDRAM)for a real-time project am yet to see any higher usage then 512 point FFT. Any larger then that I believe is not feasible for real-time realization and syncronization. On the other hand, you can performing any size of FFT you want in an offline environment like matlab. --Bhooshan This message was sent using the Comp.DSP web interface on www.DSPRelated.com
bhooshaniyer wrote:
> Mark-- > >>bhooshaniyer wrote: >> >>>It is not possible for computational reasons to take 40,000 >>>point DFT in one shot >> >>How in the world can you make such a blanket statement? It completely >>depends on the platform, datatype, and speed requirements. > > > If one has implemented FFT in an embedded DSP system with about 100 kb > internal memory, it wouldnt seem so blankety.
Your explanation makes it seem more so. Please don't make absolute statements about the entire field of DSP that only reflect the limited experience of one subfield. Someone might actually trying to learn something from this newsgroup :^)
> > >>On my less-than-cutting-edge Athlon XP 2100+: a 40,000 point FFT can be >>performed in >>** 4 ms by FFTW3 ( http://www.fftw.org ) >>** 10 ms by KISSFFT ( http://sourceforge.net/projects/kissfft ) > > > At what sampling rate?
Sampling rate doesn't enter into it. That doesn't affect how fast a single transform can be done. It certainly influences the realtime requirements. Then again, not all systems needs to be realtime. If 40,000 point FFTs are all you want to do, then my box could chew them @ 10MS/s. 4e4 / 4e-3 = 1e7 In reality, that would be lowered by additional processing and IO.
> Anyways in my limited experience of persorming FFT > in an embedded DSP system(not a native machine with 40 gb hard disk and > 256mb of RAM but less than 1mb of RAM and about 16 mb of SDRAM)for a > real-time project am yet to see any higher usage then 512 point FFT. Any > larger then that I believe is not feasible for real-time realization and > syncronization. On the other hand, you can performing any size of FFT you > want in an offline environment like matlab.
I never assume I will never need feature X. I customized an FFT algo once for a 16bit fixed point processor that could not even fit the entire sequence into memory. I've also seen applications that require multi-megapoint FFTs for extremely fine frequency resolution. Absolute truth #1 : There are no absolutes.
Mark-

>Your explanation makes it seem more so.
>Please don't make absolute statements about the entire field of DSP that
>only reflect the limited experience of one subfield. Someone might >actually trying to learn something from this newsgroup :^)
I never said that I dish out AT's in my posts! Anyways, I just give my opinions, which are based on my experience.Isnt it quite obvious that posts in a public technical forum - like any other forum - will have personal biases? I dont buy this argument that some one hangs about comp.dsp for absolute truths on even the most miniscule subset of DSP, let alone the entire field of DSP. I was advicing a relatively in-experienced engineer with a few tips based on my experience.I dont read anything more than that. And in fact I believe my advice sets his expectations right for an implementation of FFT. Further more, I also added a note saying that whatever I said involved fair amount of over simplification and it was based on computational reasons. All in all I thought it was an advice that was not wrong to begin with and quite helpful if he ever gets around to implementing FFT on an embedded chip.
>@ 10MS/s.
That seems a like hell lot of time to me.
>I customized an FFT algo once for a 16bit fixed point processor that >could not even fit the entire sequence into memory.
What was the size of FFT you implemented?
>Absolute truth #1 : There are no absolutes.
Well, I sign off my posts with "--bhooshan". Its one man's opinion,Period. PS:My grand father - who was a doctor and a military man during the world wars - once told me that an argument should be stopped once it starts generating more heat than light. --Bhooshan This message was sent using the Comp.DSP web interface on www.DSPRelated.com