Hello, I am trying to determine the theoretical frequency resolution of the DFT. I am sub-sampling an RF sign wave with a 8 bit ADC. I understand the restrictions of the FFT's frequency resolution due to the nature of the algorithm, but a DFT can compare the sampled sine wave to an infinite amount different frequencies and take the best fit. I think the answer to this question has something to do with the resolution of the ADC (8 bit in my case), acquisition time, the amount of samples, and noise in the system. I have yet to see a clear mathematical formula to explain this. Please remember that I am sampling a filtered RF sine wave that is AC coupled into the ADC, and I already know roughly the frequency of the acquired sine wave. I have all the processing time in the world so a DFT is ideal for this situation. Thanks to all that respond.
Frequency Resolution of the DFT
Started by ●October 29, 2003
Reply by ●October 29, 20032003-10-29
Thomas Magma wrote:> Hello, > > I am trying to determine the theoretical frequency resolution of the DFT. I > am sub-sampling an RF sign wave with a 8 bit ADC. I understand the > restrictions of the FFT's frequency resolution due to the nature of the > algorithm, but a DFT can compare the sampled sine wave to an infinite amount > different frequencies and take the best fit. > > I think the answer to this question has something to do with the resolution > of the ADC (8 bit in my case), acquisition time, the amount of samples, and > noise in the system. I have yet to see a clear mathematical formula to > explain this. Please remember that I am sampling a filtered RF sine wave > that is AC coupled into the ADC, and I already know roughly the frequency of > the acquired sine wave. I have all the processing time in the world so a DFT > is ideal for this situation. > > Thanks to all that respond.I can't connect with comparing the sampled signal with an infinite number of frequencies. How is that conceivable with a finite amount of computation? Frequency is the reciprocal of period. The frequency resolution of a Fourier transform is the reciprocal of the time encompassed by the samples fed to it. (When sampling for one second, frequencies of one Hz can be resolved. When sampling for a minute, 1/60th Hz can be resolved. Assuming always, that the Nyquist criterion is met. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 29, 20032003-10-29
Jerry Avins wrote:> Thomas Magma wrote: > >> Hello, >> >> I am trying to determine the theoretical frequency resolution of the >> DFT. I >> am sub-sampling an RF sign wave with a 8 bit ADC. I understand the >> restrictions of the FFT's frequency resolution due to the nature of the >> algorithm, but a DFT can compare the sampled sine wave to an infinite >> amount >> different frequencies and take the best fit. >> >> I think the answer to this question has something to do with the >> resolution >> of the ADC (8 bit in my case), acquisition time, the amount of >> samples, and >> noise in the system. I have yet to see a clear mathematical formula to >> explain this. Please remember that I am sampling a filtered RF sine wave >> that is AC coupled into the ADC, and I already know roughly the >> frequency of >> the acquired sine wave. I have all the processing time in the world so >> a DFT >> is ideal for this situation. >> >> Thanks to all that respond. > > > I can't connect with comparing the sampled signal with an infinite > number of frequencies. How is that conceivable with a finite amount of > computation? > > Frequency is the reciprocal of period. The frequency resolution of a > Fourier transform is the reciprocal of the time encompassed by the > samples fed to it. (When sampling for one second, frequencies of one Hz > can be resolved. When sampling for a minute, 1/60th Hz can be resolved. > Assuming always, that the Nyquist criterion is met. > > JerryI neglected your question (surmise?) about converter resolution. With infinite converter accuracy, a DFT's frequency resolution is (sample frequency)/(number of samples). Noise and finite converter accuracy and resolution keep that limit from being reached. It takes good measurements to distinguish a 5/16-18 bolt from am M8-1.4. Thin nuts will fit either, but thicker ones -- the analog of longer sample times -- won't. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 29, 20032003-10-29
All an FFT does is multiple a known frequency (sine table) to an unknown frequency (sampled data) and plot the real/imaginary vector magnitude of each result. An FFT quantitively increments the "known" frequency part which limits the frequency resolution. A DFT is not restricted by this quantitive increment and can increment it's known frequency on a much more finite scale resulting in a higher frequency resolution. Theoretically you should be able to achieve infinite frequency resolution from only two samples of a sine wave given that you are sampling a perfect sine wave with no noise and are using an ADC with 2^infinite resolution, and also you know roughly the frequency so as to eliminate the images. "Jerry Avins" <jya@ieee.org> wrote in message news:bnp80a$5vj$1@bob.news.rcn.net...> Thomas Magma wrote: > > > Hello, > > > > I am trying to determine the theoretical frequency resolution of theDFT. I> > am sub-sampling an RF sign wave with a 8 bit ADC. I understand the > > restrictions of the FFT's frequency resolution due to the nature of the > > algorithm, but a DFT can compare the sampled sine wave to an infiniteamount> > different frequencies and take the best fit. > > > > I think the answer to this question has something to do with theresolution> > of the ADC (8 bit in my case), acquisition time, the amount of samples,and> > noise in the system. I have yet to see a clear mathematical formula to > > explain this. Please remember that I am sampling a filtered RF sine wave > > that is AC coupled into the ADC, and I already know roughly thefrequency of> > the acquired sine wave. I have all the processing time in the world so aDFT> > is ideal for this situation. > > > > Thanks to all that respond. > > I can't connect with comparing the sampled signal with an infinite > number of frequencies. How is that conceivable with a finite amount of > computation? > > Frequency is the reciprocal of period. The frequency resolution of a > Fourier transform is the reciprocal of the time encompassed by the > samples fed to it. (When sampling for one second, frequencies of one Hz > can be resolved. When sampling for a minute, 1/60th Hz can be resolved. > Assuming always, that the Nyquist criterion is met. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > ����������������������������������������������������������������������� >
Reply by ●October 29, 20032003-10-29
Jerry Avins wrote:> > Frequency is the reciprocal of period. The frequency resolution of a > Fourier transform is the reciprocal of the time encompassed by the > samples fed to it. (When sampling for one second, frequencies of one Hz > can be resolved. When sampling for a minute, 1/60th Hz can be resolved.No, that's the frequency *spacing* for the Fourier frequencies. One can resolve frequencies much closer than that if the S/N is high enough. The DFT evaluated at non-Fourier frequencies must be used, and if the signal has harmonics it has to be massaged in a nontrivial way. For a single sinusoid with Gaussian noise, you'll find the formulas you need by looking up parametric frequency estimation. I think the simplest way to get at them is from the Bayesian approach of Jaynes and Bretthorst, though there are more conventional approaches. A quick reference for the needed formulas is Bretthorst's book at http://bayes.wustl.edu/ He also shows what to do if you have harmonics (and I summarize some of the algorithm in http://www.museweb.com/bha.pdf). The standard forumulas assume a single sinusoid and Gaussian noise with known sigma. For your case, presuming the only "noise" is from the converter, I'd use the standard sqrt(12) formula to get an equivalent sigma from your ADC resolution and plug that into the formula. It won't be exact, but it should be in the ballpark of what you can hope to achieve. -Tom -- To respond by email, replace "somewhere" with "astro" in the return address.
Reply by ●October 30, 20032003-10-30
Thomas Magma wrote:> All an FFT does is multiple a known frequency (sine table) to an unknown > frequency (sampled data) and plot the real/imaginary vector magnitude of > each result. An FFT quantitively increments the "known" frequency part > which limits the frequency resolution. A DFT is not restricted by this > quantitive increment and can increment it's known frequency on a much more > finite scale resulting in a higher frequency resolution.Where does that notion come from? It isn'r valid. "DFT" stands for "discrete Fourier transform"; an operation on a series of numbers, rather than a continuous function. FFTs -- fast Fourier transforms -- are a a group of algorithms that perform DFTs with good computational efficiency. They don't differ from DFTs, they _are_ DFTs.> Theoretically you should be able to achieve infinite frequency resolution > from only two samples of a sine wave given that you are sampling a perfect > sine wave with no noise and are using an ADC with 2^infinite resolution, and > also you know roughly the frequency so as to eliminate the images.If you know that you have a pure sinusoid, you don't need an FT. That's a different (and not usually useful) subject. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 30, 20032003-10-30
Tom Loredo wrote:> Jerry Avins wrote: > >>Frequency is the reciprocal of period. The frequency resolution of a >>Fourier transform is the reciprocal of the time encompassed by the >>samples fed to it. (When sampling for one second, frequencies of one Hz >>can be resolved. When sampling for a minute, 1/60th Hz can be resolved. > > > No, that's the frequency *spacing* for the Fourier frequencies. One > can resolve frequencies much closer than that if the S/N is high > enough. The DFT evaluated at non-Fourier frequencies must be used, > and if the signal has harmonics it has to be massaged in a nontrivial > way.You can indeed resolve more detail, but with techniques that extend Fourier transforms. The transform itself doesn't go there. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●October 30, 20032003-10-30
Jerry Avins wrote:> If you know that you have a pure sinusoid, you don't need an FT. That's > a different (and not usually useful) subject.The case where the signal contains a *bounded* number of (possibly decaying, i.e. complex-frequency) pure sinusoids is, actually, quite an important and well-studied case. (e.g. to extract eigenfrequencies and damping rates from time series, either from experiment or from simulation.) As you say, in that case, you don't want a Fourier transform per se, since the FT assumes that you know basically nothing about your signal. A beautiful and very readable paper on the subject is: V. A. Mandelshtam and H. S. Taylor, "Harmonic inversion of time signals," J. Chem. Phys., vol. 107, no. 17, p. 6756-6769 (Nov. 1 1997). See also erratum, ibid, vol. 109, no. 10, p. 4128 (Sep. 8 1998). (Note that directly doing a least-squares fit is usually a very poorly conditioned approach.) Cordially, Steven G. Johnson
Reply by ●October 30, 20032003-10-30
Maybe I should be leaving Jean Fourier's name out of this to try to explain myself. I'm talking about multiplying a band of frequencies (spectrum analysis with a fixed span) with sampled data of a single sinusoidal frequency and plotting the result and then determining frequency resolution/accuracy. So lets say I sampled a 10MHz sinusoidal signal which I know is accurate to +/- 5 ppm. My reference to my ADC is known and accurate and I trying to determine the actual frequency of the 10MHz. So I will want to analyze a span of 100 Hz centered around the 10MHz which is equivalent to the +/-5ppm. Without using a FFT, I can mathematical generate any frequency in that band and multiply it with my captured data and then simply take the greatest vector magnitude to determine the actual frequency of the 10MHz signal. What I'm trying to determine is the limitations of this approach. If I choose to break that 100 Hz into 100,1000, or 10000 discrete frequencies and multiply it with my data, what is the advantage.? And where does the ADC bit resolution, amount of samples and sample length fit in? I hope that I am making myself clear enough as to what I am trying to achieve. "Jerry Avins" <jya@ieee.org> wrote in message news:bnq3dq$9tt$1@bob.news.rcn.net...> Thomas Magma wrote: > > > All an FFT does is multiple a known frequency (sine table) to an unknown > > frequency (sampled data) and plot the real/imaginary vector magnitude of > > each result. An FFT quantitively increments the "known" frequency part > > which limits the frequency resolution. A DFT is not restricted by this > > quantitive increment and can increment it's known frequency on a muchmore> > finite scale resulting in a higher frequency resolution. > > Where does that notion come from? It isn'r valid. "DFT" stands for > "discrete Fourier transform"; an operation on a series of numbers, > rather than a continuous function. FFTs -- fast Fourier transforms -- > are a a group of algorithms that perform DFTs with good computational > efficiency. They don't differ from DFTs, they _are_ DFTs. > > > Theoretically you should be able to achieve infinite frequencyresolution> > from only two samples of a sine wave given that you are sampling aperfect> > sine wave with no noise and are using an ADC with 2^infinite resolution,and> > also you know roughly the frequency so as to eliminate the images. > > If you know that you have a pure sinusoid, you don't need an FT. That's > a different (and not usually useful) subject. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > ����������������������������������������������������������������������� >
Reply by ●October 30, 20032003-10-30
Jerry Avins wrote:> > You can indeed resolve more detail, but with techniques that extend > Fourier transforms. The transform itself doesn't go there.I think you need to be more precise with your terminology. The DFT is defined as a sum evaluated only at the Fourier frequencies. But the sum itself (which some authors call the discrete time Fourier transform) can be evaluated at any frequencies between the Fourier frequencies. There is even a fast algorithm to do it (using the fractional FFT). So if by "the transform" you mean the DFT, you are right, and since the OP phrased his question specifically in reference to the DFT, I'll grant you that. But if (as one might assume from your previous sentence) you are referring to Fourier transforms in general, you can evaluate them at any desired frequency, even for a finite, discretely sampled time series. In any case, the OP's question was about frequency resolution, and the resolution of a frequency estimator calculated using Fourier methods for a given data set has little to do with the Fourier spacing. You need to use at least that fine a spacing to *find* the peak in the periodogram, but the actual peak location provides a frequency estimate whose resolution depends on the S/N and can easily be much finer than the Fourier spacing. -Tom -- To respond by email, replace "somewhere" with "astro" in the return address.
