Thread Subject: how to reverse windowing effect?

Greetings,

I'd like to apply the blackman-harris window to my real-
time data array, before taking its FFT and applying a
frequency-domain filter to it.

My question is, when I then do the inverse FFT, how do I
reverse the effect of windowing (in this case using
blackman-harris 4 term, -92db) so that the resulting real-
time waveform is as accurate as possible?

Is there some equation I can simply apply? I see a lot of
references to windowing in the literature, but no
information about how to reverse the effect of windowing
when going back from the frequency to the time domain.
Looking for practical advice how to compute this.

Best regards, -GGK

"ggk giust" <ggkmath@comcast.net> wrote
> I see a lot of
> references to windowing in the literature, but no
> information about how to reverse the effect of windowing
> when going back from the frequency to the time domain.

That's because it is not possible. Some operations, such as
the FFT for example do not destroy information and thus are
completely reversible. Other operations are not.

Consider an operation on a block of data where each point is
replaced with the average of the current point and the
previous point (i.e. blk(k) = (blk(k) + blk(k-1))/2.
(I sometimes call this the "1 1" filter). Clearly the result
is smoother than the input. Now would you expect this
operation to be reversible? ... I hope not :)

Windowing is much the same thing, and you can think of it as
a smoothing filter in the frequency domain. For instance the
Hanning window is a "1/4 1/2 1/4" filter in the frequency
domain. Regardless of whether you are smoothing in the
frequency domain or the time domain, information is lost and
you can't reverse the operation.

~Paul

On May 19, 4:59 pm, "ggk giust" <ggkm...@comcast.net> wrote:
> Greetings,
>
> I'd like to apply the blackman-harris window to my real-
> time data array, before taking its FFT and applying a
> frequency-domain filter to it.
>
> My question is, when I then do the inverse FFT, how do I
> reverse the effect of windowing (in this case using
> blackman-harris 4 term, -92db) so that the resulting real-
> time waveform is as accurate as possible?
>
> Is there some equation I can simply apply? I see a lot of
> references to windowing in the literature, but no
> information about how to reverse the effect of windowing
> when going back from the frequency to the time domain.
> Looking for practical advice how to compute this.
>
> Best regards, -GGK

A few thoughts:

1) There is no need to apply a window just to implement a frequency
domain filter.

2) If you want to generate a windowed power spectrum from the data you
are filtering, apply the window in the frequency domain after the FFT
and after pulling off the unwindowed frequency domain data for the
filter processing. The window you suggest belongs to the family of
cosine-summed filters that can be applied as small convolutions in the
frequency domain.

3) Why are you considering the 4-term -92 db window instead of the
correctly optimized 4-term -98 dB version Nuttall published in a
correction to the harris paper?

4) Windows can be applied as a matrix multiply in the frequency domain
after the FFT. For the cosine-summed windows, this matrix has only
near diagonal elements. For a discussion of the conditions under which
the matrix is invertible and can be used to remove the windowing see
section V of the article:
Practical methods for rapid and accurate computation of
interferometric spectra for remote sensing
applications
Barnet, C.D. Blaisdell, J.M. Susskind, J.
Gen. Sci. Corp., Beltsville, MD, USA ;
Geoscience and Remote Sensing, IEEE Transactions on
Jan. 2000 Volume: 38 , Issue: 1 page(s): 169 - 183

5) For examples of the use of windows in a transform-modify-
inverse_transform context, look at pre and post processing used in
audio compression schemes like MP3. Also look in the music analysis/
synthesis literature.

I hope that will give you a few ideas to consider.

Dale B. Dalrymple
http://dbdimages.com

Thanks,

Is the Nuttall window you describe above called the
Blackman-Nuttall window in this link?

http://en.wikipedia.org/wiki/Window_function#Nuttall_window.
2C_continuous_first_derivative

The only paper reference I could find on the internet for
Nuttall was the following:

A.H. Nuttall, “ Some Windows with Very Good Sidelobe
Behavior”, IEEE Transactions on Acoustics, Speech, and
Signal Processing, Volume 29, Issue 1, February 1981, pp.
84 – 91.

Does the paper call it the Nuttall window? Thanks again, GGK

On May 20, 7:26 am, "ggk " <ggkm...@comcast.net> wrote:
> Thanks,
>
> Is the Nuttall window you describe above called the
> Blackman-Nuttall window in this link?
>
> http://en.wikipedia.org/wiki/Window_function#Nuttall_window.
> 2C_continuous_first_derivative
>
> The only paper reference I could find on the internet for
> Nuttall was the following:
>
> A.H. Nuttall, “ Some Windows with Very Good Sidelobe
> Behavior”, IEEE Transactions on Acoustics, Speech, and
> Signal Processing, Volume 29, Issue 1, February 1981, pp.
> 84 – 91.
>
> Does the paper call it the Nuttall window? Thanks again, GGK

Nuttall calls it the minimum 4-term window. The coefficients are given
in (37) on page 89.

Knowledgeable window selection is about tradeoffs. Nuttall provides
enough examples with parameters to choose the best cosine-summed
window up to 4 terms for most applications.

Nuttall describes so many windows in this and other papers that
'Nuttall window' has no useful descriptive value. The term 'Blackman -
harris' has also been used for enough different things by enough
authors to be meaningless by itself. Your inclusion of "4 term, -92dB"
was quite appropriate and was the needed information that many people
leave off.

Your wki reference is, well, a wiki reference. It has some good
information and more. It references good papers by harris and Nuttall
but the descriptions of the papers show a lack of competence in the
windowing literature and are grossly misleading. So read the
references and take the rest as pretty pictures and probably having
had good intentions. The equations given have probably been copied
accurately. The interpretive comments are dubious.

Dale B. Dalrymple

On 20 Mai, 01:59, "ggk giust" <ggkm...@comcast.net> wrote:
> Greetings,
>
> I'd like to apply the blackman-harris window to my real-
> time data array, before taking its FFT and applying a
> frequency-domain filter to it.
>
> My question is, when I then do the inverse FFT, how do I
> reverse the effect of windowing (in this case using
> blackman-harris 4 term, -92db) so that the resulting real-
> time waveform is as accurate as possible?
>
> Is there some equation I can simply apply? I see a lot of
> references to windowing in the literature, but no
> information about how to reverse the effect of windowing
> when going back from the frequency to the time domain.
> Looking for practical advice how to compute this.

So you want to apply a window and then reverse the effects
of the same window? That inspires the question why you think
you want to apply the window in the first place. Keep in
mind that windowing is not a voodoo ritual that needs to be
performed in a seanse to please the powers of the CPU.

Windowing is a technique which serves a very specific purpose.

The shortish story is that 'windowing' is one of many ways to
design FIR filters. The method is appealing because FIR
filters are simple to implement (there are no weird numerical
effects to consider) and FIR design by windowing is merely
a cookbook exercise with no need for fancy software.

Now, the windowing method is based on first finding a finite-
length approximation of an ideal FIR filter, which is of
infinite length. Truncating the ideal filter causes
certain non-ideal effects to appear, most notably what
is known as spectral leakage. There is no way to avoid
this, so from here on the filter design problem consists
of balancing a number of 'bad' factors:

- Stop-band attenuation
- Filter length
- Transition bandwidth

The different window functions have different properties:
Some give short filters but mediocre stop band attenuation.
Others give excellent stop band attenuation, but result
in filters that have lots of coefficients and wide
transition bands.

And so on.

The very short story is that you have to accept some
'degradation' of the filtered signal. It is your
responibilty as system designer to select a filter which
cleans up the data while avoiding to distort the data
too badly.

Rune

Dale, thanks... in your text

"Nuttall calls it the minimum 4-term window. The
coefficients are given in (37) on page 89."

is (37) referencing a paper? Or is it just page 89 of the
Nuttall paper I referenced above?

Rune, thanks... I need to apply a window to separate the
spurs from the random background noise. Then apply a
bandpass filter to the result, take the inverse FFT, and
reverse the effect of the window to get a real-time
waveform to measure the PDF of zero-crossings (my ultimate
goal).

However, based on the response, it appears I'll need to re-
think my methodology to remove the random noise from the
real-time waveform. Assuming my windowing allows me to
identify the relevant spurs in the waveform, how can I use
this information to re-create an accurate real-time
waveform having only these spurs in it (and not the random
noise)? Perhaps a real-time filter with bandpasses only at
those spur frequencies identified by the windowing...?

Any recommendation for a new methodology, as reversing the
effect of the windowing seems to out of the question. I
wonder if I could just throw out the edges of the real-
time waveform and use the center? (But I suspect the
center is modified by windowing as well).

On May 20, 3:33 pm, "ggk " <ggkm...@comcast.net> wrote:
> Dale, thanks... in your text

> "Nuttall calls it the minimum 4-term window. The
> coefficients are given in (37) on page 89."
>
> is (37) referencing a paper? Or is it just page 89 of the
> Nuttall paper I referenced above?

(37) is the equation number in the paper where the coefficient values
are given.

Of the dozens of windows Nuttall has described, this one is the one
that Matlab calls "nuttallwin" although there is no way to tell that
from the documentation without looking to see if the coefficients are
the same as in (37) on page 89 of the Nuttall paper. (They are.)

> Rune, thanks...

Windowing is still not always irreversible. As Rune points out,
windowing may not even be needed for what you say you want to achieve.

Go back to my original suggestion 5). You want to perform a transform-
modify-inverse-transform process. So do the audio compression people.
They compress and decompress as their 'modify' and apply windows
complementary and compatible with reconstruction. Your 'modify' seems
to be noise removal. Google on 'spectral subtraction' for an extensive
literature on that topic.

Good luck

Dale B. Dalrymple

In the ideal world, reverse windowing effect could be
possible, and what people calls "deconvolution".

Convolution is multiply the signal with the kernel (windows
- flipped if you are purist) in the frequency domain.
Deconvolution consists thus of dividing the signal by the
kernel, in the frequency domain of course.

Deconvolution is an "ill-posed" problem, and must be treated
with care. Adding a regularization term is one way. One of
the technique for e-blurring image is deconvolution.

Bruno