Jerry Avins wrote:> Bob Cain 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". To contend that the >>> added-in-between (dare I write "interpolated"?) points are what the >>> output of a twice-speed converter would have produced is surely wrong. >>> To argue that they are is to accept Rune's argument as valid, rather >>> than as the reductio-ad-absurdam that he intended. >> >> >> >> If the input signal remains identically band limited, why would they >> be different? >> >> >> Bob > > > An actual resolution increase requires actual data at the original > sampling rate. To resolve signals one Hz apart, you need a second's > worth of suitably bandlimited samples. You propose using half a second's > worth, and "filling in" the missing samples with zeros.For the record, I'm proposing no such thing. Never occured to me. If you've read my other posts in the thread it should be clear that we are discussing the meaning of resolution in two different contexts. What you say is not in question and I don't think it necessasary to show that one context is right and the other wrong because they have different domains of applicability. Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
Zero padded FFt
Started by ●March 3, 2004
Reply by ●March 5, 20042004-03-05
Reply by ●March 5, 20042004-03-05
no-one@dont-mail-me.com (Robert Scott) wrote in message news:<40478127.3394242@news.provide.net>...> On Thu, 4 Mar 2004 10:50:33 -0500, "Clay S. Turner" <CSTurner@WSE.Biz> > wrote: > > >Hello Bob, > > > >I think the arguments center around what we mean by resolution. Certainly > >zero padding will not give us more information than was already contained in > >the original samples. And a lot of people will associate the term resolution > >with information. Imagine we have two sine waves close together in > >frequency, and we collect N samples, and N is such that both sines fit in > >the same spectral bin. Now zero padding is not going to let us tell the two > >frequencies apart. If we wish to resolve the two frequencies, we need to let > >N be bigger. > > That conclusion is not obvious. In fact, I think it may be wrong. If > you have two sine waves that each would give a peak in the power > spectrum in the same bin, there is still some information that could > discriminate between them, even without zero-padding. Namely, you can > estimate the sine frequency by looking at the amplitude of the peak > and taking into account the amplitude in the bins adjacent to the > peak. There are several different interpolation formulas for this, > such as quadratic interpolation. So it stands to reason that if the > two frequencies could be discriminated without zero padding of the FFT > using quadratic interpolation, then perhaps they can be discriminated > with zero padding without quadratic interpolation. Why not? I would > guess that the difference between zero-padding an getting more real > samples to fill out a larger N is that the power spectrum has a more > well-defined peak in the second case, while the zero padding adds some > noise to the first case.I don't understand what you mean, but Clay is absolutely right. The ability to resolve peaks depends on the amount of data available. I did comment on this a couple of days ago in a post that was intended and phrased as a joke. If your argument was to be taken literally, the bogus line of arguments I sketched out would have to be taken literally as well, and that is easily seen to degenerate into an absurdity. I like to use this example to illustrate what really happens: Make a signal with N=8 samples as a sum of two sines with frequencies f1=0.14 fs and f2=0.20 fs (fs is samppling frequency) and unit amplitudes. First, compute the DFT of the raw signal and plot its magnitude versus frequency. Then, zero-pad the signal to a total length of, say, 128. Plot the DFT magnitude of this signal as well. Make sure to map the frequency bands properly. Then, repeat this exercise but with N=32 samples in the original data series. Take some time to contemplate the difference between the magnitude spectra of the zero-padded short sequence and the 32-pt DFT of the long sequence. Rune
Reply by ●March 5, 20042004-03-05
Robert Scott wrote:> On Thu, 04 Mar 2004 21:49:29 -0500, Jerry Avins <jya@ieee.org> wrote: > > >>That's hair splitting. Resolving the frequencies means having separate >>peaks. > > > Yes, and I think that is exactly what would happen if you zero-pad the > time series before doing an FFT. The two sine waves that were not > resolved in the non-padded case could be resolved in the sense that > you mean in the padded case. > > > -Robert Scott > Ypsilanti, Michigan > (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)Now there's a testable assertion. Use as a test signal a pair of equal-amplitude tones 10 Hz apart. Time/frequency duality suggests that six second's worth of observation is needed to distinguish them. Sample at, say, three times the frequency of the higher for three seconds, then FFT. Math shows that the "bins" will be 20 Hz apart, hence unable to resolve the signal as two sinusoids. Now pad the sample sequence to double its length, and FFT again. This time, the "bins" will be 10 Hz apart. You claim that separate peaks will show up. Interesting! With enough added zeros, would you expect to resolve the 1-Hz wow in the tape transport? Is there any limit at all to extending the frequency resolution by adding null data? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 5, 20042004-03-05
Bob Cain wrote:> Jerry Avins wrote: > >> Bob Cain 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". To contend that the >>>> added-in-between (dare I write "interpolated"?) points are what the >>>> output of a twice-speed converter would have produced is surely wrong. >>>> To argue that they are is to accept Rune's argument as valid, rather >>>> than as the reductio-ad-absurdam that he intended. >>> >>> >>> >>> >>> If the input signal remains identically band limited, why would they >>> be different? >>> >>> >>> Bob >> >> >> >> An actual resolution increase requires actual data at the original >> sampling rate. To resolve signals one Hz apart, you need a second's >> worth of suitably bandlimited samples. You propose using half a second's >> worth, and "filling in" the missing samples with zeros. > > > For the record, I'm proposing no such thing. Never occured to me. If > you've read my other posts in the thread it should be clear that we are > discussing the meaning of resolution in two different contexts. > > What you say is not in question and I don't think it necessasary to show > that one context is right and the other wrong because they have > different domains of applicability.Bob, I certainly don't mean to belittle you or to waste time restating the obvious. I seem to have gotten of the track. When you wrote, "there are two disparate meanings to resolution in this case, one being the resolving power of an IR in operation and the other the resolving power in terms of disclosure of information to an observer", I let that go. It was of Adrian that I asked what "exact samples" meant, then you asked how actual samples could differ from interpolated samples if both sets had the same band limit. It became appropriate or repeat that the increased resolution to the eye does not replicate what a closer look at real data would show. Now I'm thoroughly confused. If you don't mean to imply that data interpolated by zero padding is as real as what is gotten by sampling, what did you mean by, "If the input signal remains identically band limited, why would [interpolated samples] be different?" Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 5, 20042004-03-05
Jerry Avins wrote:> > Robert Scott wrote:> Now there's a testable assertion. Use as a test signal a pair of > equal-amplitude tones 10 Hz apart.Well stop right there. You have already at this point gathered (by some unknown/unidentified means) more useful information about the signal than you could ever hope to gain by padding with zeroes. -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! =-----
Reply by ●March 5, 20042004-03-05
jim wrote:> > Jerry Avins wrote: > >>Robert Scott wrote: > > >>Now there's a testable assertion. Use as a test signal a pair of >>equal-amplitude tones 10 Hz apart. > > > Well stop right there. You have already at this point gathered (by some > unknown/unidentified means) more useful information about the signal than you > could ever hope to gain by padding with zeroes. > > -jimDo you refer to my saying that there are two tones, 10 Hz apart? Well, assume that I lied (or not), and try to prove it with the samples. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 5, 20042004-03-05
Jerry Avins wrote:> Do you refer to my saying that there are two tones, 10 Hz apart? Well, > assume that I lied (or not), and try to prove it with the samples. >Assuming you are telling the truth the envelope of the wave form is known with certainty - at least the frequency is. Detecting the phase is the next step. Then after removing the envelope frequency your left with one frequency exactly half way between the original tones. You can just count the cycles of that waveform. If you lied then it won't work. -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! =-----
Reply by ●March 5, 20042004-03-05
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. But I agree that there is nothing magic about zero-padding. You do lose information as you truncate more and more of the signal. In real-world signals where noise is a factor, you soon get to a point where any gains you might get from zero-padding are quickly swallowed up by the noise. Since the peaks are so broad, it doesn't take much noise to shift which bin is the peak. -Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)
Reply by ●March 5, 20042004-03-05
jim wrote:> > Jerry Avins wrote: > > >>Do you refer to my saying that there are two tones, 10 Hz apart? Well, >>assume that I lied (or not), and try to prove it with the samples. >> > > > Assuming you are telling the truth the envelope of the wave form is known with > certainty - at least the frequency is. Detecting the phase is the next step. Then > after removing the envelope frequency your left with one frequency exactly half > way between the original tones. You can just count the cycles of that waveform. If > you lied then it won't work. > > -jimIf 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? Jerry _____________________ * An eight-point saw has seven teeth per inch. -- 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: > > ... > >> 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). The raw (unscaled,unpadded) N point DFT gives you N samples of the Fourier transform at frequencies k.(Fs/N) for k=0,1..N-1. There are ways to calculate samples at other frequencies. Fer instance.. Padding with M trailing zeros and evaluating the N+M point DFT of the padded sequence will give you samples at k.(Fs/(N+M)) for k=0,1..N+M-1. Pre-multiplying x[n] by exp(-j.2.pi.alpha.n/N) before the DFT will give you samples at frequencies (k+alpha).(Fs/N) for k=0,1..N-1. alpha can be any real, but typically you would only be interested in alpha of form i/I for i=0..I-1 where I is a natural number. If x[n] are real you can use symmetry to to reduce the number of complex DFT's (FFT's) you actually need to perform. If you chose alpha=1/4 for real x[n] then you can over sample the Fourier transform by a factor of 2 using just one (complex) N point DFT. Regards -- Adrian Hey
