DSPRelated.com
Forums
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 wond3rboy ●February 19, 2013
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
On Feb 21, 3:49&#4294967295;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
>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 reason
for
>>=20 >> computing a zero padded FFT. I can think of two, the fact that we are
usi=
>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 is
n=
>ot so valid now, as there are very many FFTs that are not radix-2 (for
inst=
>ance Matlab and Octave use FFTW which allows arbitrary numbers of samples
a=
>s input to the FFT, so the widespread practice of zero-padding when using
t=
>hose libraries may be misguided). > >In some applications when the sampled data have a relationship to the
frequ=
>encies after transformation, zero-filling can be used to improve spectral
a=
>ccuracy - an example is photometric absorption spectra - here,
zero-filling=
> combined with appropriate windowing can offer an advantage, but as usual
t=
>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 can
implem=
>ent specific interpolations into the 'original' data. This can be better
th=
>an original-domain interpolation both because all sampled data can easily
b=
>e used for the interpolation and because the FFT-iFFT can be
computationall=
>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
"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 &#4294967295;Minimum Resolution Bandwidth,&#4294967295; >and defines it as: &#4294967295;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.&#4294967295;
Resolution depends on signal to noise ratio only. Infinite SNR = infinite resolution. Vladimir Vassilevsky DSP and Mixed Signal Consultant www.abvolt.com
On Feb 21, 12:13&#4294967295;pm, "Vladimir Vassilevsky" <nos...@nowhere.com>
wrote:
> "kevin" <kevinjmc...@netscape.net> wrote: > >The above is one of several available on the web. &#4294967295;Note Section G on > >p. 57 where the author writes about &#4294967295;Minimum Resolution Bandwidth,&#4294967295; > >and defines it as: &#4294967295;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.&#4294967295; > > Resolution depends on signal to noise ratio only. > Infinite SNR = infinite resolution. > > Vladimir Vassilevsky > DSP and Mixed Signal Consultantwww.abvolt.com
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. If you want to accurate estimate the frequency of that sinusoid then SNR plays a very important part. Dave
"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
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
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 &#4294967295;Minimum Resolution Bandwidth,&#4294967295; > > >and defines it as: &#4294967295;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.&#4294967295; > > > > 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
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."
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.pdf
Interpolation 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 McGee
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com