Reply by Steven G. Johnson●March 16, 20042004-03-16
Ronald H. Nicholson Jr. wrote:
> If you knew, a priori, that there were exactly one or two frequencies
> present, with extremely low noise and/or other modulation present,
> you might be able to "resolve" whether there are one or two sinusoids,
> and the separation if there are two, by the total shape of the "hump"
> spanning the entire FFT. (e.g. not just "interpolating" the peaks).
Yes, if you know that your signal consists of a bounded number of
(possibly exponentially decaying) sinusoids, possibly with a small
amount of noise, then there are a number of known techniques to extract
their frequencies and amplitudes with greater accuracy than is possible
with the DFT.
The simplest thing, of course, is simply a least-squares fit, but this
is very ill-conditioned. A very nice, well-behaved technique was
described in:
V. A. Mandelshtam and H. S. Taylor, "Harmonic inversion of time
signals," J. Chem. Phys., vol. 107, no. 17, p. 6756-6769 (Nov. 1
1997). See also erratum, ibid, vol. 109, no. 10, p. 4128 (Sep. 8
1998).
Cordially,
Steven G. Johnson
Reply by Ronald H. Nicholson Jr.●March 11, 20042004-03-11
In article <404df632$0$1167$65c69314@mercury.nildram.net>,
Adrian Hey <ahey@NoSpicedHam.iee.org> wrote:
>I think a better test to see the benefits would be to have two test
>signals of N samples each, one with a single sinusoid at frequency
>half way between the centre frequencies of two adjacent DFT bins and
>a second consisting of the sum of two sinusoids each of which is
>precisely centred one of the same two bins respectively.
>
>My guess is if you look at the spectrum (mag^2 of DFT output) for these
>two cases using N point DFT you'll find it diffucult to to tell whether
>there is only one or two distinct sinusoids there.
If you knew, a priori, that there were exactly one or two frequencies
present, with extremely low noise and/or other modulation present,
you might be able to "resolve" whether there are one or two sinusoids,
and the separation if there are two, by the total shape of the "hump"
spanning the entire FFT. (e.g. not just "interpolating" the peaks).
In the old analog radar days, I think they called this type of signal
interpretation "blobology" (as in: is that blip one or two bogies?)
I also wouldn't doubt that radio astronomers do something like this to
resolve certain kinds of binary systems.
IMHO. YMMV.
--
Ron Nicholson rhn AT nicholson DOT com http://www.nicholson.com/rhn/
#include <canonical.disclaimer> // only my own opinions, etc.
Reply by Robert Scott●March 9, 20042004-03-09
On Tue, 09 Mar 2004 16:44:37 +0000, Adrian Hey
<ahey@NoSpicedHam.iee.org> wrote:
>Robert Scott wrote:
>
>> On 9 Mar 2004 02:48:30 -0800, allnor@tele.ntnu.no (Rune Allnor) wrote:
>> A zero-padding of half the data did seem
>> to increase the resolution slightly, but when I zero-padded even more,
>> the two humps blended into one another, producing a single hump
>> half-way between the two
>
>Hello Robert,
>
>IIRC in your original description of your experiment you weren't zero
>padding in the sense that we have been discussing. That is, taking
>N signal samples and padding with N zeros to give a 2N point DFT, or
>3N zeros to give a 4N point DFT etc..
>
>Instead you were truncating the original N sample sequence to N/2
>samples with N/2 trailing zeros, or N/4 samples with 3N/4 trailing
>zeros etc..
>
>Hope I've got that right. If so, then it isn't surprising that the
>humps got wider and blended together as you describe.
That is true, but that was the easiest way I could cobble up some code
in an existing application. I think the results I obtained, when
properly interpretted, do apply to the case of true zero-padding. But
as I said, my positive results apply only to a single sine wave at a
time.
-Robert Scott
Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)
Reply by Adrian Hey●March 9, 20042004-03-09
Jerry Avins wrote:
> The issue that I addressed is the false
> notion that the same process, applied to measured samples of a waveform,
> reveals details that the actual samples are too few to reveal.
This notion is not false if we're talking about using uninterpolated DFT
samples to calculate the spectrum, and I take we are since that is what most
graphs/displays are based on, and your own comments regarding French curves
(implying the curve being interpolated is real) seem to support this
hypothesis.
You really can't reconstruct the spectrum from the Fs/N spaced spectrum
samples given by the mag^2 of an N (non-zero) point DFT. Well actually you
can in the trivial case where signal is known to be periodic (with period
N), but usually the real world isn't that nice.
You can do the reconstruction (in principle, e.g. by sinc convolution) if
you start out with Fs/(2.N) spaced samples, but even in this case using zero
padded FFT's or similar is probably the more computationally effecient way
of doing this (at least until samples are dense enough for a simple
polynomial based interpolation to provide sufficient precision).
Regards
--
Adrian Hey
Reply by Adrian Hey●March 9, 20042004-03-09
Robert Scott wrote:
> On 9 Mar 2004 02:48:30 -0800, allnor@tele.ntnu.no (Rune Allnor) wrote:
> A zero-padding of half the data did seem
> to increase the resolution slightly, but when I zero-padded even more,
> the two humps blended into one another, producing a single hump
> half-way between the two
Hello Robert,
IIRC in your original description of your experiment you weren't zero
padding in the sense that we have been discussing. That is, taking
N signal samples and padding with N zeros to give a 2N point DFT, or
3N zeros to give a 4N point DFT etc..
Instead you were truncating the original N sample sequence to N/2
samples with N/2 trailing zeros, or N/4 samples with 3N/4 trailing
zeros etc..
Hope I've got that right. If so, then it isn't surprising that the
humps got wider and blended together as you describe.
I think a better test to see the benefits would be to have two test
signals of N samples each, one with a single sinusoid at frequency
half way between the centre frequencies of two adjacent DFT bins and
a second consisting of the sum of two sinusoids each of which is
precisely centred one of the same two bins respectively.
My guess is if you look at the spectrum (mag^2 of DFT output) for these
two cases using N point DFT you'll find it diffucult to to tell whether
there is only one or two distinct sinusoids there.
If you then repeat this for various oversampling ratios (e.g. pad with N
zeros and do 2N point FFT to get 2:1 oversampling), I think you will
begin to see the effect Ronald H. Nicholson described in his post. (Of
course the actual frequency spacing between bins will half each time you
double the DFT length, so it would help with comparison if you can
compensate for this in your plots to keep the frequency axis constant.)
Regards
--
Adrian Hey
Reply by Jerry Avins●March 9, 20042004-03-09
Ronald H. Nicholson Jr. wrote:
> In article <4046002e$0$3076$61fed72c@news.rcn.com>,
> Jerry Avins <jya@ieee.org> wrote:
>
>>Zero padding doesn't increase resolution. It increases the number of
>>points in the plot by interpolating. You can do as well with a French
>>curve and a practiced eye.
>
>
> Both correct and incorrect. Theoretically, zero padding won't increase
> FFT resolution. But the theoretically correct intervening points are
> properly calculated by infinite width (or at least twice the data length
> to dump the coeff's which will be multiplied by zero) Sinc reconstruction.
>
> Sinc reconstruction will resolve more inflection points than something
> like a cubic polynomial interpolation (roughly what a French curve
> approximates). That is why Mr. Scott's experiment was actually resolving
> two close humps by zero padding the FFT (given a low enough noise floor).
>
> A full Sinc interpolation reconstruction process will also resolve
> more humps and inflection points than a low order polynomial, but at a
> much higher computational cost than by just using a zero padded FFT.
> So zero padding an FFT is a computationally efficient way of doing
> a better interpolation than one can get using a low order polynomial
> interpolator. It really doesn't add information, but it does "correct"
> the information which is commonly and incorrectly assumed from using
> methods such as the aforementioned French curve and a "practiced" eye.
>
>
> IMHO. YMMV.
Ron,
I had thought the issue resolved. No one seems to doubt (and I didn't
claim otherwise) that zero padding can reveal the underlying shape of a
curve -- a filter's impulse response, for example -- with increasing
accuracy as the number of added zeros in increased, passing to a
continuous curve in the limit. The issue that I addressed is the false
notion that the same process, applied to measured samples of a waveform,
reveals details that the actual samples are too few to reveal.
A image made with any lens shows blurs -- Airy disks -- where points
would ideally be; the bigger the lens (window), the smaller the blurs.
When such an image is sampled, zero padding with increasing numbers of
zeros reveals more and more detail about the structure of the blurs, not
detail in the object. This is not to say that there are not heuristics
that allow quite good guesses to me made about the shapes of features
just below the resolution limit, but when the image of a car is no more
than an elongated blob, one can't determine the model, no matter how
many zeros one adds, experts on TV crime shows notwithstanding.
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by Robert Scott●March 9, 20042004-03-09
On 9 Mar 2004 02:48:30 -0800, allnor@tele.ntnu.no (Rune Allnor) wrote:
>
>Exactly what would this "something" be? In this case you made the
>signal yourself, so you know what's in there. Would you be eable to
>say that there are two lines in there (as opposed to one slightly damped
>or otherwise non-perfect sinusoidal) if you did not have this
>prior knowledge?
>
>The term "resolution" is usually taken to mean that one can *resolve*
>two or more components in the spectrum. A sufficient requirement to
>achieve that is that there is space for at least one "small" Fourier
>coefficient between two "large" ones. Working out the details would
>show the lines must be at 2pi/N radians apart in the Z plane.
Although the experiment that I reported was based on analyizing one
noise-free sine wave at a time, I also tried resolving two summed sine
waves very close to the same frequency. The results of this
experiment were not so good. A zero-padding of half the data did seem
to increase the resolution slightly, but when I zero-padded even more,
the two humps blended into one another, producing a single hump
half-way between the two. So I would say that the benefit of
zero-padding is confined only to those cases where you can assume that
only a single frequency is present, there is very little noise, and
you only want to find the frequency of that single sine wave.
-Robert Scott
Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)
Reply by Rune Allnor●March 9, 20042004-03-09
no-one@dont-mail-me.com (Robert Scott) wrote in message news:<4049408e.3506856@news.provide.net>...
> OK, all this speculation finally pushed me over the edge, so I tested
> it, and it works just as I thought it would. Here is my experiment.
>
> I created a time series with a sine wave of exactly half the Nyquist
> frequency (f1 = 1/4 of the sampling frequency) using N=16384 samples
> and computed the power spectrum. Sure enough, there was a nice peak
> at bin 4096. Then I created a time series with a sine wave of a
> frequency of f2 = f1 + 2/16384. Sure enough it had a nice peak at bin
> 4098. So here we have two frequencies, f1 and f2, whose power spectra
> have peaks in bins 4096 and 4098 respectively. Then I started to zap
> the time series to zero past a certain number of samples. First I
> tried 8192 (half the original number of samples). The resulting power
> spectrum still had peaks at bins 4096 and 4098. Then I zapped the
> samples past 6000. Still the peaks were in different bins. I went
> all the way down to 1024 samples (with the remaining 15360 samples
> forced to zero for both frequencies). I still got peaks in those same
> two bins, 4096 and 4098. What was the difference? It was the
> broadness of the peaks. Here are the amplitudes around bin 4096 for
> frequency f1:
>
> Zap samples Previous Peak Next
> past: bin bin bin
>
> 6000 4612 5673 4612
> 2048 1688 1721 1688
> 1024 694 697 694
>
> As you can see, the peaks for the cases with extreme zero-padding are
> very very broad. But if I had run a 1024-point FFT in that last case
> instead of embedding 1024 samples in a zero-padded 16384-point FFT, I
> would have bin spacing only 1/16 as wide, and I certainly would not
> have been able to tell the difference between frequencies f1 and f2 by
> looking only at which bin had the peak amplitude. But here they are,
> still two bins apart. So there is something to this zero-padding
> thing.
Exactly what would this "something" be? In this case you made the
signal yourself, so you know what's in there. Would you be eable to
say that there are two lines in there (as opposed to one slightly damped
or otherwise non-perfect sinusoidal) if you did not have this
prior knowledge?
The term "resolution" is usually taken to mean that one can *resolve*
two or more components in the spectrum. A sufficient requirement to
achieve that is that there is space for at least one "small" Fourier
coefficient between two "large" ones. Working out the details would
show the lines must be at 2pi/N radians apart in the Z plane.
Rune
Reply by Ronald H. Nicholson Jr.●March 9, 20042004-03-09
In article <4046002e$0$3076$61fed72c@news.rcn.com>,
Jerry Avins <jya@ieee.org> wrote:
>Zero padding doesn't increase resolution. It increases the number of
>points in the plot by interpolating. You can do as well with a French
>curve and a practiced eye.
Both correct and incorrect. Theoretically, zero padding won't increase
FFT resolution. But the theoretically correct intervening points are
properly calculated by infinite width (or at least twice the data length
to dump the coeff's which will be multiplied by zero) Sinc reconstruction.
Sinc reconstruction will resolve more inflection points than something
like a cubic polynomial interpolation (roughly what a French curve
approximates). That is why Mr. Scott's experiment was actually resolving
two close humps by zero padding the FFT (given a low enough noise floor).
A full Sinc interpolation reconstruction process will also resolve
more humps and inflection points than a low order polynomial, but at a
much higher computational cost than by just using a zero padded FFT.
So zero padding an FFT is a computationally efficient way of doing
a better interpolation than one can get using a low order polynomial
interpolator. It really doesn't add information, but it does "correct"
the information which is commonly and incorrectly assumed from using
methods such as the aforementioned French curve and a "practiced" eye.
IMHO. YMMV.
--
Ron Nicholson rhn AT nicholson DOT com http://www.nicholson.com/rhn/
#include <canonical.disclaimer> // only my own opinions, etc.
Reply by Jerry Avins●March 6, 20042004-03-06
Adrian Hey wrote:
...
> I'm not sure what you mean by this, but whatever, I'm pretty sure
> my answer for all plausible interpretations is "no" :-)
...
Does my reply to Bob about measure vs. calculate clear this up?
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������