Jerry Avins wrote:> > If you want to look at it that way, we don't need any samples at all. > The usual case is about how much information do the samples themselves > encode, and the methods one might use to extract it. There is a moral to > the story that ends, "If you tell me how high the building is, I'll give > you this damn barometer", but not the one we want to draw here. To avoid > this foolishness, I rephrase my question: > > The file contains 3,999 samples* taken at 8,000 samples per second the > sampled waveform consists of one or more sinusoids in the vicinity of 2 > KHz; if more, all amplitudes are the same. There may be noise, but the > signal power exceeds noise power by at least 30 dB. No frequency differs > from any other by more than 10 Hz. Analyzing those samples by any means > you choose, what is the best description you are able to assert about > the original waveform? Will zero padding help you to know some of the > finer details? >Sorry, didn't mean to hose your barometer. The point I was making was that you had essentially removed all uncertainty from the question (other than the possibility that you were lying). Anyone who might try that would find that they could resolve said frequencies. They might then come to the conclusion that zero padding had something to do with that. -jim -----= Posted via Newsfeeds.Com, Uncensored Usenet News =----- http://www.newsfeeds.com - The #1 Newsgroup Service in the World! -----== Over 100,000 Newsgroups - 19 Different Servers! =-----
Zero padded FFt
Started by ●March 3, 2004
Reply by ●March 6, 20042004-03-06
Reply by ●March 6, 20042004-03-06
Adrian Hey wrote:> Jerry Avins wrote: > > >>Adrian Hey wrote: >> >> ... >> >> >>>Of the three obvious ways I can think of to calculate more densely >>>spaced exact samples, the zero padding technique is the second >>>most efficient but probably the easiest to implement for powers >>>of 2. >> >>I have to ask what you mean by "exact samples". > > > I mean exact samples of the Fourier transform of our N samples, > call them x[n], n=0,1..N-1. To be more precise, exact samples of > the Fourier transform of this function.. > > N-1 > x(t)=SUM x[n].delta(t-(n/Fs)) where Fs is the sampling frequency > n=0 > > The Fourier transform of this is continuous and periodic (with period Fs).... Do you also say that the exact samples described here are what extended sampling of the actual waveform would measure (within the limit imposed be noise and the ability to discriminate), or only that they exactly fit the summation? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 6, 20042004-03-06
Jerry Avins wrote:> Adrian Hey wrote: > >> Jerry Avins wrote: >> >> >>> Adrian Hey wrote: >>> >>> ... >>> >>> >>>> Of the three obvious ways I can think of to calculate more densely >>>> spaced exact samples, the zero padding technique is the second >>>> most efficient but probably the easiest to implement for powers >>>> of 2. >>> >>> >>> I have to ask what you mean by "exact samples". >> >> >> >> I mean exact samples of the Fourier transform of our N samples, >> call them x[n], n=0,1..N-1. To be more precise, exact samples of >> the Fourier transform of this function.. >> >> N-1 >> x(t)=SUM x[n].delta(t-(n/Fs)) where Fs is the sampling frequency >> n=0 >> >> The Fourier transform of this is continuous and periodic (with period >> Fs). > > > ... > > Do you also say that the exact samples described here are what extended > sampling of the actual waveform would measure (within the limit imposed > be noise and the ability to discriminate), or only that they exactly fit > the summation?Jerry, here is where our focus splits. You are thinking in terms of sections of a continuous signal where I am thinking in terms of the analysis of an FIR. In the latter context, zero extension of that FIR followed by an FFT will disclose more points in the underlying continuous frequency domain function (or zero extension of the sampled frequency domain function will disclose more points of the continuous time domain function.) The value of those new points are strictly valid and may not be obvious at all from examining a smaller set of points. This is all I am trying to say and while it doesn't correspond to your definition of higher resolution it does correspond to the vernacular use of the word and I'm not sure what else to call it. Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
Reply by ●March 6, 20042004-03-06
Jerry Avins wrote:> Adrian Hey wrote: > >> Jerry Avins wrote: >> >> >>>Adrian Hey wrote: >>> >>> ... >>> >>> >>>>Of the three obvious ways I can think of to calculate more densely >>>>spaced exact samples, the zero padding technique is the second >>>>most efficient but probably the easiest to implement for powers >>>>of 2. >>> >>>I have to ask what you mean by "exact samples". >> >> >> I mean exact samples of the Fourier transform of our N samples, >> call them x[n], n=0,1..N-1. To be more precise, exact samples of >> the Fourier transform of this function.. >> >> N-1 >> x(t)=SUM x[n].delta(t-(n/Fs)) where Fs is the sampling frequency >> n=0 >> >> The Fourier transform of this is continuous and periodic (with period >> Fs). > > ... > > Do you also say that the exact samples described here are what extended > sampling of the actual waveform would measure (within the limit imposed > be noise and the ability to discriminate),I'm not sure what you mean by this, but whatever, I'm pretty sure my answer for all plausible interpretations is "no" :-)> or only that they exactly fit the summation?I say they exactly fit the Fourier transform of the above summation, which is also a summation.. N-1 X(f) = SUM x[n].exp(-j.2.pi.n.f/Fs) n=0 The DFT of x[n] (let's call it X'(k)) gives you.. N-1 X'(k) = X(k.Fs/N) = SUM x[n].exp(-j.2.pi.n.k/N) for k=0,1..N-1 n=0 But there's nothing particularly special about those frequencies. If we're looking at the spectrum of x(t), rather than it's Fourier transform X(f), we need to oversample X(f) by a factor of 2 (I.E. have 2.N samples of X(f) spaced at intervals of Fs/(2.N)) just to ensure that the spectrum is adequately sampled. We can't reconstruct (|X(f)|^2) from only the N spectrum samples given by (|X'(k)|^2). Regards -- Adrian Hey
Reply by ●March 6, 20042004-03-06
Bob Cain wrote:> Jerry Avins wrote:...>> Do you also say that the exact samples described here are what >> extended sampling of the actual waveform would measure (within the >> limit imposed be noise and the ability to discriminate), or only that >> they exactly fit the summation? > > > Jerry, here is where our focus splits. You are thinking in terms of > sections of a continuous signal where I am thinking in terms of the > analysis of an FIR.... That explains it all. I thought I was confining myself to how this thread started, and never considered another context for my remarks.> In the latter context, zero extension of that FIR > followed by an FFT will disclose more points in the underlying > continuous frequency domain function (or zero extension of the sampled > frequency domain function will disclose more points of the continuous > time domain function.)Of course.> The value of those new points are strictly valid > and may not be obvious at all from examining a smaller set of points. > This is all I am trying to say and while it doesn't correspond to your > definition of higher resolution it does correspond to the vernacular use > of the word and I'm not sure what else to call it.I suspect the trade needs a more discriminating vocabulary, at least to distinguish these two cases. All along, I meant by "resolution" what an optician calls "resolving power"; the ability to distinguish close measured objects as separate. It relates to measurement (and analysis of measured data) and not at all to calculation per se. Jerry P.S. In optics, the larger an instrument's entrance pupil -- think "window" -- the better its resolving power. When a bright line in a spectrum obscures a neighboring dim one, reducing a spectroscope's round aperture to an inscribed square with its diagonal parallel to the instrument's slit can sometimes allow the dim line to be resolved. I leave it as a puzzle to the reader to "resolve" this seeming paradox. -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●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. �����������������������������������������������������������������������
Reply by ●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 ●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 ●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 ●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. �����������������������������������������������������������������������
