Window functions

"Jon Harris" <goldentully@hotmail.com> wrote in message news:<2pjm2kFlrvruU1@uni-berlin.de>...
> "Stan Pawlukiewicz" <spam@spam.mitre.org> wrote in message
> news:ch24rc$4v6$1@newslocal.mitre.org...

> >    IMHO the last significant paper on window filter synthesis was
> > written by Kaiser back in the 50's where he introduced the Kaiser window
> > as as an approximation of the zeroth order spherical prolate window.
> 
> That may be true, but the windowing technique can be very useful when you need
> to calculate filter coefficients "on the fly".  Computationally, it is much
> simpler than the optimized methods.  So while it might be sub-optimal, I
> wouldn't say it is obsolete.

Yes, Jon, that's why I'm playing with the windows. The Remez algorithm 
is available under matlab, but you need matlab to use it, one doesn't 
learn much DSP by plugging in the numbers, and it's a bit too complicated 
for me to attempt to implement it myself. I am in the process of learning 
how to use some new toys of mine, more specifically a C++ compiler under 
windows. I have used C++ before, but only under UNIX.

The main reason is that a couple of other threads recently have made it 
clear to me that I'm not quite as up-to-date on the trivial details 
on filter design by windosws, that I might have wanted to...

Anyway, I thought that I could use an example program that forces me to 
learn the basics of the compiler, and that even might be useful afterwards 
without me getting bogged down with all sorts of numerical subtleties
in the mean time. 

Hence a program for design and analysis of filters designed by windowing.  
I have the basics up and running (although there are stiil a few flies 
and other bugs left in the code), so I thought "why not try to include 
these awkward windows, if it's not too much fuzz".

Rune

Jerry Avins <jya@ieee.org> wrote in message news:<4134a7c1$0$19705$61fed72c@news.rcn.com>...
> Stan Pawlukiewicz wrote:

> >   IMHO the last significant paper on window filter synthesis was written 
> > by Kaiser back in the 50's where he introduced the Kaiser window as as 
> > an approximation of the zeroth order spherical prolate window.
> 
> But Stan, windows are used for more than filter design. The prime
> example is windowing a set of samples to minimize the artifacts caused
> by non-periodicity. The sidelobe width that is readily seen in a filter
> also characterizes the way a window in that use trades resolution for
> artifact reduction.
> 
> Rune knows how to design filters. It's my guess that he's looking at
> windows for their effect on data.

That too (I made some comments on my purposes in a reply to Jon Harris).

There *is* the slightly embarrasing point that an MSc student took me  
completely by surprise a few months ago, when he worked with the same 
data I had used in my PhD thesis.

As you know, I work with seismic data. These data are already collected, 
and all data are available to me when I first sit down to do whatever 
processing on them. So all those concerns about causality and efficient
implementations of filters that are so crucial in on-line applications, 
don't really apply to my application. This leaves me with a certain 
degree of freedom others might not have, but more importanntly, it causes 
me to get sloppy. 

More specifically, instead of making a low-pass filter with cutoff 
at 10 Hz, I used to compute the spectrum of the data by FFT, zero out 
all the coefficients above 10 Hz, and transform back to time domain. 

This "filter" was only a means for visual inspection of the data, in 
order to identify certain waves and decide if subsequent analysis 
steps were possible. In that respect, my crude "filter" worked well.
The results of my attempts at filtering are seen in figure 3.7 of 
my PhD thesis, of which a PDF version is supposed to be available here:
http://www.fysel.ntnu.no/~allnor/thesis/thesis.pdf 

Now, last spring a student worked with the same data and wanted to 
reproduce the same plots I had made, and he (well with good help 
from his supervisor, who happened to have written a PhD thesis on 
filter banks) actually *designed* a filter to my crude spec, and 
applied it to the data. 

Suffice it to say that I got very embarrased when I saw the filtered 
data this student got out of it. There were nothing visible in his 
plots that I did not see in my own, but his looked much more "crisp"
while mine were very crude.

So yes, I'd like to make design tools that allow me to design and 
test filters in my own "outside-matlab" data processing flows, and 
see what effects they have on the data...

Rune

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<3YudnT5_xdBRbKncRVn-gw@centurytel.net>...
> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> news:f56893ae.0408310548.8ba60b4@posting.google.com...
> > Hi all.
> >
> > I'm playing a bit with window functions in filter design etc, and
> > have come across a couple of gruelling expressions. More specifically,
> > the Chebychev window [1, eq. 5-17], the Tukey window [2, table 8.1]
> > and the Lanczos window, [2, table 8.1].
> >
> > I would like to know how one estimates the width of the main lobe
> > for these filters, and how one uses the various control parameters.
> > Table 8.1 in P&M seems to contain quite a few typos, which does not
> > exactly help me understand what's going on.
> 
> Rune,
> 
> I'm going to note that you said "etc." and not worry about what you're going
> to do with the windows.  You may peek through them for all I care!  :-)
> 
> I don't recall a general method or figure or table that compares them -
> although fred harris or Al Nuttall may have done so.  I have a more
> arm-waving method.....
> 
> 1)  First you need to define how main lobe width will be measured.  -3dB
> points?  first zero points? etc.  Note that they are all pretty much the
> same at -3dB and can be quite different at the first zero point.

I think the first zero is a good way of doing things. It's fairly easy 
to find (at least for the "trivial" windows...), and as you say, 
the numbers can be very different for different windows. In practice, 
I suspect some sort of compromise would be more useful.

> 2)  Then, realize that the van der Maas functin provides the lowest
> (minimax) sidelobe for a given main lobe width - exept it's not physically
> realizable and the end points of the window are infinite as I recall.
> Nonetheless, it's a good data point.

Ouch! van der who? Never heard of neither the guy or his funcion. 
Oh well... 

> 3)  Also, realize that the rectangular window "sinc" isn't optimum in
> frequency in any particular way - regarding main lobe width or sidelobes.
> So this one isn't interesting.

No, not as such... (you might want to read my reply to Jerry...)
but it's a good refernce for comparision.

> 4)  The Dolph-Chebyshev window is an approximation to the van der Maas and
> is physically realizable.   So, presumably, this is the best you can do in
> combination of main lobe width vs. side lobe level.

I note that Rick uses the Chebychev quite a lot in his book. Which is 
why I got interested. The problem is how to use it. The maths is there, 
but I would like to see some cook-book rules of thumb. If one needs a 
numerical (or manual) optimization routine, I'm not quite that interested.
For now.

> 5) All of the others have some nice properties of their own but are less
> "good" in combination - wider main lobe / higher sidelobes - but perhaps
> with rapid sidelobe decay, easy to compute, etc.  Lyon's Figure 5-26 gives a
> pretty good idea of what's possible in the minimax case.  Everything else
> will be "worse" in the strict main lobe / sidelobe comparison.  Compare
> Kaiser beta=4 to gamma=1.5 for Dolph-Chebyshev.  The first sidelobes are
> nearly the same and the Kaiser main lobe is wider...

Exactly. That's the sort of things I'd be interested in checking out. 
The equations are OK and appear (I haven't attempted to implement them 
yet) to be easy to implement, given N, gamma, beta and what have you. 
I try to take the more design-oriented approach, in the sense that one 
provides a spec like type of window, cut-off frequency for pass band 
and stop-band, and other relevant parameters where such apply, and 
compute filter parameters from there. 

What I would like, is to get from this spec to at least an initial 
estimate for the filter, where perhaps some details can be adjusted to 
tweak the performance, but that does not completely depend on an 
iterative trial'n error approach.
 
Rune

Jerry Avins wrote:
> Stan Pawlukiewicz wrote:
> 
> > Jon Harris wrote:
> 
>    ...
> 
> >> That may be true, but the windowing technique can be very useful when 
> >> you need
> >> to calculate filter coefficients "on the fly".  Computationally, it is 
> >> much
> >> simpler than the optimized methods.  So while it might be sub-optimal, I
> >> wouldn't say it is obsolete.
> >>
> >>
> > 
> > Signal Processing with flies should be called FSP ;)
> 
> The dyslexics among us sometimes store data in flies.

I once saw a very neat cartoon, which somehow captured the conept of
(non-)commutativity very nicely. It contained two displays, which were
labeled: "Fly on a banana" and "Banana on a fly" (with appropriate
drawings, of course).

(She's sleeping now, so I have a moment of spare time :-)

Rune Allnor wrote:
> Suffice it to say that I got very embarrased when I saw the filtered 
> data this student got out of it. There were nothing visible in his 
> plots that I did not see in my own, but his looked much more "crisp"
> while mine were very crude.

Sounds to me like:
a) this student was standing on the shoulders of giants, and
b) Rune is one of the giants.

It's great that you see (and take) an opportunity to improve your 
knowledge, but I don't think you should be embarrassed.

-- 
Jim Thomas            Principal Applications Engineer  Bittware, Inc
jthomas@bittware.com  http://www.bittware.com    (603) 226-0404 x536
A pessimist is an optimist with experience

Andor wrote:

   ...

> (She's sleeping now, so I have a moment of spare time :-)

Those who didn't understand the reference should go to
http://users.erols.com/jyavins/bariska

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jim Thomas wrote:

> Rune Allnor wrote:
> 
>> Suffice it to say that I got very embarrased when I saw the filtered 
>> data this student got out of it. There were nothing visible in his 
>> plots that I did not see in my own, but his looked much more "crisp"
>> while mine were very crude.
> 
> 
> Sounds to me like:
> a) this student was standing on the shoulders of giants, and
> b) Rune is one of the giants.
> 
> It's great that you see (and take) an opportunity to improve your 
> knowledge, but I don't think you should be embarrassed.

I don't know about that. I'm always embarrassed about how na�ve I was
last week. It won't surprise me if this message embarrasses me tomorrow.

Rune,

There are a number of free P-M filter design programs available,
Scilab's and Octave's among them. The latest one I found is at
http://www.winfilter.20m.com/ and I'm sure you know that ScopeFIR from
http://www.iowegian.com/ has a free trial version.

For off-line use, window performance is really only important for
analysis. For filters, there are optimizing methods -- at least
equiripple and least squares -- and performance lost by using a
window design can be bought back with a few extra taps.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:f56893ae.0408312254.750357e4@posting.google.com...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:<3YudnT5_xdBRbKncRVn-gw@centurytel.net>...
> > "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> > news:f56893ae.0408310548.8ba60b4@posting.google.com...
> > > Hi all.
> > >
> > > I'm playing a bit with window functions in filter design etc, and
> > > have come across a couple of gruelling expressions. More specifically,
> > > the Chebychev window [1, eq. 5-17], the Tukey window [2, table 8.1]
> > > and the Lanczos window, [2, table 8.1].
> > >
> > > I would like to know how one estimates the width of the main lobe
> > > for these filters, and how one uses the various control parameters.
> > > Table 8.1 in P&M seems to contain quite a few typos, which does not
> > > exactly help me understand what's going on.
> >
> > Rune,
> >
> > I'm going to note that you said "etc." and not worry about what you're
going
> > to do with the windows.  You may peek through them for all I care!  :-)
> >
> > I don't recall a general method or figure or table that compares them -
> > although fred harris or Al Nuttall may have done so.  I have a more
> > arm-waving method.....
> >
> > 1)  First you need to define how main lobe width will be measured.  -3dB
> > points?  first zero points? etc.  Note that they are all pretty much the
> > same at -3dB and can be quite different at the first zero point.
>
> I think the first zero is a good way of doing things. It's fairly easy
> to find (at least for the "trivial" windows...), and as you say,
> the numbers can be very different for different windows. In practice,
> I suspect some sort of compromise would be more useful.
>
> > 2)  Then, realize that the van der Maas functin provides the lowest
> > (minimax) sidelobe for a given main lobe width - exept it's not
physically
> > realizable and the end points of the window are infinite as I recall.
> > Nonetheless, it's a good data point.
>
> Ouch! van der who? Never heard of neither the guy or his funcion.
> Oh well...
>
> > 3)  Also, realize that the rectangular window "sinc" isn't optimum in
> > frequency in any particular way - regarding main lobe width or
sidelobes.
> > So this one isn't interesting.
>
> No, not as such... (you might want to read my reply to Jerry...)
> but it's a good refernce for comparision.
>
> > 4)  The Dolph-Chebyshev window is an approximation to the van der Maas
and
> > is physically realizable.   So, presumably, this is the best you can do
in
> > combination of main lobe width vs. side lobe level.
>
> I note that Rick uses the Chebychev quite a lot in his book. Which is
> why I got interested. The problem is how to use it. The maths is there,
> but I would like to see some cook-book rules of thumb. If one needs a
> numerical (or manual) optimization routine, I'm not quite that interested.
> For now.
>
> > 5) All of the others have some nice properties of their own but are less
> > "good" in combination - wider main lobe / higher sidelobes - but perhaps
> > with rapid sidelobe decay, easy to compute, etc.  Lyon's Figure 5-26
gives a
> > pretty good idea of what's possible in the minimax case.  Everything
else
> > will be "worse" in the strict main lobe / sidelobe comparison.  Compare
> > Kaiser beta=4 to gamma=1.5 for Dolph-Chebyshev.  The first sidelobes are
> > nearly the same and the Kaiser main lobe is wider...
>
> Exactly. That's the sort of things I'd be interested in checking out.
> The equations are OK and appear (I haven't attempted to implement them
> yet) to be easy to implement, given N, gamma, beta and what have you.
> I try to take the more design-oriented approach, in the sense that one
> provides a spec like type of window, cut-off frequency for pass band
> and stop-band, and other relevant parameters where such apply, and
> compute filter parameters from there.
>
> What I would like, is to get from this spec to at least an initial
> estimate for the filter, where perhaps some details can be adjusted to
> tweak the performance, but that does not completely depend on an
> iterative trial'n error approach.

Rune,

The windowing approach doesn't lend itself to going directly to filter
characteristics. The windowing approach is handy in some situations but
imprecise. That's why the Parks-McClellan program is so prevalent.

The paper I wrote with Temes and Barcilon dealt with things like rise time,
rise time without over/undershoot, etc.  Otherwise, I view the minimax
design of windows as exactly the same problem as the minimax design of
filters.  If you can design a window using a numerical method, then you can
just as easily design a filter.

Maybe looking more carefully at the Kaiser window and its parameters would
give you more insight.

I often think of the windowing process as a convolution in frequency.  Start
with a "perfect" lowpass filter with response 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1
1.  You know that the time window is a sinc and that's probably not what you
want because there will be temporal aliasing.  Thus the need for a window.

By windowing in time, you will convolve the frequency response with the
frequency sinc-like function that has a time "window" of the sort we're
discussing here.  If you can envision the convolution being computed, you
can envision how sidelobes in the window frequency response affect the
resulting filter response.  - It's just not a very precise picture.....

Here's what I glean from this:
- the higher the sidelobes of the frequency domain version of the window,
the higher the ripples resulting in the convolved filter.
- the wider the main lobe of the frequency domain version of the window, the
wider the transition regions of the convolved filter.

Because the result is a convolution, the window characteristics in frequency
are averaged out by the ideal filter function.  So, precise window
characteristics are softened by that "filtering" process.  In other words,
maybe it doesn't matter as much as one might think - unless you have very
precise filter specifications indeed!

I hope this helps....

PS: van der Maas derived a continuous function that starts with a given main
lobe width between first zeros and computes the minimax sidelobe level going
to +/- infinity.  The sidelobes going to infinity are a sinusoid - so the
edges of the window have corresponding dirac functions.  Because this isn't
physically realizable, Dolph and Taylor and others came up with
approximations to the van der Maas function that *are* physically
realizable.  And, was Dolph doing it for discrete arrays?  I think so ....

Most of the literature is in antenna theory.

Fred

"Jerry Avins" <jya@ieee.org> wrote in message
news:4135f7f8$0$19704$61fed72c@news.rcn.com...
> Rune,
>
> There are a number of free P-M filter design programs available,
> Scilab's and Octave's among them. The latest one I found is at
> http://www.winfilter.20m.com/ and I'm sure you know that ScopeFIR from
> http://www.iowegian.com/ has a free trial version.
>

Hello Rune et. al.,

With a little proding I can make my "c" source code for a P-M algo
available. It was one of my earliest "c" programs. But it works quite well.
Plus the Remez portion operates in a stand alone fashion.

Clay

On 31 Aug 2004 06:48:59 -0700, allnor@tele.ntnu.no (Rune Allnor)
wrote:

>Hi all. 
>
>I'm playing a bit with window functions in filter design etc, and 
>have come across a couple of gruelling expressions. More specifically, 
>the Chebychev window [1, eq. 5-17], the Tukey window [2, table 8.1]
>and the Lanczos window, [2, table 8.1].
>
>I would like to know how one estimates the width of the main lobe 
>for these filters, and how one uses the various control parameters. 
>Table 8.1 in P&M seems to contain quite a few typos, which does not 
>exactly help me understand what's going on.
>
>Any comments or opinions are most welcome. 
>
>Rune
>
>[1] Lyons: Understanding DSP.  2nd ed., 
>           Prentice-Hall, 2004
>
>[2] Proakis & Manolakis: Digital Signal Processin - Principles, 
>           Algorithms and Applications. 3rd ed., Prentice-Hall, 1996.

Hi Rune,

   if you're looking for an equation that you 
can use to estimate mainlobe width, as a function 
of the Chebyshev gamma control parameter, 
I don't know of any such equation.  Sorry.

But speaking of windows, I'm beginning to believe that 
my equations for the Hanning and Hamming windows 
are incorrect!

My N-point Hamming equation, for example, is: 

w1(n) = 0.54 - 0.46*cos(2*pi*n/(N-1))        [1]
for n = 0,1,2,...,N-1.

My Eq. [1] agrees, by the way, with Proakis & Manolakis,
Opp & Schafer, MATLAB, etc.

If you plot the w1(n) samples in [1] give ya' this nice 
symmetrical window sequence where the first and last 
samples are both zero-valued.  However, I just discovered 
(maybe I knew this years ago and forgot) that the Fourier 
transform of Eq. [1]'s w1(n) does *not* give us the 
correct Fourier transform of a Hamming window!!

The correct N-point discrete Fourier transform (DFT) of an 
N-point Hamming window is three real non-zero samples.  
The amplitudes of those samples are 0.23N, 0.54N, and 
0.23N.  The imaginary part of the correct N-point DFT of 
an N-point Hamming window is all zeros.

The DFT of Eq. [1]'s w1(n) is neither real-only nor does 
it's freq-domain samples have the correct amplitudes.

I now think the correct N-point Hamming equation 
should be: 

w2(n) = 0.54 - 0.46*cos(2*pi*n/(N))        [2]
for n = 0,1,2,...,N-1.

If you plot w2(n) in the time domain it does not "look 
symmetric".  The w2(n) sequence's first and last samples 
are not equal.  But the DFT of Eq. [2]'s w2(n) is real-only 
and it's freq-domain samples do have the correct amplitudes
(0.23N, 0.54N, and 0.23N).

I want to call w2(n) "DFT symmetric", because if we circularize 
(is that a word) it, by repeating it over and over, making 
it periodic, then it becomes symmetrical.

I know I know, the difference between w1(n) and w2(n) becomes 
smaller and smaller as N becomes larger.

Anyway, I'm thinking that there are two different types of 
symmetry: "linear symmetry" and "DFT symmetry".  And 
that window functions should always be "DFT Symmetric".
And maybe I should change the equations in my book with 
regard to the Hanning and Hamming windows.

OK, this my rant of the day.
See Ya',
[-Rick-]