Question about DFT

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."