Re: Appendix A: Types of Fourier Transforms

On Friday, January 21, 2011 6:59:36 PM UTC-5, dbd wrote:

  ...

> The window is how the user trades off locality and variance. It is an
> important tool in controlling the selected processing. It is useful to
> put the window conceptually in the DFT because basis function values
> outside the window are never calculated while the data values outside
> the extent of the window are used.

  ...

This is new to me, and surprising. When calculating an FT, just what exactly are the values outside the extent of the window used /for/?

Jerry

On Jan 23, 12:10=A0pm, Jerry Avins <j...@ieee.org> wrote:
> On Friday, January 21, 2011 6:59:36 PM UTC-5, dbd wrote:
> ...
> > It is useful to
> > put the window conceptually in the DFT because basis function values
> > outside the window are never calculated while the data values outside
> > the extent of the window are used.

>
> This is new to me, and surprising. When calculating an FT, just what exac=
tly are the values outside the extent of the window used /for/?
>
> Jerry

No Jerry, not an FT, a DFT. That may seem picky, but this is a thread
discussing relations between different transforms, so let's keep it
straight.

In dynamic signal analyzers (DSA), data outside the current window
will be used for weighted overlapped spectral averaging (WOSA or
Welch's method) and/or generating other lines in the waterfall/
spectrogram displays. These are common basic digital signal processing
applications of DFTs. These are common systems where data sets are
much larger than interesting transform sizes and all the data gets
processed, sometimes within multiple windows. These are applications
where the processing is selected because it is known (and verifiable)
that there are signal components that cannot be treated correctly as
periodically extended. Because of this, stochastic signals and non-
stationary signals can be either enhanced or reduced by the selection
of appropriate post-DFT algorithms. Applications outside of DSAs
include filter banks, frequency domain adaptive filters,
demultiplexers and intercept receivers.

Now if you want to know how data outside the window influences
calculations inside the window, you'll need to ask steveu   	 (Jan 11,
4:49 pm in this thread), but he hasn't been responsive to earlier
questions about this.

Dale B. Dalrymple

On Jan 23, 6:30 pm, dbd <d...@ieee.org> wrote:
> On Jan 23, 12:10 pm, Jerry Avins <j...@ieee.org> wrote:
>
> > On Friday, January 21, 2011 6:59:36 PM UTC-5, dbd wrote:
> > ...
> > > It is useful to
> > > put the window conceptually in the DFT because basis function values
> > > outside the window are never calculated while the data values outside
> > > the extent of the window are used.
>
> > This is new to me, and surprising. When calculating an FT, just what
> > exactly are the values outside the extent of the window used /for/?
>
>
> No Jerry, not an FT, a DFT. That may seem picky, but this is a thread
> discussing relations between different transforms, so let's keep it
> straight.

ya know Dale.  Jerry is just grinning (as am i).  we aren't (at least
we weren't, can't promise about the future) the folks patronizing
someone else ("in the real world ... question is disingenuous ... Get
your own question straight").  we are here about the technical issue
only, and, although i'm biting my lip, i will try to keep it that way,
at least from my end.

ya know, it's sorta like those guys wondering where in this space the
universe is expanding where it's the universe *and* the space
expanding.  maybe not.

you see, Dale, picking this finite set of N samples out of a stream is
an application of windowing.


> Placing the window on the basis functions puts the
> control where it is best understood.

the whole point Dale is that the windowing happened long before (or
maybe just microseconds before) the DFT ever sees the data.  the
windowing is best understood where at the point where it is applied.

now what *is* windowing?  consider something similar: sampling.  how
is windowing similar to sampling, Dale?  what is fundamentally similar
between the two?

they are both throwing away information?  now how are they throwing
away information?  in either physical situation is the machine is just
extracting the information it wants and is just ignoring the
information it doesn't

but how do we mathematically model it?

for sampling, we model it by multiplying by the dirac comb:


      y(t) = x(t) * SUM{ delta(t - n*T) }

           = SUM{ x(n*T) * delta(t - n*T) }

           = SUM{ x[n] * delta(t - n*T) }

i think there should be another factor of T tossed in there, but
that's a different fish to fry.  the point is that value of the
sampling function between the samples is zero.  we model throwing away
that information by multiplying it by zero.


for windowing, we model it by multiplying by a window function:

      y(t) = x(t) * w(t)

and  w(t) = 0  for all |t| > W

or (before he accuses us of being disingenuous), for a discrete-time
signal

      y[n] = x[n] * w[n]

if you're saying that there *is* no space outside of 0 <= n < N, then
the rectangular window is no operation at all and has no effect.  so
then, how are there any effects to model if you're just yanking N
samples out of a much longer stream?

that is where the window is applied.  whether it's a rectangular
window or you apply something else to it like a Hamming or Kaiser.
and you *model* what it does by multiplying the samples that are
outside this window by zero.  those N samples are appended by an
infinite string of zeros on both sides and, if we could get a
hypothetical machine to do a DTFT, that is the information it would
see.

since a finite number of samples are non-zero, and if the input is
assumed sampled from a bandlimited source, you could attach a sinc()
function to each of those N samples, CFT that, and you have the DTFT
for -pi < omega < +pi.  uniformly sample those frequency-domain points
(with a spacing of 2*pi/N) and you have the DFT.  funny thing is, when
you sample in one domain, it causes periodic repeating and overlapping
in the reciprocal domain.  you cannot escape the periodic extension no
matter how you want to view the DFT.



____________________________________________________

> In dynamic signal analyzers (DSA), data outside the current window
> will be used for weighted overlapped spectral averaging (WOSA or
> Welch's method) and/or generating other lines in the waterfall/
> spectrogram displays. These are common basic digital signal processing
> applications of DFTs. These are common systems where data sets are
> much larger than interesting transform sizes and all the data gets
> processed, sometimes within multiple windows. These are applications
> where the processing is selected because it is known (and verifiable)
> that there are signal components that cannot be treated correctly as
> periodically extended. Because of this, stochastic signals and non-
> stationary signals can be either enhanced or reduced by the selection
> of appropriate post-DFT algorithms. Applications outside of DSAs
> include filter banks, frequency domain adaptive filters,
> demultiplexers and intercept receivers.

____________________________________________________


blah blah blah blah blah....

the above says absolutely nothing regarding the issue at hand.  it's
fluff.  not even that.

Dale, if you had an inclination to address the question, it would be
about producing a mathematical problem or mathematical operation where
embedding the window functions into the basis functions of the DFT
actually serves a purpose.  what operation of the DFT is somehow "more
correct" with the rectangular window in the basis functions than it is
where the basis functions are periodic?  i can show you something very
basic where putting the rectangular window into the basis functions
causes an error, unless you put in a workaround (the modulo
indexing).  and no one has yet told us why having an error requiring a
workaround has utility.

> Now if you want to know how data outside the window influences
> calculations inside the window, you'll need to ask steveu (Jan 11,
> 4:49 pm in this thread), but he hasn't been responsive to earlier
> questions about this.

we'll wait for steve.

r b-j

On Jan 23, 9:07&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> ...
>
> that is where the window is applied. &#4294967295;whether it's a rectangular
> window or you apply something else to it like a Hamming or Kaiser.
> and you *model* what it does by multiplying the samples that are
> outside this window by zero. &#4294967295;those N samples are appended by an
> infinite string of zeros on both sides and, if we could get a
> hypothetical machine to do a DTFT, that is the information it would
> see.
>
> since a finite number of samples are non-zero, and if the input is
> assumed sampled from a bandlimited source, you could attach a sinc()
> function to each of those N samples, CFT that, and you have the DTFT
> for -pi < omega < +pi. &#4294967295;uniformly sample those frequency-domain points
> (with a spacing of 2*pi/N) and you have the DFT. &#4294967295;funny thing is, when
> you sample in one domain, it causes periodic repeating and overlapping
> in the reciprocal domain. &#4294967295;you cannot escape the periodic extension no
> matter how you want to view the DFT.
>

You cannot use sinc interpolation to recover arbitrary bandlimited
signals from only N samples. Stochastic, non-stationary, and periodic
(but not periodic in the N samples) signals cannot be recovered from
only the N samples. As has been said all along, your process can only
work for the signal space of linear combinations of signals periodic
in N samples (and within the bandlimit). You have only a special case
for your argument. Not everyone is willing to live only in that
corner.

> ____________________________________________________
>
> > In dynamic signal analyzers (DSA), data outside the current window
> > will be used for weighted overlapped spectral averaging (WOSA or
> > Welch's method) and/or generating other lines in the waterfall/
> > spectrogram displays. These are common basic digital signal processing
> > applications of DFTs. These are common systems where data sets are
> > much larger than interesting transform sizes and all the data gets
> > processed, sometimes within multiple windows. These are applications
> > where the processing is selected because it is known (and verifiable)
> > that there are signal components that cannot be treated correctly as
> > periodically extended. Because of this, stochastic signals and non-
> > stationary signals can be either enhanced or reduced by the selection
> > of appropriate post-DFT algorithms. Applications outside of DSAs
> > include filter banks, frequency domain adaptive filters,
> > demultiplexers and intercept receivers.
>
> ____________________________________________________
>
> blah blah blah blah blah....
>
> the above says absolutely nothing regarding the issue at hand. &#4294967295;it's
> fluff. &#4294967295;not even that.
>

You are correct that this is not responsive to your issue. As it is a
response to a question by Jerry about a snippet quoted from one of my
posts, your interpretation of it as a response to you is disingenuous
or incoherent.

Dale B. Dalrymple

On Jan 24, 8:08&#4294967295;pm, dbd <d...@ieee.org> wrote:
> On Jan 23, 9:07&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
>
>
> > ...
>
> > that is where the window is applied. &#4294967295;whether it's a rectangular
> > window or you apply something else to it like a Hamming or Kaiser.
> > and you *model* what it does by multiplying the samples that are
> > outside this window by zero. &#4294967295;those N samples are appended by an
> > infinite string of zeros on both sides and, if we could get a
> > hypothetical machine to do a DTFT, that is the information it would
> > see.
>
> > since a finite number of samples are non-zero, and if the input is
> > assumed sampled from a bandlimited source, you could attach a sinc()
> > function to each of those N samples, CFT that, and you have the DTFT
> > for -pi < omega < +pi. &#4294967295;uniformly sample those frequency-domain points
> > (with a spacing of 2*pi/N) and you have the DFT. &#4294967295;funny thing is, when
> > you sample in one domain, it causes periodic repeating and overlapping
> > in the reciprocal domain. &#4294967295;you cannot escape the periodic extension no
> > matter how you want to view the DFT.
>
> You cannot use sinc interpolation to recover arbitrary bandlimited
> signals from only N samples.

the sinc functions attached to the samples outside of the window have
those sample values (what are zero) multiplying them.  doesn't matter,
forget about attaching sinc functions to the samples, just leave them
attached to the dirac deltas (all by N have zero coefficients) and
apply a continuous Fourier Transform to that.  then you get the DTFT
for omega not just between -pi and +pi, but it will repeat (with
period 2*pi) forever.  you still sample that with N equally spaced
samples (with spacing 2*pi/N) and you get the DFT.

> Stochastic, non-stationary, and periodic (but not periodic in the
> N samples) signals cannot be recovered from only the N samples.

the DFT doesn't know or care where those N samples came from.  it's
just presented with N samples.  whether they come from stochastic or
deterministic sources, stationary or not, periodic or not, they're
just N samples.

but the DFT still fits N periodic basis functions (with coefficients
X[k]) to those N samples.  any rectangular window embedded to those
basis functions serve no utility.  if you attach the rectangular
window functions to the basis functions, then, if any shifting is
needed (by multiplying by e^(-i*2*pi*k*m/N) or by a transfer function,
H[k]), all that rectangular window does for you is force you to use
modulo-N arithmetic in the indices.

> As has been said all along, your process can only
> work for the signal space of linear combinations of signals periodic
> in N samples (and within the bandlimit). You have only a special case
> for your argument.

no, what i had said is that whether or not you are thinking the N
samples were extracted from a periodic signal, it doesn't matter.  the
DFT treats those N samples as defining a single period of a periodic
signal.  the DFT fits periodic basis functions to those N samples.

> Not everyone is willing to live only in that corner.

you have no choice.  (but it's not a corner, it's the whole space of N
arbitrary sample values.)

> > ____________________________________________________
>
> > > In dynamic signal analyzers (DSA), data outside the current window
> > > will be used for weighted overlapped spectral averaging (WOSA or
> > > Welch's method) and/or generating other lines in the waterfall/
> > > spectrogram displays. These are common basic digital signal processing
> > > applications of DFTs. These are common systems where data sets are
> > > much larger than interesting transform sizes and all the data gets
> > > processed, sometimes within multiple windows. These are applications
> > > where the processing is selected because it is known (and verifiable)
> > > that there are signal components that cannot be treated correctly as
> > > periodically extended. Because of this, stochastic signals and non-
> > > stationary signals can be either enhanced or reduced by the selection
> > > of appropriate post-DFT algorithms. Applications outside of DSAs
> > > include filter banks, frequency domain adaptive filters,
> > > demultiplexers and intercept receivers.
>
> > ____________________________________________________
>
> > blah blah blah blah blah....
>
> > the above says absolutely nothing regarding the issue at hand. &#4294967295;it's
> > fluff. &#4294967295;not even that.
>
> You are correct that this is not responsive to your issue. As it is a
> response to a question by Jerry about a snippet quoted from one of my
> posts,

you weren't responding to his question either.  just a form of techno-
babble.

the issue (using the briefest language i can think of) is whether or
not the DFT is something different than the DFS.  whether or not the
DFT necessarily periodically extends the data passed to it.  whether
or not there is any utility in defining the DFT basis functions
differently from those of the DFS, whether or not there is any utility
to windowing the DFT basis functions outside of the interval 0 <= n <
N.

i am keeping the issue focused on that point.

> your interpretation of it as a response to you is disingenuous
> or incoherent.

whatever you say.

r b-j

On Jan 24, 7:33&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> ...
> the DFT doesn't know or care where those N samples came from. &#4294967295;it's
> just presented with N samples. &#4294967295;whether they come from stochastic or
> deterministic sources, stationary or not, periodic or not, they're
> just N samples.
> ...

The DFT doesn't know or care where it's N input samples came from, it
only produces N outputs, there are just N outputs. The DFT algorithm
is not performed by sampling the infinite CFT of the input samples.
This is robert's replacement for the DFT. Replacing the DFT with
robert's replacement for the DFT performs the periodic extension, not
the DFT. Replacement of the DFT by robert's replacement of the DFT is
only valid for the specific signal space already described. If robert
has failed to distinguish the DFT from the DFS it may be because he
isn't comparing the DFS to the DFT  but to robert's replacement for
the DFT instead.

Dale B. Dalrymple

On Jan 25, 2:42&#4294967295;am, dbd <d...@ieee.org> wrote:
> On Jan 24, 7:33&#4294967295;pm, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
> > ...
> > the DFT doesn't know or care where those N samples came from. &#4294967295;it's
> > just presented with N samples. &#4294967295;whether they come from stochastic or
> > deterministic sources, stationary or not, periodic or not, they're
> > just N samples.
> > ...
>
> The DFT doesn't know or care where it's N input samples came from, it
> only produces N outputs, there are just N outputs.

N values which define one period of a periodic sequence, X[k].

> The DFT algorithm
> is not performed by sampling the infinite CFT of the input samples.

no, it's one way the DFT is derived (the other way is the DFS way, map
this one periodic sequence x[n] to another periodic sequence, X[k]).

there is no CFT of the input samples.  there *is* an CFT of the input
samples attacted to dirac impulses and it is not uncommon at all to
derive the DFT as sampling the output of the DTFT:

     X(e^(i*omega))  =  SUM{ x[n] * e^(-i*omega*n) }

with N samples of spacing 2*pi/N from omega=-pi to just before omega=
+pi.

That *is* a common and legitimate way to view the DFT.  it's the same
as sampling the Z Transform of x[n] N equally spaced places on the
unit circle in the z-plane.

And, again the point is, sampling X(e^(i*omega)) in the frequency
domain causes what x[n] is in the time domain to be repeated forever
in both directions and overlapped and added.  That is what sampling
does.

So are you gonna start doing the math, Dale?

r b-j