Question about DFT

[[forgot to add a point i had intended.]]

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.  [[and, 
at this point there likely *is* some deviation of what "we have" and the 
original underlying periodic (of some different period than N) or 
aperiodic components.]]  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."

On Dec 10, 8:13 am, Fred Marshall <fmarshallxremove_th...@acm.org>
wrote:
> 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.
...
> > Fred
>
> > The statement is very succinct,
> > ...
> > 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.

Yes, there are other applications of not just the N samples but the
very same DFT coefficients. The algorithms know as 'frequency
reassignment' calculate the amplitude, center frequency and phase of
linear FM components from the same DFT coefficients. The N-periodic
components are a subset of those linear FMs. So are periodic, but not
N-periodic components. So, while you, as the analyst may chose to
interpret via an N-periodic assumption, the use of DFT coefficients
and selection of N and Fs and the signals to apply them to, do not
need to depend on any prefered periodic assumption.

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

Choosing to analyze and reason from only a single block of N samples
is sometimes a necessity and sometimes just the analyst's choice, but
it is a position of ignorance with respect to the properties of the
original sequence whether voluntary or not. Analysts are free to chose
assumptions to deal with that ignorance. You have your favorite
assumption and I have often used it as well. It has the advantage of
requiring the least additional processing after the DFT and is often
good enough for applications.
>
> 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.
We often try to pick N and Fs so that the assumption of periodicity is
valid. Some instruments generate Fs to be synchronous with the
periodicities of the signal. There is literature on resampling to make
the Fs synchronous. It is often useful to make the assumption of
periodiciy whether it is valid or not. My point is that the assumption
is one possible interpretation (among others) by the analyst to cope
with the consequences of examining only the analysis of one block of N
samples. At the cost of further analysis of the N DFT coefficients,
the assumption may not be necessary, useful, or appropriate.
>
> 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.

In addition to the algorithms already suggested for application to the
N DFT coefficients, the aperiodic components are also accesible to the
analyst after N is selected by analyzing adjacent blocks of N samples
and comparing magnitude and phase. Components that differ between the
blocks are not N-periodic. (If the magnitudes are the same, the
component may be periodic with period other than N.) If the components
are identical, the components are candidates for periodicity. In
theory, it would be necesary to analyze all blocks to prove
periodicity. In practice it is often adequate  to make the distinction
between aperiodic or close-enough to periodic by comparing two or few
blocks. In fact, until you do this there is no basis other than
assumption, as stated by Glen's formulation or construction of the
original time sequence by periodic extension by the analyst, as O&S do
in their examples, for the periodic assumption. Well, in the
construction case, the original sequence is defined by periodic
extension, so the DFT and assumptions have nothing to do with it. But
the assumption is convenient and often useful so it is often made
without any basis.

> 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.
>
It a choice available to the analyst. It is both a choice of context
and a choice of interpretation within that context.

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

Ugly is your word, not mine. The DFT coefficients can still be used to
calculate the frequency, ampltude and phase of the 'plus a 1/2'
frequency component, which demonstrates that the assumption of N-
periodicity is not a characteristic of the DFT and the coefficients it
calculates, but one of many interpretations available to the analyst
and one that can be usefully ignored when chosing how to analyze DFT
coefficients. Is that what you mean by ugly?
> ...

Dale B. Dalrymple

On Dec 10, 10:23�am, robert bristow-johnson
<r...@audioimagination.com> wrote:
>...
>
> it's also mathematically correct. &#4294967295;and something that the periodicity
> deniers just don't seem to get.
>
> r b-j                  r...@audioimagination.com
>
> "Imagination is more important than knowledge."

There are no "periodicity deniers". There are only those deniers who
know only a single small view of the world and from lack of
imagination would deny others the use of many other valid useful
world views.

Dale B. Dalrymple

On 12/10/2011 12:42 PM, dbd wrote:
>> 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.
> Ugly is your word, not mine. The DFT coefficients can still be used to
> calculate the frequency, ampltude and phase of the 'plus a 1/2'
> frequency component, which demonstrates that the assumption of N-
> periodicity is not a characteristic of the DFT and the coefficients it
> calculates, but one of many interpretations available to the analyst
> and one that can be usefully ignored when chosing how to analyze DFT
> coefficients. Is that what you mean by ugly?
>> >  ...
> Dale B. Dalrymple

Dale,

Well, let's see .. Yes, I introduced "ugly" to suggest the nature of the 
continous FT of what's in the temporal window .. the spectral spreading 
that's evident in that case.  I didn't really say that but it's what I 
was imagining.

So, we start with a rectangular window of, let's say for illumination, M 
+ 1/2 periods of a sinusoid.  I guess it doesn't matter if we sample it 
before or after windowing although if we sample it after windowing then 
the sample rate would be considered to be "too low" because of the sharp 
edges at the ends which suggests an issue with the boundary conditions. 
  But, we accept the aliasing it causes by calling it something else: 
"spectral spreading" or "leakage".  Is it true that spectral spreading, 
being continuous is somehow "more OK" than aliasing of a spectral line 
from one frequency to another?  Seems like it, eh?  And, how "ugly" is 
*that*?  Depends on the eye of the beholder I guess.

But, without the 1/2 period, the boundary conditions are smooth and 
there is no aliasing / spectral spreading.

Fred

On Dec 10, 1:50&#4294967295;pm, Fred Marshall <fmarshallxremove_th...@acm.org>
wrote:

> ...
> So, we start with a rectangular window of, let's say for illumination, M
> + 1/2 periods of a sinusoid. &#4294967295;I guess it doesn't matter if we sample it
> before or after windowing although if we sample it after windowing then
> the sample rate would be considered to be "too low" because of the sharp
> edges at the ends which suggests an issue with the boundary conditions.
> &#4294967295; But, we accept the aliasing it causes by calling it something else:
> "spectral spreading" or "leakage". &#4294967295;Is it true that spectral spreading,
> being continuous is somehow "more OK" than aliasing of a spectral line
> from one frequency to another? &#4294967295;Seems like it, eh? &#4294967295;And, how "ugly" is
> *that*? &#4294967295;Depends on the eye of the beholder I guess.
>
> But, without the 1/2 period, the boundary conditions are smooth and
> there is no aliasing / spectral spreading.
>
> Fred

There is spreading from windowing, but you can avoid looking at it.

Any time you window you generate spectral spreading, even with a
rectangular window and n-periodic boundary conditions. The convenience
(or "beauty") of this case is that the projection of the N-periodic
signals spread by the rectangular window is zero at the frequency
samples calculated by the N point DFT except at the component
frequency. The spectral spreading is non-zero elsewhere. The time
domain windowing process convolves the FT of the window with the FT of
the signal in the frequency domain.  If you take N samples (that is
the rectangular window) of a single N-periodic frequency component,
the DFT calculates samples the delta function, the FT of the single
component, convolved with the sync function that is the FT of the
rectangular window. At the frequencies the N point DFT calculated
samples, the windowed response is non-zero at only one sample. The
zeros are due to the zeros of the sync function. If you sample the
response at any other frequency, the projection is non-zero. An
example of this can be calculated by zero extending the N time domain
samples by N zeros and calculating the 2N point DFT. Alternate samples
of the 2N point DFT output will be the samples calculated by the N
point DFT of the original N samples and the rest of the points will be
non-zero samples of the windowing-spread single frequency component at
the frequencies half way between the frequency of samples calculated
by the N point DFT.

Dale B. Dalrymple

On 12/10/11 3:53 PM, dbd wrote:
> On Dec 10, 10:23 am, robert bristow-johnson <rbj@audioimagination.com>  wrote:
...
>> the DFT invertibly maps one discrete and periodic sequence of numbers to another discrete and periodic sequence of numbers of the same period.
>>
>> ... something that the periodicity deniers just don't seem to get.
>>
>
> There are no "periodicity deniers". There are only those deniers who
> know only a single small view of the world and from lack of
> imagination would deny others the use of many other valid useful
> world views.

it's math, not something subjective nor political nor theological nor 
philosophical like "world views".

equality signs are pretty much focused in their meaning and unforgiving.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."