Why window in time domain before FFT?

This is loosely related to my post "Why no flat topped windows?"
My portion of that thread is best forgotten. Please forget ;)

However, the responses got me thinking and straightened some of my 
spaghetti coded thought. What follows will probably be slanted in ways I 
cannot know by eventual application - in _some_ sense characterizing 
speech. The vaguer that taken, probably the better.

THE GOAL:
Infinite frequency resolution with absolute intensity accuracy.
Sorry, don't have the time.

Common approach:
Choose a window by trading off frequency resolution for accuracy (in 
measure chosen by user) of amplitude. Adjusting window width and/or zero 
padding used to observe desired resolution. Band limiting applied only 
at the high end to satisfy Nyquist and anti-aliasing. An advantage, that 
I've never seen explicitly mentioned, is that there is *NO* restriction 
of _when_ the window begins.


PROPOSED approach:

Goals:
Maximize resolution.
Define amplitude accuracy in a spectrum to spectrum sense by multiplying 
one window by a "normalizing" constant.
Acceptable constraints:
Effectively band limiting of low end -- throw out frequencies less than 
x*(1/window width).[Question to be answered: Does filtering have to be 
done before FFT or is it possible just to just set appropriate bins to 
zero?]

Inspiration for approach:
In introducing the idea of windowing use is sometimes made of a special 
case when no windowing is needed. IE, the sample is an integral multiple 
of the period of all frequencies present. I've also seen discussion 
stating that an ideal window's shape would be zero at leading/trailing 
edge and all derivatives would also be zero.

Implementation:
Real time processing not required.
Sample rate and high frequency cutoff constrained only by Nyquist and 
aliasing.
Nominal window width is 100 ms.
Low frequency cut off >~ 30 Hz.
Window shape rectangular.
Window start restricted to zero crossing.
Window end restrictions:
    1. zero crossing in same sense as at start -- ie
       value the same (zero) at start/end of window
       first derivative has same sign at start/end of window
    2. window width
       +- 1/2 period of low freq limit
       prefer +- less than 10% of nominal
    3. from possible end points meeting above criteria
       chose for best match of local slope
When comparing spectra, multiply by [(nominal width)/(actual width)]

Comments? [more on how I approached problem than on result]

A somewhat related note: 
If you can "get away with" assuming a cyclic signal, you don't have to
window anymore. The error that I'm introducing through the cyclic
assumption can be easily investigated and justified, and from that point
on life gets so much easier.

-mn

mnentwig wrote:
> A somewhat related note: 
> If you can "get away with" assuming a cyclic signal, you don't have to
> window anymore. The error that I'm introducing through the cyclic
> assumption can be easily investigated and justified, and from that point
> on life gets so much easier.
> 
> -mn

  I can't assume cyclic exactly. But was trying to fudge in that by 
constraining window such that value was the same (zero) and 1st 
derivative was approximately equal at each end of window.

On Nov 3, 7:47 am, Richard Owlett <rowl...@atlascomm.net> wrote:
> This is loosely related to my post "Why no flat topped windows?"
> My portion of that thread is best forgotten. Please forget ;)
>
> However, the responses got me thinking and straightened some of my
> spaghetti coded thought. What follows will probably be slanted in ways I
> cannot know by eventual application - in _some_ sense characterizing
> speech. The vaguer that taken, probably the better.
>
> THE GOAL:
> Infinite frequency resolution with absolute intensity accuracy.
> Sorry, don't have the time.
>
> Common approach:
> Choose a window by trading off frequency resolution for accuracy (in
> measure chosen by user) of amplitude. Adjusting window width and/or zero
> padding used to observe desired resolution. Band limiting applied only
> at the high end to satisfy Nyquist and anti-aliasing. An advantage, that
> I've never seen explicitly mentioned, is that there is *NO* restriction
> of _when_ the window begins.
>
> PROPOSED approach:
>
> Goals:
> Maximize resolution.
> Define amplitude accuracy in a spectrum to spectrum sense by multiplying
> one window by a "normalizing" constant.
> Acceptable constraints:
> Effectively band limiting of low end -- throw out frequencies less than
> x*(1/window width).[Question to be answered: Does filtering have to be
> done before FFT or is it possible just to just set appropriate bins to
> zero?]
>
> Inspiration for approach:
> In introducing the idea of windowing use is sometimes made of a special
> case when no windowing is needed. IE, the sample is an integral multiple
> of the period of all frequencies present. I've also seen discussion
> stating that an ideal window's shape would be zero at leading/trailing
> edge and all derivatives would also be zero.
>
> Implementation:
> Real time processing not required.
> Sample rate and high frequency cutoff constrained only by Nyquist and
> aliasing.
> Nominal window width is 100 ms.
> Low frequency cut off >~ 30 Hz.
> Window shape rectangular.
> Window start restricted to zero crossing.
> Window end restrictions:
>     1. zero crossing in same sense as at start -- ie
>        value the same (zero) at start/end of window
>        first derivative has same sign at start/end of window
>     2. window width
>        +- 1/2 period of low freq limit
>        prefer +- less than 10% of nominal
>     3. from possible end points meeting above criteria
>        chose for best match of local slope
> When comparing spectra, multiply by [(nominal width)/(actual width)]
>
> Comments? [more on how I approached problem than on result]

Richard

Your post resembles the porcupine: there are so many points thrown so
close together that it's hard to try to handle.

There is also a lack of context. Do you mean to measure frequency and
amplitude of stationary tones? Modulated tones? The modulation
parameters? Continuous spectra? Narrowband noise? What are the other
signals present to be rejected? White noise? Colored noise? Stationary
tones? Modulated tones? Continuous spectra? Many of the different
combinations of these signals/interferers require different windowing
approaches. The hardest part of selecting windowing approaches is
usually selecting and understanding the problem you are trying to
solve. If you want to start by solving them all at once, troll on.

Dale B. Dalrymple
http://dbdimages.com
http://stores/lulu.com/dbd

On Sat, 03 Nov 2007 09:47:07 -0500, Richard Owlett wrote:

> This is loosely related to my post "Why no flat topped windows?"
> My portion of that thread is best forgotten. Please forget ;)
> 
> However, the responses got me thinking and straightened some of my 
> spaghetti coded thought. What follows will probably be slanted in ways I 
> cannot know by eventual application - in _some_ sense characterizing 
> speech. The vaguer that taken, probably the better.
> 
> THE GOAL:
> Infinite frequency resolution with absolute intensity accuracy.
> Sorry, don't have the time.

Ooh.  I _like_ that turn of phrase.  It's succinct, accurate, and just a
bit smart-ass.  I only wish I had thought of it.
> 
> Common approach:
> Choose a window by trading off frequency resolution for accuracy (in 
> measure chosen by user) of amplitude. Adjusting window width and/or zero 
> padding used to observe desired resolution. Band limiting applied only 
> at the high end to satisfy Nyquist and anti-aliasing. An advantage, that 
> I've never seen explicitly mentioned, is that there is *NO* restriction 
> of _when_ the window begins.
> 
> 
> PROPOSED approach:
> 
> Goals:
> Maximize resolution.
> Define amplitude accuracy in a spectrum to spectrum sense by multiplying 
> one window by a "normalizing" constant.
> Acceptable constraints:
> Effectively band limiting of low end -- throw out frequencies less than 
> x*(1/window width).[Question to be answered: Does filtering have to be 
> done before FFT or is it possible just to just set appropriate bins to 
> zero?]

If by "filtering" you mean getting rid of the mean and trend in your data
-- yes.  Hopefully my answer below will make it clear why this is the case.

> Inspiration for approach:
> In introducing the idea of windowing use is sometimes made of a special 
> case when no windowing is needed. IE, the sample is an integral multiple 
> of the period of all frequencies present. I've also seen discussion 
> stating that an ideal window's shape would be zero at leading/trailing 
> edge and all derivatives would also be zero.
> 
> Implementation:
> Real time processing not required.
> Sample rate and high frequency cutoff constrained only by Nyquist and 
> aliasing.
> Nominal window width is 100 ms.
> Low frequency cut off >~ 30 Hz.
> Window shape rectangular.
> Window start restricted to zero crossing.
> Window end restrictions:
>     1. zero crossing in same sense as at start -- ie
>        value the same (zero) at start/end of window
>        first derivative has same sign at start/end of window
>     2. window width
>        +- 1/2 period of low freq limit
>        prefer +- less than 10% of nominal
>     3. from possible end points meeting above criteria
>        chose for best match of local slope
> When comparing spectra, multiply by [(nominal width)/(actual width)]
> 
> Comments? [more on how I approached problem than on result]

It's a bit early in the morning for me to grok this whole approach you're
taking, so I'm going to comment and/or clarify what I see are underlying
assumptions and hope it helps.

The FFT struggles from two problems, one more basic than the other.  The
first problem you've explicitly identified: You can't gather complete
information about a sample's frequency content if the sample itself is of
finite duration.  I see hints that you know of the second, and you've been
on the group long enough to know it.  None the less, I'm going to state it
my way: The FFT mathematics is written as if the sample that you're
analyzing is one cycle of a periodic waveform.

The first problem is about as insurmountable as they come.  I don't know
if there are other transforms out there (aside from an FFT with windowing)
that overcome the second problem, but the FFT is just so dang
computationally efficient that even if there were such a transform it may
still make more sense to beat the FFT into submission with data
preprocessing rather than using it.

All of the windowing folderol is there to surmount the second problem. 
When you have a data sample whose value (or nth derivative) starts
at one value and ends at another, the FFT algorithm doesn't "see" this as
a sample that happens to start at one thing and end at another.  Instead,
it "sees" it as a periodic wave with a whopping big discontinuity between
cycles.  It then proceeds to add the frequency spectrum of this whopping
big discontinuity into the frequency spectrum of all the stuff in between.

The whole point of windowing your data is to smooth out the discontinuity,
to trade off a little bit of spreading of the spectrum for not splattering
the "energy" from that "discontinuity" all over the spectrum that you
really want to see.  The point of all the different windows is that (a)
it's a touchy-feely process, so there's room to invent new windows, (b)
different data sets are going to benefit from different windows, and (c)
different experimental goals are going to benefit from different windows.

You mentioned the lack of flat-topped windows.  I have used a window
that's flat on top with 1/2 cycle raised cosines to bring the ends down to
zero.  This is for noisy data that is inherently bandpass, so there isn't
a significant amount of DC to smear over my spectrum with the more abrupt
than usual endings but there is a lot of full-strength samples to average
over.  It worked for me -- maybe it could be the "Wescott Window"?

So go ahead and invent the "Owlett Window" -- perhaps it'll be an
improvement, if not for all of us, then at least for the data sets that
you're dealing with, and the problems that you're trying to solve.

-- 
Tim Wescott
Control systems and communications consulting
http://www.wescottdesign.com

Need to learn how to apply control theory in your embedded system?
"Applied Control Theory for Embedded Systems" by Tim Wescott
Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html

dbd wrote:
> On Nov 3, 7:47 am, Richard Owlett <rowl...@atlascomm.net> wrote:
> 
>>This is loosely related to my post "Why no flat topped windows?"
>>My portion of that thread is best forgotten. Please forget ;)
>>
>>However, the responses got me thinking and straightened some of my
>>spaghetti coded thought. What follows will probably be slanted in ways I
>>cannot know by eventual application - in _some_ sense characterizing
>>speech. The vaguer that taken, probably the better.
>>
>>THE GOAL:
>>Infinite frequency resolution with absolute intensity accuracy.
>>Sorry, don't have the time.
>>
>>Common approach:
>>Choose a window by trading off frequency resolution for accuracy (in
>>measure chosen by user) of amplitude. Adjusting window width and/or zero
>>padding used to observe desired resolution. Band limiting applied only
>>at the high end to satisfy Nyquist and anti-aliasing. An advantage, that
>>I've never seen explicitly mentioned, is that there is *NO* restriction
>>of _when_ the window begins.
>>
>>PROPOSED approach:
>>
>>Goals:
>>Maximize resolution.
>>Define amplitude accuracy in a spectrum to spectrum sense by multiplying
>>one window by a "normalizing" constant.
>>Acceptable constraints:
>>Effectively band limiting of low end -- throw out frequencies less than
>>x*(1/window width).[Question to be answered: Does filtering have to be
>>done before FFT or is it possible just to just set appropriate bins to
>>zero?]
>>
>>Inspiration for approach:
>>In introducing the idea of windowing use is sometimes made of a special
>>case when no windowing is needed. IE, the sample is an integral multiple
>>of the period of all frequencies present. I've also seen discussion
>>stating that an ideal window's shape would be zero at leading/trailing
>>edge and all derivatives would also be zero.
>>
>>Implementation:
>>Real time processing not required.
>>Sample rate and high frequency cutoff constrained only by Nyquist and
>>aliasing.
>>Nominal window width is 100 ms.
>>Low frequency cut off >~ 30 Hz.
>>Window shape rectangular.
>>Window start restricted to zero crossing.
>>Window end restrictions:
>>    1. zero crossing in same sense as at start -- ie
>>       value the same (zero) at start/end of window
>>       first derivative has same sign at start/end of window
>>    2. window width
>>       +- 1/2 period of low freq limit
>>       prefer +- less than 10% of nominal
>>    3. from possible end points meeting above criteria
>>       chose for best match of local slope
>>When comparing spectra, multiply by [(nominal width)/(actual width)]
>>
>>Comments? [more on how I approached problem than on result]
> 
> 
> Richard
> 
> Your post resembles the porcupine: there are so many points thrown so
> close together that it's hard to try to handle.

I'll agree to "hard to handle".
> 
> There is also a lack of context. 

I'll disagree. My I quote myself ;)

 >> What follows will probably be slanted in ways I cannot know by
 >> eventual application - in _some_ sense characterizing speech.

 > Do you mean ...?  ...? ...? etc

NOPE. As stated above "characterizing speech"
I obviously wish to compare spectrum of one "chunk" of speech to another.
I then go on to list characteristics _in order of significance_ .
Note other indicators of application
   low freq of interest 30 Hz. (considered to be low end of audible)
   window length near 100 msec (typical of speech recognition)

> The hardest part of selecting windowing approaches is
> usually selecting and understanding the problem you are trying to
> solve. 

That was a given.
That why I tried to describe my understand of HOW a window is chosen. I 
  then described the characteristics of a window I'm considering and 
what I hoped to achieve.

> If you want to start by solving them all at once, troll on.

I don't see how this would be considered a "troll".

.On Nov 3, 10:52 am, Richard Owlett <rowl...@atlascomm.net> wrote:
.>
.> > There is also a lack of context.
.>
.> I'll disagree. My I quote myself ;)
.>
.>  >> What follows will probably be slanted in ways I cannot know by
.>  >> eventual application - in _some_ sense characterizing speech.
.>
.>  > Do you mean ...?  ...? ...? etc
.>
.> NOPE. As stated above "characterizing speech"

Unfortunately all of the ...? ...? ...? are listed because they relate
to characterizing speech. It would be hard to pick a broader context
than "characterizing speech". Maybe you do know what measurements you
want to make. If so, please share it with us. If not, how can you
expect to pick a window to make them?

.> I obviously wish to compare spectrum of one "chunk" of speech to
another.
.> I then go on to list characteristics _in order of significance_ .

Yes, and different characteristics of speech are what require
different windowing approaches.
So, what are -your- characteristics of speech and their order of
significance? Your statement in the paragraph mentioning
characterizing speech,"The vaguer that taken, probably the better. "
isn't an explanation of characteristics of interest to you and doesn't
provide a basis for evaluating windowing approaches.

This is the hard part of the window selection/design process, getting
more specific than "I want a window that makes me feel good." (My
apologies to Huey Lewis and the News)

.>
.> > If you want to start by solving them all at once, troll on.
.>
.> I don't see how this would be considered a "troll".
That's to be expected.

Dale B. Dalrymple
http://dbdimages.com
http://stores.lulu.com/dbd

On Nov 3, 12:47 pm, Richard Owlett <rowl...@atlascomm.net> wrote:
> mnentwig wrote:
> > A somewhat related note:
> > If you can "get away with" assuming a cyclic signal, you don't have to
> > window anymore. The error that I'm introducing through the cyclic
> > assumption can be easily investigated and justified, and from that point
> > on life gets so much easier.
>
>   I can't assume cyclic exactly. But was trying to fudge in that by
> constraining window such that value was the same (zero) and 1st
> derivative was approximately equal at each end of window.

okay, Richard, then this is where the rubber meets the road regarding
this occasional little dispute that crops up here regarding the
alledged *inherent* periodic nature of the DFT (which is what the FFT
is an implementation of).  i am a partisan in this debate that says
that the DFT *inherently* periodically extends the finite data passed
to it.

so even if you do not or cannot assume cyclic behavior of the signal
passed to the DFT, the DFT *does* make that assumption (if i may
anthropomorphize the DFT).  that means whatever is the finite data set
you passed to the DFT, the DFT "assumes" it is one period of a
discrete periodic function with period equal to the length of the DFT,
N.

so, now imagine if you yank out N samples from a continuous stream of
data and send that to the DFT.  the DFT thinks it's a discrete
periodic function and your last sample x[N-1] is followed immediately
by your first (or "0th") sample x[0] (so the implied x[N] is the same
as x[0]).  if no periodic nature can be assumed, then there is likely
an "unnatural" discontinuity between the x[N-1] and x[N] (which is =
x[0]) which wouldn't be there if we yanked N samples out of a periodic
function of period N.  that discontinuity (a step function) will
introduce spurious high frequencies in your spectrum that you would
not expect if you were looking at x[n] *before* you yanked N samples
out of it and threw away all of the others.

that is literally applying a rectangular window (a simple window, with
predictable behavior, but crappy), whether you like it or not.
windowing cannot be avoided in the context where you cannot assume
periodicity.  that rectangular window applies discontinuities (in the
0th derivative and higher) that mucks up your spectrum with a lot of
high frequency energy that was not in your original signal.  so
applying a different window, that has reduced discontinuities will
have reduced introduction or promotion of spurious high frequencies to
muck up your spectrum a little less.  those apparent and spurious high
frequecies can be equivalently thought of as what happens to every
significant frequency compoenent in your unwindowed signal, which
shows up as a thin spike in the frequency domain.  each spike
(associated with a particular frequency component) is convolved with
the DFT of the window function.

in the case of the crappy rectangular window, that convolving function
is a sinc function (most precisely, this periodic dirichlet sinc-like
function).  and the side lobes of this sinc function are pretty big
(because their sizes die off in inverse proportion to frequency
difference from the frequency of that significant frequency component
or that thin spike).  1/f isn't so good and other windows have
convolving functions with side lobes that die off faster than 1/f (but
there is a tradeoff with the width, or sloppiness, of the main lobe).

so, besides tradeoffs between main-lobe sloppiness and side-lobe
corruption, the other trade off is accuracy versus resources.  the
larger N is, the larger your chuck of data is, means that you can get
better performance in *both* main-lobe and side-lobe performance.  but
with a fixed N, the main-lobe and side-lobe problems trade off with
each other, when you consider different windows.  Kaiser tried (and
succeeded very well) to put an optimal expression of this tradeoff,
getting the best side-lobe performance for a fixed main lobe width,
and then even introduced a window shape parameter (called "beta", i
think) that you can twist to trade off between the main-lobe and side-
lobe problems (given a fixed N).  this is why the Kaiser window is
commonly cited in the lit and commonly used in practice.

but, *if* you *can* assume periodicity with a known integer period,
using the DFT (on the *unwindowed* signal) of length, N, exactly equal
to that period, will get you exactly the Fourier coefficients of that
discrete periodic function.  those coefficients themselves form a
discrete and periodic function, with period of the same length N.

this is my most complete and concise answer to your posted subject
question, Richard, that i can muster.  i don't really know anything
else about windows.

r b-j

On Nov 3, 3:23 pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
.> ...
.> Kaiser tried (and
.> succeeded very well) to put an optimal expression of this tradeoff,
.> getting the best side-lobe performance for a fixed main lobe width,
.> and then even introduced a window shape parameter (called "beta", i
.> think) that you can twist to trade off between the main-lobe and
side-
.> lobe problems (given a fixed N).

In the mid 1950's the zero'th order modified bessel function window
was know as the Taylor 1-term window. I don't know who originally
suggested it. Taylor described it as a 1 term approximation from a
Bessel function series expression for the prolate spheroidal wave
function, which is the optimal window for minimum mainlobe width vs
integrated sidelobe energy. The 'Kaiser-Bessel' window is not an
optimum window but an easier to calculate approximation. Kaiser won
due acclaim by discovering Bessel's series summation for the Bessel
function on the blackboard of an associate at Bell labs where he
worked, writing a dozen lines of Fortran that implemented it, and
publishing to the benefit of DSPers.

Don't take my word for it. Check out what Kaiser said:
James Kaiser oral history transcript. IEEE History Center, February
11, 1997;

.> this is why the Kaiser window is
.> commonly cited in the lit and commonly used in practice.
.> ...
.> r b-j

Dale B. Dalrymple
http://dbdimages.com
hyyp://stores.lulu.com/dbd

On Nov 3, 8:35 pm, dbd <d...@ieee.org> wrote:
> On Nov 3, 3:23 pm, robert bristow-johnson <r...@audioimagination.com>
> wrote:
> .> ...
> .> Kaiser tried (and
> .> succeeded very well) to put an optimal expression of this tradeoff,
> .> getting the best side-lobe performance for a fixed main lobe width,
> .> and then even introduced a window shape parameter (called "beta", i
> .> think) that you can twist to trade off between the main-lobe and
> side-
> .> lobe problems (given a fixed N).
>
> In the mid 1950's the zero'th order modified bessel function window
> was know as the Taylor 1-term window. I don't know who originally
> suggested it. Taylor described it as a 1 term approximation from a
> Bessel function series expression for the prolate spheroidal wave
> function, which is the optimal window for minimum mainlobe width vs
> integrated sidelobe energy. The 'Kaiser-Bessel' window is not an
> optimum window but an easier to calculate approximation. Kaiser won
> due acclaim by discovering Bessel's series summation for the Bessel
> function on the blackboard of an associate at Bell labs where he
> worked, writing a dozen lines of Fortran that implemented it, and
> publishing to the benefit of DSPers.
>
> Don't take my word for it. Check out what Kaiser said:
> James Kaiser oral history transcript. IEEE History Center, February
> 11, 1997;

i'd rather take your word for it.  i'm not even a member of IEEE (can
you believe that) and haven't been since, just one year, when i was an
undergraduate student and i jumped on IEEE bandwagon driven by our
local IEEE student chapter at the U of North Dakota.

r b-j