Zero padded FFt

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

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

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.)

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.

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