dft general Q

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