Windowing in the Frequency Domain

>Rune Allnor wrote:
>> On 4 Apr, 18:28, "OldUncleSilas" <gibbering.babo...@gmail.com>
>> wrote: 
>
>>> I'm currently working on a pitch identification program in
>>> MATLAB. &#65533;It uses the Sliding DFT so I need to apply windowing
>>> functions in the frequency domain.
>> 
>> Ouch... I am not aware of a single application where
>> windows are applied in frequency domain...
>
>The application is when you have a spectrum in hand and the window's 
>spectrum has small support.
>
>>> I understand this is done by convolution and have managed to
>>> find the kernel for the von Hann window: [-0.25 0.5 -0.25], but
>>> am struggling to find a concrete answer for other windows like
>>> the Hamming and Blackman window.
>
>It's always the transform of the time-domain window function. For 
>windows defined as cosine sums, like your other examples, that means 
>the central kernal value is the window's constant term and the other 
>values are half the coefficients on the cosines; half because each 
>occurs twice.
>
>>>&#65533;And why doesn't cconv(A,[-0.25 0.5 -0.25]) give a result that's
>>> the same size as A?
>
>Read the documentation: "If you omit n, it defaults to 
>length(a)+length(B)-1. When n = length(a)+length(B)-1, the circular 
>convolution is equivalent to the linear convolution computed with 
>conv."
>
>
>Martin
>
>-- 
>Quidquid latine scriptum est, altum videtur.
>

Many thanks to you sir.  So Hamming is [-0.23 0.54 -0.23] and Blackman
[0.04 -0.25 0.42 -0.25 0.04].

On Sat, 04 Apr 2009 13:42:31 -0500, "OldUncleSilas"
<gibbering.baboons@gmail.com> wrote:

>Hello, thanks for the help
>
>>On 4 Apr, 18:28, "OldUncleSilas" <gibbering.babo...@gmail.com> wrote:
>>> Hello there,
>>> I'm currently working on a pitch identification program in MATLAB.
>=A0It
>>> uses the Sliding DFT so I need to apply windowing functions in the
>>> frequency domain.
>>
>>Ouch... I am not aware of a single application where
>>windows are applied in frequency domain...
>
>
>It is impossible to window in the time domain when using the SDFT, so I
>must do that process in the frequency domain.

Hello OldUncleSilas,
   Like you, for years I thought (assumed) there was no 
way to perform time-domain windowing when using the 
SDFT.  As it turns out (the following is NOT a drug 
or alchohol-induced statement) there *IS* a way 
to perform time-domain windowing when using the 
SDFT.

An engineer from the Netherlands, John A. Scholz, showed 
me how to do that back in 2004.  Sadly, I can't find 
any of the old E-mails between John and me.

Good Luck,
[-Rick-]

On 10 Apr, 01:37, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:

> &#4294967295; &#4294967295;Like you, for years I thought (assumed) there was no
> way to perform time-domain windowing when using the
> SDFT. &#4294967295;As it turns out (the following is NOT a drug
> or alchohol-induced statement) there *IS* a way
> to perform time-domain windowing when using the
> SDFT.

Leaving the 'how' aside, *why* would anyone want
to do that?

I can't think of any application outside optics where
measurements are done directly in spectral domain?
One starts with a sequence of temporal (or spatial)
measurements and applies one or more DFTs (or
equivalent filtering operations) to do the conversion
to spectrum domain.

If we start out with a sequence of DFTs, spectrogram
style, and want to use a (temporal) window function
to smooth the spectrum, why not do the window
computations directly in time domain, once and for all?

The OP's post is a bit ambiguous on exactly what
he is doing. On first reading I interpreted the post differently,
but it might be interpreted as if he deals with legacy code.
If that's the case, and this code does not allow users to
specify window functions, that's reason enoght to abandon
the legacy code and reimplement.

If the OP has access to all the source code, I can't see any
reason whatsoever to start messing with these things in
frequency domain.

Rune

Rune Allnor wrote:
> 
> On 10 Apr, 01:37, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
> 
> >    Like you, for years I thought (assumed) there was no
> > way to perform time-domain windowing when using the
> > SDFT.  As it turns out (the following is NOT a drug
> > or alchohol-induced statement) there *IS* a way
> > to perform time-domain windowing when using the
> > SDFT.
> 
> Leaving the 'how' aside, *why* would anyone want
> to do that?
> 
> I can't think of any application outside optics where
> measurements are done directly in spectral domain?
> One starts with a sequence of temporal (or spatial)
> measurements and applies one or more DFTs (or
> equivalent filtering operations) to do the conversion
> to spectrum domain.
> 
> If we start out with a sequence of DFTs, spectrogram
> style, and want to use a (temporal) window function
> to smooth the spectrum, why not do the window
> computations directly in time domain, once and for all?

maybe because he doesn't want it to be so permanent.

> 
> The OP's post is a bit ambiguous on exactly what
> he is doing. On first reading I interpreted the post differently,
> but it might be interpreted as if he deals with legacy code.
> If that's the case, and this code does not allow users to
> specify window functions, that's reason enoght to abandon
> the legacy code and reimplement.

What he is doing sounded pretty simple to me. The time domain windows he
is encountering are just simple raised cosine functions. And that means
he can do the windowing in the frequency domain by  convolving with a
simple (i.e. short) kernel that is just derived directly from the
coefficients of his time domain function. 
	I guess the issue is that with a sliding dft the large number of window
functions that need to be implemented becomes computationally expensive.
And that convolving with a kernel of length 3 in the frequency domain is
slightly faster than multiplying with a window length N in the time
domain. Plus the whole effect of the time domain window function is
really just to shape the impulse response of that convolution kernel so
he might just as well work directly with the impulse response of
convolution kernel using some of the conventional time domain windows as
a starting point.

-jim  

> 
> If the OP has access to all the source code, I can't see any
> reason whatsoever to start messing with these things in
> frequency domain.
> 
> Rune

OldUncleSilas wrote:
> 
> >Rune Allnor wrote:
> >> On 4 Apr, 18:28, "OldUncleSilas" <gibbering.babo...@gmail.com>
> >> wrote:
> >
> >>> I'm currently working on a pitch identification program in
> >>> MATLAB. &#65533;It uses the Sliding DFT so I need to apply windowing
> >>> functions in the frequency domain.
> >>
> >> Ouch... I am not aware of a single application where
> >> windows are applied in frequency domain...
> >
> >The application is when you have a spectrum in hand and the window's
> >spectrum has small support.
> >
> >>> I understand this is done by convolution and have managed to
> >>> find the kernel for the von Hann window: [-0.25 0.5 -0.25], but
> >>> am struggling to find a concrete answer for other windows like
> >>> the Hamming and Blackman window.
> >
> >It's always the transform of the time-domain window function. For
> >windows defined as cosine sums, like your other examples, that means
> >the central kernal value is the window's constant term and the other
> >values are half the coefficients on the cosines; half because each
> >occurs twice.
> >
> >>>&#65533;And why doesn't cconv(A,[-0.25 0.5 -0.25]) give a result that's
> >>> the same size as A?
> >
> >Read the documentation: "If you omit n, it defaults to
> >length(a)+length(B)-1. When n = length(a)+length(B)-1, the circular
> >convolution is equivalent to the linear convolution computed with
> >conv."
> >
> >
> >Martin
> >
> >--
> >Quidquid latine scriptum est, altum videtur.
> >
> 
> Many thanks to you sir.  So Hamming is [-0.23 0.54 -0.23] 

That sounds correct if the window function is of the form:

 0.54*cos(0*w) + 0.46*cos(1*w)  [w is something like 2*n*pi/(N-1)]



>and Blackman
> [0.04 -0.25 0.42 -0.25 0.04].

On 11 Apr, 14:57, jim <"sjedgingN0Sp"@m@mwt,net> wrote:
> Rune Allnor wrote:
>
> > On 10 Apr, 01:37, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
>
> > > &#4294967295; &#4294967295;Like you, for years I thought (assumed) there was no
> > > way to perform time-domain windowing when using the
> > > SDFT. &#4294967295;As it turns out (the following is NOT a drug
> > > or alchohol-induced statement) there *IS* a way
> > > to perform time-domain windowing when using the
> > > SDFT.
>
> > Leaving the 'how' aside, *why* would anyone want
> > to do that?
>
> > I can't think of any application outside optics where
> > measurements are done directly in spectral domain?
> > One starts with a sequence of temporal (or spatial)
> > measurements and applies one or more DFTs (or
> > equivalent filtering operations) to do the conversion
> > to spectrum domain.
>
> > If we start out with a sequence of DFTs, spectrogram
> > style, and want to use a (temporal) window function
> > to smooth the spectrum, why not do the window
> > computations directly in time domain, once and for all?
>
> maybe because he doesn't want it to be so permanent.
>
>
>
> > The OP's post is a bit ambiguous on exactly what
> > he is doing. On first reading I interpreted the post differently,
> > but it might be interpreted as if he deals with legacy code.
> > If that's the case, and this code does not allow users to
> > specify window functions, that's reason enoght to abandon
> > the legacy code and reimplement.
>
> What he is doing sounded pretty simple to me.

Sure. It certainly 'sounds simple'. Therein lies the trap.

> The time domain windows he
> is encountering are just simple raised cosine functions. And that means
> he can do the windowing in the frequency domain by &#4294967295;convolving with a
> simple (i.e. short) kernel that is just derived directly from the
> coefficients of his time domain function.

I'm not sure that's the case. As I recall from Proakis & Manolakis
(I'm writing off memory here, so I might be wrong) the window
coefficients for the N-length window (N odd) are computed as

w[n] = 1/2 + 1/2 cos (pi*n / (N+1) )

The other details might not be correct, but do note the N+1
divisor in the argument to the cosine term. (I am sure somebody
will point us to authoritative references if this happens to be wrong)

Anyway, do note that you compute the window coefficients
from a cosine that has a period one sample longer than the
length of the window.

The net effect of this is that the N-point DFT of the window
function does not have 6 non-zero coefficients, as seems to
be the basis of the OP's argument, but N non-zero coefficients.
Which in turn means the computational load of doing the
computations in frequency domain is significantly higher
than in time domain.

In fact, one can use the familiar argument that 'convolution
in one domain is formally equivalent to, but comutationally more
expensive than, multiplication in the other domain', but with
frequency and time domains in the oposite roles than usual.

> &#4294967295; &#4294967295; &#4294967295; &#4294967295; I guess the issue is that with a sliding dft the large number of window
> functions that need to be implemented becomes computationally expensive.

Nope. The algorithm is straight-forward:

At initialization:
- Decide on the frame length N
- Allocate one N-length real-valued buffer
- Compute the window coefficients once
  and store in the buffer

After initialization:

- Read the pre-computed window coefficients from the
  buffer every time they are needed
- Multiply this coefficient with the sample before it is
  stored in the input buffer to the DFT

So after initialization you have exactly 1 memory access and
1 real-valued multiplication more than you would with no (explicit)
window function.

It doesn't get more efficient than that!

> And that convolving with a kernel of length 3 in the frequency domain is
> slightly faster than multiplying with a window length N in the time
> domain.

Well, even if the convolution kernel is of length 3 (I argued
above that the length is N), you need N*3 complex-valued
multiplications to do the work in frequency domain. Assuming
4 real mults per 1 complex mult (I don't know the exact
number) that's 12x more real-valued mults right there,
compared to if you do the same work in time domain.
With an N-pt convolution kernel you have at least 4N
times more work to do, if you choose to do things in
frequency domain.

Rune

On Apr 11, 9:57 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 11 Apr, 14:57, jim <"sjedgingN0Sp"@m@mwt,net> wrote:
> ...
> (I am sure somebody
> will point us to authoritative references if this happens to be wrong)
> ...
> Rune

An early general reference, already cited in this thread:

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


A more recent reference, discussing the OP's application:

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

Dale B. Dalrymple

Rune Allnor wrote:
> 
> On 11 Apr, 14:57, jim <"sjedgingN0Sp"@m@mwt,net> wrote:
> > Rune Allnor wrote:
> >
> > > On 10 Apr, 01:37, Rick Lyons <R.Lyons@_BOGUS_ieee.org> wrote:
> >
> > > >    Like you, for years I thought (assumed) there was no
> > > > way to perform time-domain windowing when using the
> > > > SDFT.  As it turns out (the following is NOT a drug
> > > > or alchohol-induced statement) there *IS* a way
> > > > to perform time-domain windowing when using the
> > > > SDFT.
> >
> > > Leaving the 'how' aside, *why* would anyone want
> > > to do that?
> >
> > > I can't think of any application outside optics where
> > > measurements are done directly in spectral domain?
> > > One starts with a sequence of temporal (or spatial)
> > > measurements and applies one or more DFTs (or
> > > equivalent filtering operations) to do the conversion
> > > to spectrum domain.
> >
> > > If we start out with a sequence of DFTs, spectrogram
> > > style, and want to use a (temporal) window function
> > > to smooth the spectrum, why not do the window
> > > computations directly in time domain, once and for all?
> >
> > maybe because he doesn't want it to be so permanent.
> >
> >
> >
> > > The OP's post is a bit ambiguous on exactly what
> > > he is doing. On first reading I interpreted the post differently,
> > > but it might be interpreted as if he deals with legacy code.
> > > If that's the case, and this code does not allow users to
> > > specify window functions, that's reason enoght to abandon
> > > the legacy code and reimplement.
> >
> > What he is doing sounded pretty simple to me.
> 
> Sure. It certainly 'sounds simple'. Therein lies the trap.
> 
> > The time domain windows he
> > is encountering are just simple raised cosine functions. And that means
> > he can do the windowing in the frequency domain by  convolving with a
> > simple (i.e. short) kernel that is just derived directly from the
> > coefficients of his time domain function.
> 
> I'm not sure that's the case. As I recall from Proakis & Manolakis
> (I'm writing off memory here, so I might be wrong) the window
> coefficients for the N-length window (N odd) are computed as
> 
> w[n] = 1/2 + 1/2 cos (pi*n / (N+1) )

> 
> The other details might not be correct, but do note the N+1
> divisor in the argument to the cosine term. (I am sure somebody
> will point us to authoritative references if this happens to be wrong)



For one thing it sounds  simpler to convolve with {-.25 .5 -.25] in the
frequency domain that figure out what the exactly formula is in the time
domain :)





> 
> Anyway, do note that you compute the window coefficients
> from a cosine that has a period one sample longer than the
> length of the window.

Well that depends on exactly what N and n represent. 

> 
> The net effect of this is that the N-point DFT of the window
> function does not have 6 non-zero coefficients, as seems to
> be the basis of the OP's argument, but N non-zero coefficients.


> Which in turn means the computational load of doing the
> computations in frequency domain is significantly higher
> than in time domain.

I think he he is looking for the windows that do transform to a simple
kernel. Yes he could easily find many that do not, but I don't think he
is interested in those.


> 
> In fact, one can use the familiar argument that 'convolution
> in one domain is formally equivalent to, but comutationally more
> expensive than, multiplication in the other domain', but with
> frequency and time domains in the oposite roles than usual.

Yes The argument is when the convolution involves a long impulse
response then multiplication in the other domain will be faster. It
sounds like he is looking for windows that transform to short impulse
responses. 


> 
> >         I guess the issue is that with a sliding dft the large number of window
> > functions that need to be implemented becomes computationally expensive.
> 
> Nope. The algorithm is straight-forward:
> 
> At initialization:
> - Decide on the frame length N
> - Allocate one N-length real-valued buffer
> - Compute the window coefficients once
>   and store in the buffer
> 
> After initialization:
> 
> - Read the pre-computed window coefficients from the
>   buffer every time they are needed
> - Multiply this coefficient with the sample before it is
>   stored in the input buffer to the DFT

And all of that doesn't take time?

> 
> So after initialization you have exactly 1 memory access and
> 1 real-valued multiplication more than you would with no (explicit)
> window function.

Convolution might be done with no multiplies if the coefficients in the
frequency domain are powers of 2. But I don't recall that he said it had
anything to do with computational efficiency that was just a guess that
I made. He may just be just investigating different frequency domain
impulse responses and there corresponding time domain windows. 


-jim

> 
> It doesn't get more efficient than that!
> 
> > And that convolving with a kernel of length 3 in the frequency domain is
> > slightly faster than multiplying with a window length N in the time
> > domain.
> 
> Well, even if the convolution kernel is of length 3 (I argued
> above that the length is N), you need N*3 complex-valued
> multiplications to do the work in frequency domain. Assuming
> 4 real mults per 1 complex mult (I don't know the exact
> number) that's 12x more real-valued mults right there,
> compared to if you do the same work in time domain.
> With an N-pt convolution kernel you have at least 4N
> times more work to do, if you choose to do things in
> frequency domain.
> 
> Rune

On 11 Apr, 21:07, dbd <d...@ieee.org> wrote:
> On Apr 11, 9:57 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 11 Apr, 14:57, jim <"sjedgingN0Sp"@m@mwt,net> wrote:
> > ...
> > (I am sure somebody
> > will point us to authoritative references if this happens to be wrong)
> > ...
> > Rune
>
> An early general reference, already cited in this thread:
>
> 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.

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.

Coming to think of it, all the descriptions I have seen of
window functions had to do with FIR filter design. 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

Rune Allnor wrote:
> 
> On 11 Apr, 21:07, dbd <d...@ieee.org> wrote:
> > On Apr 11, 9:57 am, Rune Allnor <all...@tele.ntnu.no> wrote:
> >
> > > On 11 Apr, 14:57, jim <"sjedgingN0Sp"@m@mwt,net> wrote:
> > > ...
> > > (I am sure somebody
> > > will point us to authoritative references if this happens to be wrong)
> > > ...
> > > Rune
> >
> > An early general reference, already cited in this thread:
> >
> > 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.
> 


It think you have that turned around the impulse response for
convolution ends up being symmetric in any case. The window is what is
known as "DFT symmetic", which is not quite symmetric, but is a of a
form that produces all real DFT. The DFT of the window is symmetric in
any case because the window is real.

-jim




> 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.
> 
> Coming to think of it, all the descriptions I have seen of
> window functions had to do with FIR filter design. 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