minimum cycles for fft, and limits of filling short sample out with zeros

I need to get an FFT on as small a sample window as possible. I need to
understand the relationship between wave period expressed in samples,
minimum samples needed for FFT without zero-filling, what percentage of
those samples can be zeros from filling and still get a good result.

1. What is the minimum number of periods of signal I need to get an
accurate FFT (without zero filling)? I know < 1 is invalid but is 1
good enough?

2. If I sample less than one period, then zero-fill up to one period
(or more?), can I get a good result with an FFT?

3. What is the maximum proportion of the sample window that can consist
of zero-fill without somehow degrading the FFT result? If I sample one
period, and zero-fill two more for a total of three periods, will the
result be fine?


I suspect this could be worked out from the equations but I'm having a
bit of trouble doing that. I have searched the web most of today. My
application is EEG (brain waves).

Many thanks in advance if you have any thoughts...

JIm

kroger@princeton.edu writes:

> I need to get an FFT on as small a sample window as possible. I need to
> understand the relationship between wave period expressed in samples,
> minimum samples needed for FFT without zero-filling, what percentage of
> those samples can be zeros from filling and still get a good result.
> 
> 1. What is the minimum number of periods of signal I need to get an
> accurate FFT (without zero filling)? I know < 1 is invalid but is 1
> good enough?

That really depends on your definition of "good enough".

What information are you trying to get from the FFT?

> 2. If I sample less than one period, then zero-fill up to one period
> (or more?), can I get a good result with an FFT?

You're pushing the proverbial up hill in that case.

> 3. What is the maximum proportion of the sample window that can consist
> of zero-fill without somehow degrading the FFT result? If I sample one
> period, and zero-fill two more for a total of three periods, will the
> result be fine?

All that zero-filling (I'd call it zero-padding in this context) does
is "interpolate" between samples when you take the FFT.  It doesn't
add any new information.

> I suspect this could be worked out from the equations but I'm having a
> bit of trouble doing that. I have searched the web most of today. My
> application is EEG (brain waves).

OK.  Are you looking at multiple EEG signals? Or just one?  What
information are you trying to extract? If you have one "period", then
are you only interested in some artifact of the EEG that appears in
each period?

Ciao,

Peter K.

kroger@princeton.edu wrote:
> I need to get an FFT on as small a sample window as possible. I need to
> understand the relationship between wave period expressed in samples,
> minimum samples needed for FFT without zero-filling, what percentage of
> those samples can be zeros from filling and still get a good result.
>
> 1. What is the minimum number of periods of signal I need to get an
> accurate FFT (without zero filling)? I know < 1 is invalid but is 1
> good enough?

To point it to the extreme: One sample is good enough if you
have a perfect DC signal. From there on, you need to fill out
with more samples. There might come a point where you find
you don't benefit from adding more samples to the analysis.
There will come a point when you don't have any more samples
to add to the analysis.

> 2. If I sample less than one period, then zero-fill up to one period
> (or more?), can I get a good result with an FFT?

It depends what you want to do. You will not be able to separate
several close sinusoidals by zero-filling. Zero-filling will make
the spectrum look "nicer" on screen.

> 3. What is the maximum proportion of the sample window that can consist
> of zero-fill without somehow degrading the FFT result?

When dealing with measured data, the optimal proporsion of added
zeros is 0. There are good reasons for appending zeros to a data
set. It could be because one wants to use a radix-2 FFT, or to
make two spectrum plots equivalen.

Cheap improvements of the spectrum estimate is not one of them.

> If I sample one
> period, and zero-fill two more for a total of three periods, will the
> result be fine?

Again, it depends on what you want to use the data for.

> I suspect this could be worked out from the equations but I'm having a
> bit of trouble doing that. I have searched the web most of today. My
> application is EEG (brain waves).
>
> Many thanks in advance if you have any thoughts...

What you could do, is to take one recording of your data and
compute several DFTs and see what they look like at different
lengths. Start with a DFT of the full data set, and use it to
pick out the features you will look for in the short-segment
data. Then compute DFTs with shorter and shorter lengths.
Compute with and without zero-filling, and note how the spectra
change. When are the spectra no longer useful to you?

The answer sets the limit to how short sequences you can use.

Rune

Rune wrote:

What you could do, is to take one recording of your data and
compute several DFTs and see what they look like at different
lengths. Start with a DFT of the full data set, and use it to
pick out the features you will look for in the short-segment
data. Then compute DFTs with shorter and shorter lengths.
Compute with and without zero-filling, and note how the spectra
change. When are the spectra no longer useful to you?
The answer sets the limit to how short sequences you can use.


--------------

Hi Rune, thanks for the reply. I want short windows because the signal
is not stationary and because I am doing real-time analysis (so need a
result on as small a part of signal as possible).

Since the signal is not stationary (power of a frequency can change in
~100 msec), this approach would not be conclusive would it? I would
expect the spectrum to look different for a long part of signal and
some short subset of it. Thus, these emprical comparisions might be
uninterpretable (but worth trying, no doubt). Thus, I was looking for a
theoretical answer.

My intent is to simple see the power at various frequencies. I'd like a
short window and high frequency resolution, to the degree possible.

Thanks
Jim

kroger@princeton.edu writes:

> My intent is to simple see the power at various frequencies. I'd like a
> short window and high frequency resolution, to the degree possible.

You start running up against Heisenberg's uncertainty principle (or a
variant).  High frequency resolution implies longer time
durations... short time durations imply lower frequency resolution.
Whether you can trade off an acceptable amount of one for enough of
the other will depend on your application.

Ciao,

Peter K.

Peter K. wrote:
> kroger@princeton.edu writes:
>
> > My intent is to simple see the power at various frequencies. I'd like a
> > short window and high frequency resolution, to the degree possible.
>
> You start running up against Heisenberg's uncertainty principle (or a
> variant).  High frequency resolution implies longer time
> durations... short time durations imply lower frequency resolution.
> Whether you can trade off an acceptable amount of one for enough of
> the other will depend on your application.

The missing factor is noise.  In quantum uncertainty, Planck's
constant is the limiting factor.  In measuring frequency, the
signal-to-noise ratio is the limiter.  For instance, if the noise
level is zero, you might be able to measure a single sine waves
frequency perfectly with only three infinitely accurate samples.
Increase the noise floor, and the frequency accuracy goes down,
or the number of samples needed for a given frequency resolution
goes up, or both.

With low enough noise and a large enough separation of
frequencies in the signal, zero-padding might be one
computational method of getting a bit more accuracy in the
measurement of frequency peaks.  But it really depends a
lot on the characteristics of the noise and some a priori
knowledge about what's really in the signal.


IMHO. YMMV.
-- 
rhn A.T nicholson D.o.T c-O-m

"rhnlogic@yahoo.com" <rhnlogic@yahoo.com> writes:

> Peter K. wrote:
>> kroger@princeton.edu writes:
>>
>> > My intent is to simple see the power at various frequencies. I'd like a
>> > short window and high frequency resolution, to the degree possible.
>>
>> You start running up against Heisenberg's uncertainty principle (or a
>> variant).  High frequency resolution implies longer time
>> durations... short time durations imply lower frequency resolution.
>> Whether you can trade off an acceptable amount of one for enough of
>> the other will depend on your application.
>
> The missing factor is noise.  In quantum uncertainty, Planck's
> constant is the limiting factor.  In measuring frequency, the
> signal-to-noise ratio is the limiter.  For instance, if the noise
> level is zero, you might be able to measure a single sine waves
> frequency perfectly with only three infinitely accurate samples.
> Increase the noise floor, and the frequency accuracy goes down,
> or the number of samples needed for a given frequency resolution
> goes up, or both.
>
> With low enough noise and a large enough separation of
> frequencies in the signal, zero-padding might be one
> computational method of getting a bit more accuracy in the
> measurement of frequency peaks.  But it really depends a
> lot on the characteristics of the noise and some a priori
> knowledge about what's really in the signal.

Thank you for challenging these sorts of assertions from another
POV. My usual answer is similar - if you have a Hilbert transform of a
noiseless sine wave, then you can get its frequency using only two
[complex] samples: F = (p2 - p1)/T, where pi = arctan(yi/xi). 
-- 
%  Randy Yates                  % "She's sweet on Wagner-I think she'd die for Beethoven.
%% Fuquay-Varina, NC            %  She love the way Puccini lays down a tune, and
%%% 919-577-9882                %  Verdi's always creepin' from her room." 
%%%% <yates@ieee.org>           % "Rockaria", *A New World Record*, ELO   
http://home.earthlink.net/~yatescr

Randy Yates <yates@ieee.org> writes:

> Thank you for challenging these sorts of assertions from another
> POV. My usual answer is similar - if you have a Hilbert transform of a
> noiseless sine wave, then you can get its frequency using only two
> [complex] samples: F = (p2 - p1)/T, where pi = arctan(yi/xi). 

Agreed, with the caveat that you can never form the ideal Hilbert
transform, and that you can only have a completely noiseless signal
represented in a digital computer in pathological cases
(e.g. 1,-1,1,-1 or -1, 0, 1, 0, -1, etc.).

:-)

Ciao,

Peter K.

"rhnlogic@yahoo.com" <rhnlogic@yahoo.com> writes:

> The missing factor is noise.  In quantum uncertainty, Planck's
> constant is the limiting factor.  In measuring frequency, the
> signal-to-noise ratio is the limiter.  For instance, if the noise
> level is zero, you might be able to measure a single sine waves
> frequency perfectly with only three infinitely accurate samples.
> Increase the noise floor, and the frequency accuracy goes down,
> or the number of samples needed for a given frequency resolution
> goes up, or both.

Ayup!

> With low enough noise and a large enough separation of
> frequencies in the signal, zero-padding might be one
> computational method of getting a bit more accuracy in the
> measurement of frequency peaks.  But it really depends a
> lot on the characteristics of the noise and some a priori
> knowledge about what's really in the signal.

Ya.  In general, zero padding is only good for making the pictures
prettier... it doesn't help much with estimation accuracy.

Ciao,

Peter K.

"rhnlogic@yahoo.com" <rhnlogic@yahoo.com> writes:

> The missing factor is noise.  In quantum uncertainty, Planck's
> constant is the limiting factor.  In measuring frequency, the
> signal-to-noise ratio is the limiter.  For instance, if the noise
> level is zero, you might be able to measure a single sine waves
> frequency perfectly with only three infinitely accurate samples.
> Increase the noise floor, and the frequency accuracy goes down,
> or the number of samples needed for a given frequency resolution
> goes up, or both.

Ayup!

> With low enough noise and a large enough separation of
> frequencies in the signal, zero-padding might be one
> computational method of getting a bit more accuracy in the
> measurement of frequency peaks.  But it really depends a
> lot on the characteristics of the noise and some a priori
> knowledge about what's really in the signal.

Ya.  In general, zero padding is only good for making the pictures
prettier... it doesn't help much with estimation accuracy.

Ciao,

Peter K.