>>>>> "Bob" == Bob Cain <arcane@arcanemethods.com> writes:Bob> An illustration of this point just occured to me. It involves Bob> extending the frequency domain function by zeros and taking the Bob> inverse rather than extending the time domain but the principle works Bob> both ways. Bob> Consider the time sequence: Bob> ...+1,-1,+1,-1,+1,+1,-1,+1,-1,+1... Bob> where ... can be of any length, but let's make it big. If you pad the Bob> FFT of that to twice it's length and then take the IFFT you may (or Bob> may not) be surprised at what appears between the original +1,+1 Bob> samples. If ... is infinity then the value that appears in between Bob> will be infinite but those original finite valued samples contain all Bob> the information needed to represent that infinite value and it's still Bob> band limited. Bob> To me this is increasing resolution no matter how it is defined. I Bob> frequently find these kinds of surpises in the low frequency response Bob> of microphone FIR's that are short after I zero extend them to be Bob> long. Convolving the short FIR against a sin sweep verifies those Bob> surprises. How about this? Take N samples of the signal 10*sin(w*t) + sin((w+d)*t) where d is small. Take the FFT of this signal. Can you see the separate peaks? If so, make d small enough so that you can't really see the separate peaks anymore. Now zero-pad the data and take the FFT. Can you see the 2 peaks? Now take 16N samples and compute the FFT. Can you see the peaks now? (If not, take 128N or more samples). In the first case, you haven't increased the resolution. You've just interpolated the original FFT with more samples. The latter case does increase resolution because you can see things that were not there before. This is all rather handwavy, but I think it illustrates the point. Ray
Zero padded FFt
Started by ●March 3, 2004
Reply by ●March 4, 20042004-03-04
Reply by ●March 4, 20042004-03-04
Clay S. Turner wrote:> Hello Bob, > > I think the arguments center around what we mean by resolution.... Clay, Thank you for writing while I was composing my thoughts. You saved me the need to set them in order and wrote better than I could have. The power that interpolating has over our visualization process is often undervalued. That power becomes evident when lofting a ship or large boat. The shape of the hull is specified by relatively few numbers, tables of offsets at the control frames. There will be maybe a dozen such frames in a 90-footer, with offsets -- distances from the central plane -- given at 8 or 10 heights -- waterlines -- on each. All other locations are interpolated from these. They completely specify the hull. Two hulls, built from the same tables by different builders will differ more in the color of the paint than in any other attribute. Shipwrights call their interpolation tool a "limber batten" and use the floor of the loft above the shop to lay out patterns full size. (That work, called "lofting", is one of the few activities I know named for the place where the work is done.) Draftsmen who do similar work on a smaller scale call their interpolating tool a "spline". (A spline almost by definition is limber.) The computer-graphics spline function is named for that tool. It too is a way to connect dots with smooth curves. In my earlier message, "French curve" was a gross oversimplification. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 4, 20042004-03-04
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. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 4, 20042004-03-04
Clay S. Turner 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.Yes, I am only considering it in terms of disclosed information rather than intrinsic information. And by disclosed I mean disclosed to one observing the result of the transform directly. I just consider it important to understand that a sparse plot may not disclose to one looking at it what the behavior of an IR will actually be if it is used as a filter. Zero padding will disclose more and more information to the observer even if it doesn't have any affect on what it does and that information can be surprising and thus of value. So yes 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. Bob -- "Things should be described as simply as possible, but no simpler." A. Einstein
Reply by ●March 4, 20042004-03-04
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. -Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)
Reply by ●March 4, 20042004-03-04
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 -- "Things should be described as simply as possible, but no simpler." A. Einstein
Reply by ●March 4, 20042004-03-04
Robert Scott wrote:> 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. > > > -Robert Scott > Ypsilanti, Michigan > (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)That's hair splitting. Resolving the frequencies means having separate peaks. The same nomenclature is used in optics. Assuming objects of equal brightness, they are resolved if equal-brightness contours in their image is not everywhere concave about the brightest portion. While it's true that any departure from circularity of those contours may well hint that more than one object, that's beside the [quite literal] point. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 4, 20042004-03-04
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? > > > BobAn 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. That will produce points one Hz apart, but with no new data, the frequency resolution remains two Hz. Let's assume that the interpolated points are exactly those that would have been measured. Then there is no reason to actually make the measurement, is there? Interpolation can provide them later. If that's true, we can get our half-second of points in a quarter second, then extend the sequence with a zero-padded FFT. You don't want to go there. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 4, 20042004-03-04
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.)
Reply by ●March 5, 20042004-03-05
"Robert Scott" <no-one@dont-mail-me.com> wrote in message news:4047f7bc.2032635@news.provide.net...> 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.Hello Robert, Why don't you try it? Pick two sines with frequencies of 1000 and 1001 Hz with a sample rate of 8000 Hz. And just let N be 16 samples. Now go and zero pad the data before FFTing and see if you can resolve two separate peaks. I know you won't be sucessful, but I think you will need to convince yourself that this will be the case. If you want a proof then just remember that the DFT (of which an FFT is just a fast way of calculating it) maps sinusoids to periodic sincs. And the spectrum's magnitude will be a linear combination of these periodic sincs, one pair (using a real data) for each original sinusoid. For the case of two sinusoids, the spacing between the two periodic sincs is determined by the delta frequency, sample size N and the sample rate. Zero padding will not change this. All it does is give you more samples of the overlapped periodic sincs, but since we know the analytic solution, we can determine that no amount of zero padding can do this. Play around with plotting two periodic sincs on top of each other and then change the separation until a valley appears between the two peaks. In fact just write the formula for the sum of the two functions with a separtion alpha and find the value of alpha where the valley first forms. Hint find for what value of alpha, the 2nd derivative goes positive (and 1st equals zero) at the point directly between the two peaks. -- Clay S. Turner, V.P. Wireless Systems Engineering, Inc. Satellite Beach, Florida 32937 (321) 777-7889 www.wse.biz csturner@wse.biz
