Windowing in the Frequency Domain

On Apr 11, 1:54 pm, Rune Allnor <all...@tele.ntnu.no> wrote:

> ...
> I looked up the paper from IEEExplore. After a quick browsing
> the key equation seems to be eq. 28a, which defines the Hann
> window as
>
> w[n] = 0.5+ 0.5 cos[2*pi*n/N],  n = -N/2,...,0,...N/2-1.
>
> Note the end indexes! This window is *not* symmetric,
> and thus will produce a FIR filter which is *not* linear
> phase.

This is not a window applied to a sinc funtion to design a windowed
filter. It is a DFT window. harris explained the difference in the
material you "browsed". Try reading.

>
> So it seems there is a trade-off between a 'convenient'
> DFT of the window function, and a window function
> which produces linear-phase FIRs.

No tradeoff, they are simply different vectors.

>
> Coming to think of it, all the descriptions I have seen of
> window functions had to do with FIR filter design.

That's because you browsed instead of "seeing" the harris paper.

>It's
> no wonder the symmetric window functions are used
> in that context, since linear phase is a key point with
> FIR filters.
>
> That having been resolved, I still haven't seen any
> compelling reasons why one would want to do these
> computations in frequency domain?
>
> Rune

Others have seen what you only browse. Thank you for explaining what
you have missed.

Dale B. Dalrymple

> The sliding DFT
> Jacobsen, E.; Lyons, R.
> Signal Processing Magazine, IEEE
> Volume 20, Issue 2, Mar 2003 Page(s): 74 - 80

And errata in Tips & Tricks Jan 2004.


Martin

-- 
Quidquid latine scriptum est, altum videtur.

Rune Allnor wrote:

>> F. J. Harris: On the Use of Windows for Harmonic Analysis with
>> Discrete Fourier Transform, Proceedings of the IEEE, Vol. 66,
>> No. 1, January 1978
> 
> I looked up the paper from IEEExplore. After a quick browsing
> the key equation seems to be eq. 28a, which defines the Hann
> window as
> 
> w[n] = 0.5+ 0.5 cos[2*pi*n/N],  n = -N/2,...,0,...N/2-1.
> 
> Note the end indexes! This window is *not* symmetric,
> and thus will produce a FIR filter which is *not* linear
> phase.

Neither the OP nor harris are talking about filter design. In 
spectral analysis it is proper that the window be periodic, a point 
harris makes on p. 2, left column.

> That having been resolved, I still haven't seen any
> compelling reasons why one would want to do these
> computations in frequency domain?

The Sliding DFT updates N bin values in O(N) real operations per 
sampling interval (8*N+1 real ops + delayline bookkeeping in the 
unstabilized, real-input case). The equivalent FFT takes O(N log N) 
ops/interval, and rather more code. So with or without windowing, 
which doesn't change those complexity orders, there is an efficiency 
crossover point.


Martin

-- 
Quidquid latine scriptum est, altum videtur.

On 12 Apr, 00:44, dbd <d...@ieee.org> wrote:
> On Apr 11, 1:54 pm, Rune Allnor <all...@tele.ntnu.no> wrote:

> > Coming to think of it, all the descriptions I have seen of
> > window functions had to do with FIR filter design.
>
> That's because you browsed instead of "seeing" the harris paper.

I'll have to read the paper later, when I get the time.

> > That having been resolved, I still haven't seen any
> > compelling reasons why one would want to do these
> > computations in frequency domain?

> Others have seen what you only browse. Thank you for explaining what
> you have missed.

Still no arguments as to *why* the technique is relevant.
I'll explain why I am confused. Below I use the term
'N-period window' for N-length window with divisor N
in the cosine terms, and 'N-1-period window' for N-length
windows with divisor N-1 in the cosine terms.

First of all, I know of only two applications where these types
of windows are used: FIR filter design and spectrum estimation.
If anyone knows of other applications, I'm all ears.

------

In FIR filter design, the objective is to find a linear phase
symmetrical filter by modifying the truncated sinc by
applying a weight function. The reason is to obtain certain
improvements relative to the 'raw' sinc, like pushing down
side lobe levels and increasing stopband attenuation.

These days the window FIR filter design technique is mainly
of pedagogical importance, since e.g. Parks-McClellan type
algorithms give more direct control of the filter responses.
Except for the Kaiser (and possibly Lancosz?) window, the
user doesn't control neither ripple nor stop-band attenuation
with window functions. Those are given, once the window
function has been chosen.

So window functions have little 'operational' importance
in FIR filter design.

Now, from a *pedagogical* POV it's very hard first of all
to show that the side lobes decrease by use of windows
if you don't see them in the spectral magnitude plot.
Which is one very good reason for using the N-1-period
window functions instead of the N-period windows when
teaching.

Second, at the entry level courses where these things
are taught, the justification for teaching window functions
is that 'Just DFT'ing and setting all stop-band coefficients
to 0 is a bad thing'. Convolving with the 3-pt kernel in
frequency domain is all but equal to the newbie: The
result is that in spectrum domain, everything *looks*
equal to his own naive attempts, *except* for a handful
of coefficients near the pass-band edges. People with
years of experience with these things might appreciate
the importance; freshman students will not.

And so using the N-period window functions in class is
all but pedagogical sabotage.

---------

The other application for these windows is spectrum
estimation. In this context, the lousy properties of the
periodogram as estimator for the PSD is the sole reason
for using windows at all.

The variance of each periodogram coefficient is

Var[P(k)] = P(k)^2

The way to handle this is to average several coefficients,
ether by computing several shorter (but all of same length)
periodograms and compute the PSD estimate as the average
of the periodograms, or by computing the PSD estimate as
the weighted average of adjacent coefficients from the same
peiodogram. Or both.

With the N-1-period window function all periodogram
coefficients contribute to each estimated PSD coefficient.
This is the spectrum leakage.

*********************
Do note that the general spectrum leakage effect is
the justification for using windows at all. One might want
to control it better at times, but one does *not* want to
avoid it!
*********************

Compare this to the N-period window functions, where
each estimated PSD coefficient is computed as the
average of 3 or 5 adjacent periodogram coefficients,
depending on the type of window. One might wonder
how much of an improvement this gives, compared to
the 'raw' periodogram?

--------

To summarize:

N-period windows

- Serve no 'operational' purpose that can not be handled
  at least as well by e.g. Parks-McClellan designs.
- Are a pedagogical minefield when teaching filter
  design at DSP entry-level.
- Blatantly undermine the core justification for using
  windows at all, for non-parametric PSD estimation.

So why use them at all?

Rune

On Apr 12, 3:10 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 12 Apr, 00:44, dbd <d...@ieee.org> wrote:
>
> > On Apr 11, 1:54 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
> > > Coming to think of it, all the descriptions I have seen of
> > > window functions had to do with FIR filter design.
>
> > That's because you browsed instead of "seeing" the harris paper.
>
> I'll have to read the paper later, when I get the time.
>
> > > That having been resolved, I still haven't seen any
> > > compelling reasons why one would want to do these
> > > computations in frequency domain?
> > Others have seen what you only browse. Thank you for explaining what
> > you have missed.
>
> Still no arguments as to *why* the technique is relevant.
> I'll explain why I am confused. Below I use the term
> 'N-period window' for N-length window with divisor N
> in the cosine terms, and 'N-1-period window' for N-length
> windows with divisor N-1 in the cosine terms.
>
> First of all, I know of only two applications where these types
> of windows are used: FIR filter design and spectrum estimation.
> If anyone knows of other applications, I'm all ears.
>
> ------
>
> In FIR filter design, the objective is to find a linear phase
> symmetrical filter by modifying the truncated sinc by
> applying a weight function. The reason is to obtain certain
> improvements relative to the 'raw' sinc, like pushing down
> side lobe levels and increasing stopband attenuation.
>
> These days the window FIR filter design technique is mainly
> of pedagogical importance, since e.g. Parks-McClellan type
> algorithms give more direct control of the filter responses.
> Except for the Kaiser (and possibly Lancosz?) window, the
> user doesn't control neither ripple nor stop-band attenuation
> with window functions. Those are given, once the window
> function has been chosen.
>
> So window functions have little 'operational' importance
> in FIR filter design.
>
> Now, from a *pedagogical* POV it's very hard first of all
> to show that the side lobes decrease by use of windows
> if you don't see them in the spectral magnitude plot.
> Which is one very good reason for using the N-1-period
> window functions instead of the N-period windows when
> teaching.
>
> Second, at the entry level courses where these things
> are taught, the justification for teaching window functions
> is that 'Just DFT'ing and setting all stop-band coefficients
> to 0 is a bad thing'. Convolving with the 3-pt kernel in
> frequency domain is all but equal to the newbie: The
> result is that in spectrum domain, everything *looks*
> equal to his own naive attempts, *except* for a handful
> of coefficients near the pass-band edges. People with
> years of experience with these things might appreciate
> the importance; freshman students will not.
>
> And so using the N-period window functions in class is
> all but pedagogical sabotage.
>
> ---------
>
> The other application for these windows is spectrum
> estimation. In this context, the lousy properties of the
> periodogram as estimator for the PSD is the sole reason
> for using windows at all.
>
> The variance of each periodogram coefficient is
>
> Var[P(k)] = P(k)^2
>
> The way to handle this is to average several coefficients,
> ether by computing several shorter (but all of same length)
> periodograms and compute the PSD estimate as the average
> of the periodograms, or by computing the PSD estimate as
> the weighted average of adjacent coefficients from the same
> peiodogram. Or both.
>
> With the N-1-period window function all periodogram
> coefficients contribute to each estimated PSD coefficient.
> This is the spectrum leakage.
>
> *********************
> Do note that the general spectrum leakage effect is
> the justification for using windows at all. One might want
> to control it better at times, but one does *not* want to
> avoid it!
> *********************
>
> Compare this to the N-period window functions, where
> each estimated PSD coefficient is computed as the
> average of 3 or 5 adjacent periodogram coefficients,
> depending on the type of window. One might wonder
> how much of an improvement this gives, compared to
> the 'raw' periodogram?
>
> --------
>
> To summarize:
>
> N-period windows
>
> - Serve no 'operational' purpose that can not be handled
>   at least as well by e.g. Parks-McClellan designs.
> - Are a pedagogical minefield when teaching filter
>   design at DSP entry-level.
> - Blatantly undermine the core justification for using
>   windows at all, for non-parametric PSD estimation.
>
> So why use them at all?
>
> Rune

It would be nice to discuss this thread with you when you have had
time to read more of the thread's content.

Dale B. Dalrymple

Those who don&#4294967295;t read are no better off than those who can&#4294967295;t.
&#4294967295; Mark Twain

On 13 Apr, 04:27, dbd <d...@ieee.org> wrote:
> On Apr 12, 3:10 am, Rune Allnor <all...@tele.ntnu.no> wrote:

> > To summarize:
>
> > N-period windows
>
> > - Serve no 'operational' purpose that can not be handled
> > &#4294967295; at least as well by e.g. Parks-McClellan designs.
> > - Are a pedagogical minefield when teaching filter
> > &#4294967295; design at DSP entry-level.
> > - Blatantly undermine the core justification for using
> > &#4294967295; windows at all, for non-parametric PSD estimation.
>
> > So why use them at all?
>
> > Rune
>
> It would be nice to discuss this thread with you when you have had
> time to read more of the thread's content.

You might want to review the comments of pseudoscience,
e.g.  http://skepdic.com/pseudosc.html. Pseudoscience
is seen as '...set of ideas based on theories put forth
as scientific when they are not scientific.'

The definition of science is separated in several items:

Science ... is

(a) being based on empirical observation rather
    than the authority of some sacred text;

I made clear my empirical observations in my previous
post, leading to conclusions summarized above. I have
seen no arguments of yours to answer my questions
or counter my arguments, except a couple of references
to Harris' paper, which plays the role of a "sacred
text."

(b) explaining a range of empirical phenomena;

I have made the effort to argue why my observations
are valid and the statements in the 'sacred paper'
are troublesome. I have seen no counterarguments from
you to correct any flaws or mistakes I've made,
except another reference to the 'sacred paper'.

c) being empirically tested in some meaningful way,
   usually involving testing specific predictions
   deduced from the theory;

I have repeatedly asked what useful purpose Harris'
results provide, without any trace of a useful
answer.

(d) being confirmed rather than falsified by empirical
    tests or with the discovery of new facts;

Not too relevant in this context, as Harris presumably
is formally correct. However, his timing was way off,
since FIR filter design by window functions was obsolete
by the time of publication, as the Parks-McClellan
method had long since become available. I still haven't
seen any arguments why his frequency domain convolution
method would be relevant at all in the context of PSD
estimation.

e) being impersonal and therefore testable by anyone
   regardless of personal religious or metaphysical beliefs;

I have never met Harris, worked with him or had anything
to do with him except browse his paper. I have no idea
what your personal relation with the guy might be, although
I am wondering if you might have some personal interest in
this discussion.

f) being dynamic and fecund, leading investigators to new
   knowledge and understanding of the interrelatedness of
   the natural world rather than being static and stagnant
   leading to no research or development of a better
   understanding of anything in the natural world;

I don't know about you, but it has happened on a few
occasions with me that I started out with rather convoluted
ideas, which became clearer, more simplified and easy to
follow, as work progressed. My questions should be read with
such efforts in mind. I'm not claiming Harris was wrong.
I'm only trying to understand why his paper and results
should be regarded as important.

You come across as not too willing to help out, which
reinforces my perception of you regarding the paper as
somehow 'sacred', which in turn leads me to question if
you know Harris personally, and thus have some sort of
personal stakes invested, or have some other form of
personal bias.

(g) being approached with skepticism rather than gullibility,
    especially regarding paranormal forces or supernatural
    powers, and

Well, there is obviously no paranormal or supernatural
aspects of Harris' paper, but I have made repeated efforts
to ask sceptic questions about why it is important. With
no useful responses.

h) being fallible and put forth tentatively rather than
   being put forth as infallible or inerrant.

This is the reason why I looked up this pseudo science
page at all: The way you are totally unwilling to do
discuss in any other way than posting refernces to the
Harris paper, you come across as regarding Harris as
infallible, inerrant and omniscient, and his work to
be unquestionably important.

Now, no one except discussions on comp.dsp to follow
scientific standards. Most people make the effort to
give the gist of algorithms, methods, ideas and
concepts as a guideline for readers when they go to
the textbooks or the journal literature.

Anyone who wants to, and have the time, can find out
*how* to do something. You have done nothing in this
thread but post references to Harris' paper. Could you
please make a token effort to explain *why* it would
be worth the effort to read the paper?

That is, *why*fast frequency domain convolution is
relevant for contemporary DSP practitioners who have
no personal relations to Harris?

Of course, I expect a useful answer to state what purpose
the convolution is supposed to serve in the first place,
so that a sceptic reader can decide for himself if the
objective is met in the end.

Rune

Rune Allnor wrote:

> Of course, I expect a useful answer to state what purpose
> the convolution is supposed to serve in the first place,
> so that a sceptic reader can decide for himself if the
> objective is met in the end.


In order to answer wouldn't you have to know which window function was
going to be used in the time domain and what exactly is the purpose that
procedure served? 

I do not see where the OP specifically provided that information. He
only asked about how to convert a time domain operation to the
equivalent frequency domain operation without specifying exactly what
purpose either might serve. It sounded to me like he was experimenting.

	You prefer that he not do this. You prefer that he use only the methods
you specify. You want him to use a time domain window (you haven't said
which one or why) and do a series of discrete FFT's instead of using 
sliding DFT algorithm. I'm a skeptical reader why do you think I'm going
to be convinced your method will meet the objective in the end? Your
position seems absurd (given that the OP hasn't clearly revealed what
the objective is).

-jim

Rune Allnor wrote:
[nececssarily trimmed here...]
>..
> Not too relevant in this context, as Harris presumably
> is formally correct. However, his timing was way off,
> since FIR filter design by window functions was obsolete
> by the time of publication, as the Parks-McClellan
> method had long since become available. I still haven't
> seen any arguments why his frequency domain convolution
> method would be relevant at all in the context of PSD
> estimation.

In "creative" audio, many users fancy drawing some arbitrary frequency 
response in  a VST plugin, say (literally, with the mouse, graphic pen 
or whatever), and hope to hear a corresponding result. This drawing may 
well include zeroing one or more frequency bins, brick walls etc, but 
most usually the idea is simply to be able to draw an arbitrary EQ shape 
(Voxengo has one such, there are probably many others). Internally, this 
will likely need the windowing method, as this is manifestly not a 
design from a formal filter description. Savvy users understand that 
what they get may not be exactly what they ask for. So while the 
windowing  method may well be obsolete in terms of formal filter design, 
we musos still like the feeling of uniqueness and power that comes from 
freehand drawing just about anything, including FFT responses.

Where did PSD estimation come into the discussion? The OP's stated 
application was pitch detection, for which (given a frequency-domain 
approach) windowing is certainly necessary to expose as many genuine 
component peaks as possible, and thus papers discussing frequency-domain 
windowing remain relevant.

For the record: my own application of the SDFT is in making a sliding 
phase vocoder (SPV), where we want to do all sorts of Cool Stuff such as 
pitch scaling and arbitrary modulation of bins/components. The bandwidth 
of each bin is the same - the whole frequency range (in the SPV 
resynthesis is by oscillator bank), so any process that needs to 
consider bin amplitudes whether for peak detection or other "scientific" 
stuff will need the DFT frames to be windowed. I played with  a number 
of cos^N  windows (generously described and evaluated in the Harris 
paper which is ~still~ relevant and useful IMO), but ended up sticking 
with Hann. The SPV is ~very~ costly in CPU terms but "embarrassingly 
parallel" (which is why we are exploring SIMD acceleration), but it 
offers low latency (when we get suitable hardware to do it in real time) 
and complete freedom to frequency shift or modulate each and any bin to 
any amount limited only by Nyquist. I have even invented/discovered a 
new effect - "Transformational FM", where an arbitrary input signal is 
treated like a classic 'carrier' for Chowning-style FM, and where the 
modulating signal (applied to each bin, or to any arbitrary subest of 
them) can be any frequency within the Nyquist range. You get the same 
sideband behaviour you get from classic FM. This ~requires~ the hopsize 
= 1 nature of the SDFT.

So, in discussing these arcane techniques, I hope that they are not 
dismissed only because no, um, "scientific"  process is considered to 
require them!

Richard Dobson

On 15 Apr, 15:38, jim <"sjedgingN0Sp"@m@mwt,net> wrote:
> Rune Allnor wrote:
> > Of course, I expect a useful answer to state what purpose
> > the convolution is supposed to serve in the first place,
> > so that a sceptic reader can decide for himself if the
> > objective is met in the end.
>
> In order to answer wouldn't you have to know which window function was
> going to be used in the time domain

No. The purpose of a window function doesn't depend on
the exact type of window function. You first decide to
use the window design method (as opposed to, say, Parks-
McClellan) to come up with a FIR filter. Then you decide
what window function to use. There might be applications
where particular widows are 'standard', where you just
stick to what is already common practice, or you might
want a little more leeway, like with the Kaiser window.

> and what exactly is the purpose that
> procedure served?

Huh? As I said before, I know of two purposes to use
window functions, filter design and PSD estimation.
If somebody knows about other uses, I would like to
hear about them. I'm always willing to learn something
new.

> I do not see where the OP specifically provided that information. He
> only asked about how to convert a time domain operation to the
> equivalent frequency domain operation without specifying exactly what
> purpose either might serve. It sounded to me like he was experimenting.

It sounded to me that he didn't know why he needed
the window.

> &#4294967295; &#4294967295; &#4294967295; &#4294967295; You prefer that he not do this.

Nope. I argued that his way of doing things

1) is computationally inefficient for the N-1-period
   windows
2) has no obvious purpose, for the N-period windows

> You prefer that he use only the methods
> you specify.

This is USENET. Neither you or I can force the OP in
any direction at all.

>  You want him to use a time domain window (you haven't said
> which one or why) and do a series of discrete FFT's instead of using
> sliding DFT algorithm. I'm a skeptical reader why do you think I'm going
> to be convinced your method will meet the objective in the end? Your
> position seems absurd (given that the OP hasn't clearly revealed what
> the objective is).

My position might seem absurd in context with the OP.
However, a totally separate discussion started with
this post of mine:

http://groups.google.no/group/comp.dsp/msg/be1c2b9af37a1641?hl=no

I made the effort to ask a very clear, specific question
that ought to have an equally clear specific answer.

If you use the explicit window functions at all, first
of all, find out *why* the window is needed. DFT is a
science, where everything you do has a purpose. If you don't
know the purpose, you are basiccally meddling with
voodoo and mysticism. Hence my reference to pseudoscience.

Once you have found out what the purose is, you can start
evaluating different computational approaches. *If* it turns
out that the argument for using the window is the same as
in PSD estimation - that the variance of spectrum ceofficients
is too large - then the 3pt convolution kernel will not help
a lot.

In any case, once one knows why one do these things
in the first place, one can decide what to do:

1) Skip the explicit window computations to save FLOPS
2) Do the whole round-trip with the N-1-period
   window to get acceptable results
3) Approximate the 'ideal' 3pt convolution in
   other ways

One way of approximating the results might be to save a
few previously computed spectra and average the k'th
coefficients of the different spectra instead.

Only when you know what you aim to achieve, can you
start discussing how to go about achieving it.

Rune

On 15 Apr, 16:49, Richard Dobson <richarddob...@blueyonder.co.uk>
wrote:
> Rune Allnor wrote:
>
> [nececssarily trimmed here...]
>
> >..
> > I still haven't
> > seen any arguments why his frequency domain convolution
> > method would be relevant at all in the context of PSD
> > estimation.
...
> Where did PSD estimation come into the discussion? The OP's stated
> application was pitch detection, for which (given a frequency-domain
> approach) windowing is certainly necessary to expose as many genuine
> component peaks as possible, and thus papers discussing frequency-domain
> windowing remain relevant.

So you have a messy (magnitude) spectrum you would
like to 'clean up' to be better able to see what
is 'actual' spectral features and what is just
noise and random fluctuations?

If my interpretation is correct, what you have is
a real-life application for PSD estimation. Just for
fun, try to use the 'proper' N-1-period windows and
see how the results compare to both the 'raw' spectrum
and the 3pt kernel spectrum. You'd presumably want
to do this with recorded data, not on-line.

My prediction is that the 3pt averaged spectrum will
be a lot closer to the 'raw' spectrum, but the N-1-
period windowed spectrum will show smoother spectral
features.

I won't have any opinions about what method to use
(that would depend on what you look for in the spectra),
just ask you to try to be aware what you are doing and
why. From the above experiment you might end up with
the conclusion that you don't need the windows at all.

A more interesting outcome might be that you start
experimenting with weighted averages in spectrum domain,
where the weight coefficients have nothing to do with
the 'classic' window functions at all. If all you do
is to compute weighted averages in spectrum domain, why
constrain the weight coefficients by time-doamin
properties?

Rune