On Thursday, 21 February 2013 08:49:31 UTC, wond3rboy wrote:> > > > >"kaz" <37480@dsprelated> wrote: > > > > > >> I prefer to get fft without any zero padding. > > > > > >You are idiot. > > > > > >> Zero padding adds a sudden > > >> discontinuity to the signal implying some high frequencies. > > >. > > >With or without zero padding, discontinuity is still there. > > > > > >VLV > > > > > > > > > > > > > > Hello, > > > > Just to clear another point. I wanted to know of any technical reason for > > computing a zero padded FFT. I can think of two, the fact that we are using > > a radix 2 FFT algorithm so we might be required to have the number of > > samples to be a power of 2 or in the second case, we might need better > > visualisation (say read two closely appearing signals from a FFT plot). > > Thanks.Traditionally zero-padding was used to pad out for radix-2 FFTs - that is not so valid now, as there are very many FFTs that are not radix-2 (for instance Matlab and Octave use FFTW which allows arbitrary numbers of samples as input to the FFT, so the widespread practice of zero-padding when using those libraries may be misguided). In some applications when the sampled data have a relationship to the frequencies after transformation, zero-filling can be used to improve spectral accuracy - an example is photometric absorption spectra - here, zero-filling combined with appropriate windowing can offer an advantage, but as usual this is related to the assumed relationship. An important use of zero-filling is to interpolate - by transforming, zero-filling, optionally windowing, and then inverse transforming one can implement specific interpolations into the 'original' data. This can be better than original-domain interpolation both because all sampled data can easily be used for the interpolation and because the FFT-iFFT can be computationally more efficient than original-domain convolution. --------------------- Chris Bore BORES Signal Processing | Kingston University London www.bores.com | www.kingston.ac.uk chris@bore.com | chris.bore@kingston.ac.uk
Online · Live + on demand
February 9-11, 2027
Price goes up Jan 1: register now to lock in today's rate
Register Now →
FFT, zero padding and DFT bins
Started by ●February 19, 2013
Reply by ●February 21, 20132013-02-21
Reply by ●February 21, 20132013-02-21
On Feb 21, 3:49�am, "wond3rboy" <47228@dsprelated> wrote:> >"kaz" <37480@dsprelated> wrote: > > >> I prefer to get fft without any zero padding. > > >You are idiot. > > >> Zero padding adds a sudden > >> discontinuity to the signal implying some high frequencies. > >. > >With or without zero padding, discontinuity is still there. > > >VLV > > Hello, > > Just to clear another point. I wanted to know of any technical reason for > computing a zero padded FFT. I can think of two, the fact that we are using > a radix 2 FFT algorithm so we might be required to have the number of > samples to be a power of 2 or in the second case, we might need better > visualisation (say read two closely appearing signals from a FFT plot). > Thanks.There's a couple of other reasons: 1- Using FFTs to apply an FIR filter to a long data set - the "overlap and add" and the "overlap and save" approaches both require zero padding. 2 - Zero pading the FFT can give you a better estimate of the frequency when there is a single sinusoid present. This is different than resolution - which in most definitions I've seen means being able to detect two sinusoids that are a certain delta frequency apart. Cheers, Dave
Reply by ●February 21, 20132013-02-21
>On Thursday, 21 February 2013 08:49:31 UTC, wond3rboy wrote: >> > >>=20 >> >"kaz" <37480@dsprelated> wrote: >>=20 >> > >>=20 >> >> I prefer to get fft without any zero padding. >>=20 >> > >>=20 >> >You are idiot. >>=20 >> > >>=20 >> >> Zero padding adds a sudden >>=20 >> >> discontinuity to the signal implying some high frequencies. >>=20 >> >. >>=20 >> >With or without zero padding, discontinuity is still there. >>=20 >> > >>=20 >> >VLV >>=20 >> >=20 >>=20 >> > >>=20 >> > >>=20 >> > >>=20 >> Hello, >>=20 >>=20 >>=20 >> Just to clear another point. I wanted to know of any technical reasonfor>>=20 >> computing a zero padded FFT. I can think of two, the fact that we areusi=>ng >>=20 >> a radix 2 FFT algorithm so we might be required to have the number of >>=20 >> samples to be a power of 2 or in the second case, we might need better >>=20 >> visualisation (say read two closely appearing signals from a FFT plot). >>=20 >> Thanks. > >Traditionally zero-padding was used to pad out for radix-2 FFTs - that isn=>ot so valid now, as there are very many FFTs that are not radix-2 (forinst=>ance Matlab and Octave use FFTW which allows arbitrary numbers of samplesa=>s input to the FFT, so the widespread practice of zero-padding when usingt=>hose libraries may be misguided). > >In some applications when the sampled data have a relationship to thefrequ=>encies after transformation, zero-filling can be used to improve spectrala=>ccuracy - an example is photometric absorption spectra - here,zero-filling=> combined with appropriate windowing can offer an advantage, but as usualt=>his is related to the assumed relationship. > >An important use of zero-filling is to interpolate - by transforming,zero-=>filling, optionally windowing, and then inverse transforming one canimplem=>ent specific interpolations into the 'original' data. This can be betterth=>an original-domain interpolation both because all sampled data can easilyb=>e used for the interpolation and because the FFT-iFFT can becomputationall=>y more efficient than original-domain convolution. > >--------------------- >Chris Bore >BORES Signal Processing | Kingston University London >www.bores.com | www.kingston.ac.uk >chris@bore.com | chris.bore@kingston.ac.uk >That seems great. I will look for details on that and study more about the interpolations. Thanks
Reply by ●February 21, 20132013-02-21
"kevin" <kevinjmcgee@netscape.net> wrote:>The above is one of several available on the web. Note Section G on >p. 57 where the author writes about �Minimum Resolution Bandwidth,� >and defines it as: �we would be interested in the minimum separation >between two equal-strength lines such that for an arbitrary spectral >location their spectrum main lobes can be resolved.�Resolution depends on signal to noise ratio only. Infinite SNR = infinite resolution. Vladimir Vassilevsky DSP and Mixed Signal Consultant www.abvolt.com
Reply by ●February 21, 20132013-02-21
On Feb 21, 12:13�pm, "Vladimir Vassilevsky" <nos...@nowhere.com> wrote:> "kevin" <kevinjmc...@netscape.net> wrote: > >The above is one of several available on the web. �Note Section G on > >p. 57 where the author writes about �Minimum Resolution Bandwidth,� > >and defines it as: �we would be interested in the minimum separation > >between two equal-strength lines such that for an arbitrary spectral > >location their spectrum main lobes can be resolved.� > > Resolution depends on signal to noise ratio only. > Infinite SNR = infinite resolution. > > Vladimir Vassilevsky > DSP and Mixed Signal Consultantwww.abvolt.comVlad has his own definition of resolution, The ability to detect two closely spaced sinusoids has nothing to do with SNR - this is also called the Rayleigh resolution. If you want to accurate estimate the frequency of that sinusoid then SNR plays a very important part. Dave
Reply by ●February 21, 20132013-02-21
"Dave" <dspguy2@netscape.net> wrote: "Vladimir Vassilevsky" <nos...@nowhere.com> wrote:>> Resolution depends on signal to noise ratio only. >> Infinite SNR = infinite resolution.>Vlad has his own definition of resolution, The ability to detect two >closely spaced sinusoids has nothing to do with SNR - this is also >called the Rayleigh resolution.As long as SNR permits, it is possible to sepate two sinusoids. The SNR is the only limiting factor.>If you want to accurate estimate the frequency of that sinusoid then >SNR plays a very important part.Resolution is measurement. Vladimir Vassilevsky DSP and Mixed Signal Consultant www.abvolt.com
Reply by ●February 21, 20132013-02-21
On Tuesday, 19 February 2013 22:00:27 UTC, Vladimir Vassilevsky wrote:> "kaz" <37480@dsprelated> wrote: > > > > > I prefer to get fft without any zero padding. > > > > You are idiot.You are a Stupid Expert!> > > > > Zero padding adds a sudden > > > discontinuity to the signal implying some high frequencies. > > . > > With or without zero padding, discontinuity is still there.The DFT is defined on an interval - there is no discontinuity on that interval. Go back to school, loser.> > > > VLV
Reply by ●February 21, 20132013-02-21
On Thursday, 21 February 2013 17:13:20 UTC, Vladimir Vassilevsky wrote:> "kevin" <kevinjmcgee@netscape.net> wrote: > > > > > > >The above is one of several available on the web. Note Section G on > > >p. 57 where the author writes about �Minimum Resolution Bandwidth,� > > >and defines it as: �we would be interested in the minimum separation > > >between two equal-strength lines such that for an arbitrary spectral > > >location their spectrum main lobes can be resolved.� > > > > Resolution depends on signal to noise ratio only. > > Infinite SNR = infinite resolution.You are an idiot!> > > > Vladimir Vassilevsky > > DSP and Mixed Signal Consultant > > www.abvolt.com
Reply by ●February 21, 20132013-02-21
On 2/21/13 3:07 PM, Vladimir Vassilevsky wrote:> "Dave"<dspguy2@netscape.net> wrote: > "Vladimir Vassilevsky"<nos...@nowhere.com> wrote: > >>> Resolution depends on signal to noise ratio only. >>> Infinite SNR = infinite resolution. > >> Vlad has his own definition of resolution, The ability to detect two >> closely spaced sinusoids has nothing to do with SNR - this is also >> called the Rayleigh resolution.just off hand, if measurement time is fixed, this does not seem to be the case, as far as i can tell. i think you can model zero-mean gaussian noise, white but bandlimited to Nyquist (so it has finite variance), add it to the samples that are two sinusoids not far apart and not much louder, make some linear approximations, and come up with an expectation value for the estimation of the number of components and of the component frequencies and amplituded. those results *could* be biased if there is noise. i might guess that the probability of 1 component decreases and the probability of 2 components increases as the noise amplitude increases. i would expect that the continuous expectation value of the number of components increases from 1 to 2 as the noise variance increases. and the variance around that expectation value (whether it's biased or not) should certainly increase as the noise variance increases. that's what i would expect. what does Rayleigh say about that? i dunno what exactly happens.> > As long as SNR permits, it is possible to sepate two sinusoids. > The SNR is the only limiting factor. > >> If you want to accurate estimate the frequency of that sinusoid then >> SNR plays a very important part. > > Resolution is measurement. >ya know, i'm aware sorta of the problem and i know how to understand it in the noiseless context, but in the noisy case i hadn't really thought about it. anyway, Vlad, how do we quantitatively define resolution? is it, given a fixed window width, the minimum separation of frequencies of two sinusoids that does what? have a probability that it's 2 sinusoids equal the probability that it's 1 sinusoid? just curious. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●February 21, 20132013-02-21
On Wed, 20 Feb 2013 22:46:51 -0800 (PST), kevin <kevinjmcgee@netscape.net> wrote:>On Tue, 19 Feb 2013 13:35:53 -0600, "wond3rboy" <47228@dsprelated> >wrote: > > >>Zero padding the signal in the Time domain and computing its FFT results i= >n >>the frequency spectrum being sampled more densely. It does not affect the >>Spectral(Frequency) Resolution of the resulting FFT since the added zeros >>don't matter in the FFT computation. > >You might benefit from studying the well-known Harris paper on >windows: > >http://web.mit.edu/xiphmont/Public/windows.pdf > >The above is one of several available on the web. Note Section G on >p. 57 where the author writes about =93Minimum Resolution Bandwidth,=94 >and defines it as: =93we would be interested in the minimum separation >between two equal-strength lines such that for an arbitrary spectral >location their spectrum main lobes can be resolved.=94 Also note >further down, the statement that begins: =93The problem with this >criteria =85 .=94 > >There are a number of other papers you should study, such as: > >A. H. Nuttal, =93Some Windows with Very Good Sidelobe Behavior,=94 IEEE >Trans. on >Acoustics, Speech and Signal Processing, vol. ASSP-29, no. 1, Feb. >1981, pp. 84-91. > >and: > >R. J. Webster, =93Leakage Regulation in the Discrete Fourier Transform >Spectrum,=94 Proc. >IEEE, vol. 68, no. 10, Oct. 1980, pp. 1339-1341.This is another sad confirmation that even when you have a long-time membership and supposedly appropriate society membership, the paper is inaccessible unless a fee is paid or some other membership is obtained. I've never figured out what society memberships is/are necessary to have access to Proc. IEEE.> >The Webster paper will mess with your head. In it, the author shows >that leakage is a phenomenon of calculation. He shows that, by a >proper choice and placement of a sum-of-cosines window, he can >eliminate leakage beyond (or before) other bins in the spectrum when >confronted with an interfering sinusoid. > >Yet another paper you should get is: > >http://mgasior.web.cern.ch/mgasior/pap/biw2004.pdfInterpolation using parabolic fit to the coefficient magnitudes has significant bias and performs poorly in noise. A more recent development in a simple estimator with good performance at high and low SNR: http://www.eee.metu.edu.tr/~ccandan/pub_dir/FineDopplerEst_IEEE_SPL_June2011.pdf>Pay particular attention to the third paragraph under =93Measurements,=94 >which begins: =93The interpolation gain of 4700 =85 .=94 > >DFT 'resolution' depends on: 1) the specifics of the problem (eg: 1, >2, or 3 sinusoids, strengths, closeness, etc.), 2) what kind of window >you're using, 3) what kind of technique (if any) you're applying (eg: >estimating/subtracting sinusoids), 4) what kind of SNR you're dealing >with. Some approaches for high SNR problems make no sense when >dealing with low SNR problems. > >Without specifics, it's tough to formulate an answer. For simple zero- >padding, you'll get more points in the frequency spectrum, but it >won't necessarily help you answer the question: =93Is that bump in the >spectrum due to one sinusoid, or due to two equal-strength sinusoids >that are so closely spaced that their peaks in the frequency spectrum >have merged?=94 (and if they're not equal-strength, then that opens up >another can of worms). > >Kevin McGeeEric Jacobsen Anchor Hill Communications http://www.anchorhill.com







