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

Randy Yates wrote:

(snip)

> I think I see the "time-frequency" uncertainty thing now and
> understand at least partially why it doesn't necessarily apply to some
> types of frequency measurements.

> This may seem really obvious, but if you look at the frequency domain
> from the purely mathematical POV, you can only have a *perfect*
> sinusoid if that sinusoid extends infinitely in time. If you have only
> an "observation" of that sinusoid, which can be modeled by multiplying
> the infinite sinusoid by a rectangular window with a width
> corresponding to the observation period, then that infinite-thin peak
> in the frequency domain spreads out. Why? Cause you don't know what
> that sinusoid is "doing" outside the window. 

Say you multiply by a gaussian with a finite width instead of
a rectangular window.  If you consider the frequency domain of
the rectangular window you will see why.  A sine multiplied
by a rect has infinite frequency components that don't decay
quite fast enough.

As I wrote in another post, atomic emission spectra are closer
to lorentzian than gaussian, but not so much different.

> Now, those facts are perfectly correct WHEN ANALYZING A SIGNAL OF INFINITE
> EXTENT. However, we are free to perform an *instantaneous* frequency 
> measurement by, e.g., measuring the change in phase of the analytic signal 
> from one sample to the next and dividing by the sample interval.  Thus even
> thought that "sine" wave may be doing some really funky things outside the
> observation interval, we can still measure the INSTANTANEOUS frequency and
> that frequency can be measured PERFECT ACCURATELY if there is NO NOISE. 

Now, for the more realistic case the sine is multiplied be a gaussian.
You don't know the exact shape of the gaussian but can sample the signal
and maybe even do exact timings of the zero crossing.  The zero crossing
will be shifted slightly be the gaussian, and the shift will be 
different at different points.  So, even measuring the zero crossings
perfectly accurately with no noise you still can't exactly measure
the underlying sine frequency.  Otherwise consider passing a signal
through an analog antialiasing filter where the response is not known
exactly.

A wider pulse allows less variation and so more accurate measurement
of the frequency.

(Note that people do optical frequency counting.  Sometime in the 1980's
the ability to count optical frequencies, I believe after mixing them 
down to a lower frequency, became possible.  This meant that frequency,
and so time, could be measured much more accurately than distance. The
solution, then, was to define the speed of light to a nice round number
(299792458m/s) and define distance in terms of the speed of light and
time.)

(snip of case with noise)

-- glen

Randy Yates wrote:
> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>
> > Stan Pawlukiewicz wrote:
> >
> > (snip)
> >
> >> The problem with this, is that in quantum mechanics the location of
> >> the particle is governed by a probability density which is related
> >> to the observation.   In signal processing, the transform broadens
> >> but the location of peak governs the frequency measurement. The
> >> frequency content of a truncated signal increases but its not a
> >> probability density, i.e. the true frequency isn't a random
> >> parameter governed by chance, like a quantum particle.
> >
> > Say I have a signal that in frequency space has a broad peak,
> > maybe not so peak shaped at all.  What do I call the frequency
> > of that signal?   Somewhere within the peak, but where?
>
> That is an excellent question, Glen. At least it sure got me thinking.
>
> I think I see the "time-frequency" uncertainty thing now and
> understand at least partially why it doesn't necessarily apply to some
> types of frequency measurements.
>
> This may seem really obvious, but if you look at the frequency domain
> from the purely mathematical POV, you can only have a *perfect*
> sinusoid if that sinusoid extends infinitely in time. If you have only
> an "observation" of that sinusoid, which can be modeled by multiplying
> the infinite sinusoid by a rectangular window with a width
> corresponding to the observation period, then that infinite-thin peak
> in the frequency domain spreads out. Why? Cause you don't know what
> that sinusoid is "doing" outside the window.
>
> Now, those facts are perfectly correct WHEN ANALYZING A SIGNAL OF INFINITE
> EXTENT. However, we are free to perform an *instantaneous* frequency
> measurement by, e.g., measuring the change in phase of the analytic signal
> from one sample to the next and dividing by the sample interval.  Thus even
> thought that "sine" wave may be doing some really funky things outside the
> observation interval, we can still measure the INSTANTANEOUS frequency and
> that frequency can be measured PERFECT ACCURATELY if there is NO NOISE.
>
> Now if there IS noise, you can't measure even the INSTANTANEOUS frequency
> accurately and must do some averaging or whatever to get the accuracy up,
> so introducing noise requires that we measure the signal longer to get an
> accurate estimate.
>
> Does that make sense?

Yes, it does. You have just described the basic philosophy behind
parametric frequency estimators (MUSIC, ESPRIT,...). While it is true
that these methods are not governed by the Heisenberg uncertainty,
there are problems with these as well.

The main problem is that they are based on the *knowledge* of the
signal being comprised by sinusoids, and also that the number of
sinusoids is known at system design time. Here, "assume" or "have
reason to believe" are not good enough, one has to *know*.

Both questions reqire knowledge that can be very hard to ensure in
practical situations. So basically, one trades accuracy for robustness.

Rune

glen herrmannsfeldt wrote:
> Stan Pawlukiewicz wrote:
>
> (snip)
>
> > There's a difference between uncertainty and trying to stuff a square
> > peg in a round hole.  In discussing the uncertainty principle, in this
> > forum and in the past, the context has been either measuring the
> > frequency of a single sine wave or the ability to measure the
> > frequencies of two closely spaced sine waves.  Would you agree that
> > there is a difference between uncertainty and ambiguity?
>
>
> I will agree that they are different, but maybe not as different
> as some people seem to think.
>
> In real systems you never find a single sine wave, that is, from
> t= negative infinity to positive infinity.

Agreed, what the time domain is concerned. Most measurements
I am aware of, are of finite duration. Even so, there is a vast
difference between accurately estiamting the frequency of one
sinusoidal, and detecting the presence of two close sinusoidals.

> When I first learned all this there was the concept of wave packet,
> which tends to be a sine multiplied by a gaussian or some similar
> peak shaped function.  The peak shaped function then has a width,
> and, amazingly enough, so does the fourier transform of the
> combined function.
>
> Atomic emission spectra tend to be closer to lorentzian than
> gaussian, but it works out about the same.  If you try to measure
> the frequency, is the result uncertain or ambiguous?

In my lingo, this is a variation of the frequency estimation
problem. It seems you have only one sinusoidal (at least that's
how I interpret your description) and your problem is to detect
the frequency of this sinusoidal as exact as possible.

The separation problem is to detect the presence of two
separate sinusoidals that are close in frequency, and detect
them as two lines as opposed to one. This matlab script
demonstrates the problem:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
f1 = 0.14;           % Normalized frequencies of sinusoidals
f2 = 0.2;

N1 = 8;              % length of short data sequence
N2 = 32;             % Length of long data sequence

fv1=[0:N1]/N1;       % Frequency vector, short data sequence
fv2=[0:N2]/N2;       % Frequency vector, long data sequence

% Generate short data sequence, plot DFT
s1= exp(j*2*pi*f1*[0:N1-1])+exp(j*2*pi*f2*[0:N1-1]);
S1=fft(s1)/N1;
L1=stairs(fv1,abs([S1,S1(1)]));
set(L1,'color',[0 0 1])
hold on

% Generate long data sequence, plot DFT
s2= exp(j*2*pi*f1*[0:N2-1])+exp(j*2*pi*f2*[0:N2-1]);
S2=fft(s2)/N2;
L2=stairs(fv2,abs([S2,S2(1)]));
set(L2,'color',[1 0 0])

% Plot true spectrum lines
plot([f1 f1],[0 1],'k',[f2 f2],[0 1],'k')
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The black lines represent the true spectrum of the process
that generate the data. The blue line represents the spectrun
as estimated from an observation consisting of 8 samples, while
the red line represents the spectrum as estimated from 32 samples.

The short data sequence shows a spectrum peak in the general
vicinity of the true lines, but the frequency estimate is not
accurate and it does not reveal that there are two lines present.

The long data sequence shows that there are two lines present,
although the frequency estimates for the lines are still not
accurate.

> As for your question in this context, I would say you can have
> ambiguity without uncertainty, but not uncertainty without ambiguity.

Only half correct. Ambiguity is one particular type of uncertainty.
Inaccuracy is another.

Rune

Rune Allnor wrote:
(snip)

> Agreed, what the time domain is concerned. Most measurements
> I am aware of, are of finite duration. Even so, there is a vast
> difference between accurately estiamting the frequency of one
> sinusoidal, and detecting the presence of two close sinusoidals.

Not just one or two, but an infinite number of them.

Consider sin(w t)exp(-A t**2)  for some constant A.
This is a sum of an infinite number of sines near w,
assuming reasonable values for A.

If you try to find w by measuring a small number of
sample points there will be uncertainty depending on
where in the gaussian you are.


As for two sines, consider the low pressure sodium
emission spectrum with two narrow lines closely spaced.
You can detect that there are two lines.

Now consider sodium at higher temperature and pressure.
The lines are broadened due to doppler shift and collisions,
and there is also reabsorption by other atoms.

-- glen

"Rune Allnor" <allnor@tele.ntnu.no> writes:
> Randy Yates wrote:
> [...]
>> Does that make sense?
>
> Yes, it does. You have just described the basic philosophy behind
> parametric frequency estimators (MUSIC, ESPRIT,...). 

Thanks, Rune. I've heard about these but never had a clear understanding. 

I've never really understood the uncertainty concept as applied to DSP (i.e., the
non-physics version), but now I'm embarassed that it's so simple. 
-- 
%  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 wrote:
> "Rune Allnor" <allnor@tele.ntnu.no> writes:
> > Randy Yates wrote:
> > [...]
> >> Does that make sense?
> >
> > Yes, it does. You have just described the basic philosophy behind
> > parametric frequency estimators (MUSIC, ESPRIT,...).
>
> Thanks, Rune. I've heard about these but never had a clear understanding.

You have the basic idea very clearly. The rest is a matter of getting
the idea to work with more than one sinusoidal, with an unknown number
of sinusoidals (but you need to *know* an absolute upper limit on the
number of sinusoidals), and in the presence of noise.

> I've never really understood the uncertainty concept as applied to DSP (i.e., the
> non-physics version), but now I'm embarassed that it's so simple.

In my experience, that kind of embarrasment is a hallmark of insight.
It takes time to ponder those kinds of things, and one usually needs
a reason for pondering. And a provocation to think the consequences
through.

For my own part, I made the matlab script I posted in a response to
Glen
Herrmannsfeldt after I had encountered a Head of Division at an
international R&D institution, who claimed the parametric high
resolution
techniques I implemented for my PhD thesis were obsolete: "All you have

to do is to zero-pad your data and everything is revealed." This guy
was
head of the division where most DSP related stuff was done, and would
have had 20 or 30 years of "experience" in DSP.

Rune

glen herrmannsfeldt wrote:
> Rune Allnor wrote:
> (snip)
>
> > Agreed, what the time domain is concerned. Most measurements
> > I am aware of, are of finite duration. Even so, there is a vast
> > difference between accurately estiamting the frequency of one
> > sinusoidal, and detecting the presence of two close sinusoidals.
>
> Not just one or two, but an infinite number of them.
>
> Consider sin(w t)exp(-A t**2)  for some constant A.
> This is a sum of an infinite number of sines near w,
> assuming reasonable values for A.
>
> If you try to find w by measuring a small number of
> sample points there will be uncertainty depending on
> where in the gaussian you are.
>
>
> As for two sines, consider the low pressure sodium
> emission spectrum with two narrow lines closely spaced.
> You can detect that there are two lines.
>
> Now consider sodium at higher temperature and pressure.
> The lines are broadened due to doppler shift and collisions,
> and there is also reabsorption by other atoms.

Now I am confused. Are you capable of studying each line in
its own right? Or do you just see a fuzzy wnergy distribution
with respect to frequency?

If you are not able to study single absorption/emission lines,
then I would say you are dealing with a power spectrum density
estimation problem.

If you can see single lines and want to find their frequency
as exact as possible, then you are dealing with a frequency
estimation problem.

If you want to see if one line has split in two when you
modify the material, you are dealing with a line resolution
problem.

Rune

Rune Allnor wrote:

> glen herrmannsfeldt wrote:

(snip)

>>Now consider sodium at higher temperature and pressure.
>>The lines are broadened due to doppler shift and collisions,
>>and there is also reabsorption by other atoms. 

> Now I am confused. Are you capable of studying each line in
> its own right? Or do you just see a fuzzy wnergy distribution
> with respect to frequency?

Well, the question had to do with being able to measure
frequency exactly when there is no noise.  I was trying to
find real world examples that, even without noise, one would
not be able to measure exactly.  You can study each line in
its own right if you can build a filter to separate them.
That filter is then part of the system.  It can be considered
noiseless, but otherwise should have properties that real
filters have.

> If you are not able to study single absorption/emission lines,
> then I would say you are dealing with a power spectrum density
> estimation problem.

So, in the noiseless case can you do an exact power
spectral density measurement?

> If you can see single lines and want to find their frequency
> as exact as possible, then you are dealing with a frequency
> estimation problem.

The claim was exact.  I am looking for reasons why it
won't be exact.

> If you want to see if one line has split in two when you
> modify the material, you are dealing with a line resolution
> problem.

Well, sodium already has two lines without any modifying.

-- glen

glen herrmannsfeldt wrote:
> Stan Pawlukiewicz wrote:
> 
> (snip)
> 
>> There's a difference between uncertainty and trying to stuff a square 
>> peg in a round hole.  In discussing the uncertainty principle, in this 
>> forum and in the past, the context has been either measuring the 
>> frequency of a single sine wave or the ability to measure the 
>> frequencies of two closely spaced sine waves.  Would you agree that 
>> there is a difference between uncertainty and ambiguity?
> 
> 
> 
> I will agree that they are different, but maybe not as different
> as some people seem to think.

Then what's the Heisenberg ambiguity principle;)

Schroderinger's Drag Queen?


> 
> In real systems you never find a single sine wave, that is, from
> t= negative infinity to positive infinity.

Agreed, in real life, stuff is more complicated.
> 
> When I first learned all this there was the concept of wave packet,
> which tends to be a sine multiplied by a gaussian or some similar
> peak shaped function.  The peak shaped function then has a width,
> and, amazingly enough, so does the fourier transform of the
> combined function.
> 
> Atomic emission spectra tend to be closer to lorentzian than
> gaussian, but it works out about the same.  If you try to measure
> the frequency, is the result uncertain or ambiguous?
> 
> As for your question in this context, I would say you can have
> ambiguity without uncertainty, but not uncertainty without ambiguity.
> 
> -- glen
> 

Stan Pawlukiewicz wrote:

> glen herrmannsfeldt wrote:

>> Stan Pawlukiewicz wrote:

>> (snip)


(snip)

> Then what's the Heisenberg ambiguity principle;)

Whether the cat died or not.

> Schroderinger's Drag Queen?

>> In real systems you never find a single sine wave, that is, from
>> t= negative infinity to positive infinity.

> Agreed, in real life, stuff is more complicated.

And this problem makes it hard to get right.

The discussion was of a noiseless source, but do we also require
a noiseless detector?  For a heterodyne detector, a noiseless
mixer and local oscillator?  How do we get the right amount of
real life into the problem, even with a noiseless source.

In considering zero crossing of an optical signal, how do we
know where zero is?  Optical signals are always AC coupled,
and so require a baseline restore.  Any errors in the baseline
restore shift the reference for zero crossing.

-- glen