DSPRelated.com
Forums

Question about DFT

Started by me4dtrade December 7, 2011
Hi everyone,

I have a question about DFT.

Let's say the DFT's outputs are F(m). As we all know the m in the DFT
equation is an integer (bin number). My question is: Can I turn this
integer m to a floating point number? My point is, if I want to do a
1024 point DFT, and just want to examine a specific range of
frequencies (e.g. m = 50 - 51), instead of calculating m[0, 1023], can
I do m[50.000, 50.001, 50.002, .... 51.000], so I may get a very high
frequency resolution? Or it is equivalent to an interpolation?

From the equation of continuous FT, DFT's m is FT's  f, the frequency.
So turning m to a floating point number seems to be reasonable. Isn't
it?

Thanks in advance.

On 8 Des, 00:34, me4dtrade <me4dtr...@gmail.com> wrote:
> Hi everyone, > > I have a question about DFT. > > Let's say the DFT's outputs are F(m). As we all know the m in the DFT > equation is an integer (bin number). My question is: Can I turn this > integer m to a floating point number? My point is, if I want to do a > 1024 point DFT, and just want to examine a specific range of > frequencies (e.g. m =3D 50 - 51), instead of calculating m[0, 1023], can > I do m[50.000, 50.001, 50.002, .... 51.000], so I may get a very high > frequency resolution?
No. The DFT distributes the coefficients evenly around the unit circle in Z domain.
> Or it is equivalent to an interpolation?
I have no idea. The rule of thumb is that you need N samples to get 1/N resolution on the unit circle in Z domain. There are certain versions of the FFT that computes only a limited number of DFT coefficients, if you only are interested in a small bandwidth. But you still need N data points to get 1/N resolution.
> From the equation of continuous FT, DFT's m is FT's =A0f, the frequency. > So turning m to a floating point number seems to be reasonable. Isn't > it?
The DFT and the FT are two different things. Look at the formule> One is an integral while the other is a sum. Rune
me4dtrade <me4dtrade@gmail.com> wrote:

> I have a question about DFT.
> Let's say the DFT's outputs are F(m). As we all know the m in the DFT > equation is an integer (bin number). My question is: Can I turn this > integer m to a floating point number?
You can do a change of variables, changing the units of frequency...
> My point is, if I want to do a > 1024 point DFT, and just want to examine a specific range of > frequencies (e.g. m = 50 - 51), instead of calculating m[0, 1023], can > I do m[50.000, 50.001, 50.002, .... 51.000], so I may get a very high > frequency resolution? Or it is equivalent to an interpolation?
In that case, it is interpolation. The DFT of 1024 points is the 1024 unknowns in 1024 equations. You can't get more out than you put in, except by interpolation.
> From the equation of continuous FT, DFT's m is FT's f, > the frequency. So turning m to a floating point number seems > to be reasonable. Isn't it?
You can consider the DFT as the FT of delta functions at the data points, and periodic boundary conditions. -- glen
On Dec 7, 3:34=A0pm, me4dtrade <me4dtr...@gmail.com> wrote:
> ... > My point is, if I want to do a > 1024 point DFT, and just want to examine a specific range of > frequencies (e.g. m =3D 50 - 51), instead of calculating m[0, 1023], can > I do m[50.000, 50.001, 50.002, .... 51.000], so I may get a very high > frequency resolution? Or it is equivalent to an interpolation? > ...
You can use the Chirp-Z Transform to achieve the effect on bin center frequencies you have described. That is not necessarily a change in "frequency resolution". The shape of the frequency response of each bin will be unchanged from the shape of bins produced by an FFT of the same data, only the center frequencies change.
> ... > So turning m to a floating point number seems to be reasonable. Isn't > it? > ...
"turning m to a floating point number" is not a reasonable description of the processing you seek. Perhaps you should tell us what -you- mean by "frequency resolution" and "interpolation" before anyone tries to answer the question in your terms. Otherwise you will get such quaintly ambiguous glenisms as "You can't get more out than you put in, except by interpolation. " and you may deserve them. Dale B. Dalrymple
On 12/7/2011 7:59 PM, glen herrmannsfeldt wrote:
> You can consider the DFT as the FT of delta functions at the data > points, and periodic boundary conditions. > > -- glen
Glen, What an elegant way to put it! I don't think in all the discussions that I've seen it expressed this way. I've always just thought: this is how it is .. period. What does this imply about "and if you don't" [consider the DFT as the FT of delta functions....etc.]? Fred
On Dec 7, 6:34&#4294967295;pm, me4dtrade <me4dtr...@gmail.com> wrote:
> Hi everyone, > > I have a question about DFT. > > Let's say the DFT's outputs are F(m). As we all know the m in the DFT > equation is an integer (bin number). My question is: Can I turn this > integer m to a floating point number? My point is, if I want to do a > 1024 point DFT, and just want to examine a specific range of > frequencies (e.g. m = 50 - 51), instead of calculating m[0, 1023], can > I do m[50.000, 50.001, 50.002, .... 51.000], so I may get a very high > frequency resolution? Or it is equivalent to an interpolation? > > From the equation of continuous FT, DFT's m is FT's &#4294967295;f, the frequency. > So turning m to a floating point number seems to be reasonable. Isn't > it? > > Thanks in advance.
Yes, you can take m to be a floating-point number as in m[50.000, 50.001, 50.002, .... 51.000] and you will get 1024 numbers out of your DFT program if you have 1024 values of m between 50 and 51 (can't use the FAST Fourier Transform algorithm to compute the DFT, though). The numbers that you get will not be particularly useful in many applications, for example, you can't use them in the "transform method for computing convolutions" and Parseval's theorem does not apply. More to the point, suppose the standard DFT gives you large values for X[50] and X[51] indicating that there is significant signal energy at the frequency corresponding to those bins (or thereabouts). Well, **most** of the 1024 numbers that you obtain from your FPDFT (floating-point DFT) will be quite large, that is, you will not have an "Aha" moment where you will discover that there is a strong signal component **precisely** at the frequency corresponding to m = 50.674 (say) (and very little energy at m = 50.673 or 50.675), and this component is showing up as large values in X[50] and X[51] in your regular DFT. Put another way, instead of an "Aha" moment, you will instead have an "Arrrggggh" moment as in "Why did I waste my time doing this FPDFT?" But, it is a free country (or will be as soon as the size of government is reduced by getting rid of all the coffee drinkers in government), and you can certainly take m to be a floating-point number if you like without anyone stopping you. Dilip Teadrinker
On 12/8/11 11:47 AM, Fred Marshall wrote:
> On 12/7/2011 7:59 PM, glen herrmannsfeldt wrote: >> You can consider the DFT as the FT of delta functions at the data >> points, and periodic boundary conditions.
do the periodic boundary conditions apply in which domain? if only in the frequency domain, that's the DTFT. if both domains, then it's the DFT.
> What an elegant way to put it! I don't think in all the discussions that > I've seen it expressed this way.
it sorta sounds more diplomatic than how i generally insist what the DFT is (as an invertible mapping of one discrete and periodic sequence to another discrete and periodic sequence of the same period), but isn't it equivalent?
> I've always just thought: this is how it is .. period.
really, Fred? you certainly saw it as doing the same sorta thing as the Fourier transform (or series) in that you're representing one function as a collection of sinusoids (lest it be named after someone other than Fourier), no?
> What does this imply about "and if you don't" [consider the DFT as the > FT of delta functions....etc.]?
i think we consider the DFT to be the uniform *sampling* of the FT of a finite set of uniformly-spaced delta functions. what does that sampling of the FT imply back in the domain of those delta functions on the other side of the FT? i'm skating close to the periodic (or ongoing) political or theological or philosophical dispute we have here about the DFT. <<but me still thinks our side is Right: The DFT is one and the same as the Discrete Fourier Series because God made it so and if you don't believe that then yer going to hell fer sher.>> but i guess we shouldn't be burning to the stake the folks who don't see it so. <<tolerance is hard, it's funner to just burn the heretics.>> -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On Dec 8, 8:47&#4294967295;am, Fred Marshall <fmarshallxremove_th...@acm.org>
wrote:
> On 12/7/2011 7:59 PM, glen herrmannsfeldt wrote: > > > You can consider the DFT as the FT of delta functions at the data > > points, and periodic boundary conditions. > > > -- glen > > Glen, > > What an elegant way to put it! &#4294967295;I don't think in all the discussions > that I've seen it expressed this way. > > I've always just thought: this is how it is .. period. > > What does this imply about "and if you don't" [consider the DFT as the > FT of delta functions....etc.]? > > Fred
Fred The statement is very succinct, anyway. How many readers of comp.dsp do you think correctly convert "periodic boundary conditions" to the required assumption that the delta functions can only consist of samples of signals that are sums of components at the frequencies of the basis functions of the DFT? Aperiodic components and components periodic at other frequencies than the DFT's basis functions don't meet the "periodic boundary conditions". Dale B. Dalrymple
On 12/9/2011 9:31 AM, dbd wrote:
> On Dec 8, 8:47 am, Fred Marshall<fmarshallxremove_th...@acm.org> > wrote: >> On 12/7/2011 7:59 PM, glen herrmannsfeldt wrote: >> >>> You can consider the DFT as the FT of delta functions at the data >>> points, and periodic boundary conditions. >> >>> -- glen >> >> Glen, >> >> What an elegant way to put it! I don't think in all the discussions >> that I've seen it expressed this way. >> >> I've always just thought: this is how it is .. period. >> >> What does this imply about "and if you don't" [consider the DFT as the >> FT of delta functions....etc.]? >> >> Fred > > Fred > > The statement is very succinct, anyway. How many readers of comp.dsp > do you think correctly convert "periodic boundary conditions" to the > required assumption that the delta functions can only consist of > samples of signals that are sums of components at the frequencies of > the basis functions of the DFT? Aperiodic components and components > periodic at other frequencies than the DFT's basis functions don't > meet the "periodic boundary conditions". > > Dale B. Dalrymple
Dale, Yes, I understand and agree to a point. Except for "when?". Let us say that some signal with aperiodic components (relative to our intended DFT) is sampled for a long time. Now let us select some N or temporal window and do a DFT on those samples. The result is a length N discrete transform (complex usually). Now we have a transform pair. At this stage there are no aperiodic components .. even though the original aperiodic components may have affected the original samples. In effect what we have is a *new* periodic sequence which deviates from the original *underlying* periodic components. Actually this occurred when we selected N. When we select the sample rate and N, we are one way or another asserting its periodicity. Well, I should add I guess "if we are going to compute a DFT". I suppose there are other applications of those N samples that wouldn't suggest such a thing. Perhaps another way to put it is: - once you've sampled there's no going back .. perfect reconstruction being the only counter example that I can think of. - once you've windowed i.e. selected N samples .. except for perhaps things like concatenation of sequences with their neighboring samples .. there's no going back. - once you've DFT'd, you've put things in a context where everything is periodic and there's no going back. I'm not trolling for arguments or counter examples. Maybe these assertions are just a "mind set". Without "proof" I think it's a useful framework. So, anyway, that's how I deal with the question of aperiodic components .. which are only evident before N is selected. And, N, conceptually at least, becomes a period of something that was originally not periodic when we consider that we allow a discrete version of the FT of those samples. Obviously we can compute the FT of the N samples and get a continuous transform. Then the temporal periodicity wouldn't come up. But that's not what we do. So, I call "what we do" a context. Then there are more rigorous mathematical treatments to say the same thing but I rather think that this somewhat philosophical treatment is worthwhile. And, of course, we all know that we can select "good" values of the sample interval T and number of samples N and "bad" values of the same such that some strong periodic component is grabbed with an integer plus 1/2 of a period is in the window. That's pretty "aperiodic" and the underlying (i.e. original) boundary conditions are ugly and the resulting DFT is ugly too. But calling the DFT "ugly" is a perspective while saying "it is what it is", I think, is more to the point. Agreed? I can't comment on "many readers". Perhaps so. Fred
On 12/10/11 11:13 AM, Fred Marshall wrote:
> On 12/9/2011 9:31 AM, dbd wrote: >>> On 12/7/2011 7:59 PM, glen herrmannsfeldt wrote: >>> >>>> You can consider the DFT as the FT of delta functions at the data >>>> points, and periodic boundary conditions. >> >> The statement is very succinct, anyway. How many readers of comp.dsp >> do you think correctly convert "periodic boundary conditions" to the >> required assumption that the delta functions can only consist of >> samples of signals that are sums of components at the frequencies of >> the basis functions of the DFT?
i certainly don't make that assumption. how have you determined that it is "required"?
>> Aperiodic components and components >> periodic at other frequencies than the DFT's basis functions don't >> meet the "periodic boundary conditions".
no kidding. that's why the DTFT and the DFT ain't the same thing (whereas the DFS and DFT *are* the same thing).
> > Let us say that some signal with aperiodic components (relative to our > intended DFT) is sampled for a long time. > > Now let us select some N or temporal window and do a DFT on those > samples. The result is a length N discrete transform (complex usually). > > Now we have a transform pair. At this stage there are no aperiodic > components .. even though the original aperiodic components may have > affected the original samples. In effect what we have is a *new* > periodic sequence which deviates from the original *underlying* periodic > components.
we need to be specific about what "we have" and what is deviating from the original. as i can observe it, *nothing* is deviating from the original if your entire universe is only those N samples. but if the entire universe is only those N samples, then it doesn't make any sense to talk of those "other" components, be they aperiodic or having a period other than N. in a universe of only N samples, there is no (and have never been) any meaning to any other components. but, if you think of these N samples as a sorta "pocket universe" (sorry to borrow from cosmology, Glen and Clay will probably wince) surrounded by an infinite sea of zeros, then (if you FT) you have the DTFT. the spectrum is continuous, but repeats every 2*pi. the spectrum is not zero outside of the [-pi +pi) interval, but if you make it so (in the mind of your brain or some other mathematician's brain), then those N samples are no longer attached to N dirac deltas, but are attached to N sinc() functions that go on forever and there is no periodicity in that domain. not yet. NOW (picking up on Fred's "when"), whether you zeroed the spectrum outside of [-pi +pi) or not (i don't care if you do or not), if you uniformly sample that spectrum with N samples from -pi to just under +pi (or from 0 to just under 2*pi, i don't really care), you have the DFT. and the act of sampling that spectrum *does* *necessarily* cause the periodic extension of the original data, the N samples. this is how you go from the one valid concept that "the DTFT is what you get when you attach N delta functions to the N original data points (uniformly spaced) and the DFT is what you get when you sample the DTFT result" to the other equally valid (but i say is *more* fundamental) that "the DFT invertibly maps one discrete and periodic sequence of numbers to another discrete and periodic sequence of numbers of the same period." ...
> So, anyway, that's how I deal with the question of aperiodic components > .. which are only evident before N is selected. And, N, conceptually at > least, becomes a period of something that was originally not periodic > when we consider that we allow a discrete version of the FT of those > samples. > > Obviously we can compute the FT of the N samples and get a continuous > transform. Then the temporal periodicity wouldn't come up.
not yet...
> But that's not what we do.
... that's right. what we do is *sample* the DTFT and the undeniable effect of that is the periodic extension of the
> So, I call "what we do" a context. Then there are more > rigorous mathematical treatments to say the same thing but I rather > think that this somewhat philosophical treatment is worthwhile.
it's also mathematically correct. and something that the periodicity deniers just don't seem to get. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."