CASTalk.com

Michel Rouzic wrote:

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

Note that windowing in time-domain corresponds to convolution in
frequency domain. So to synthesize a windowed sinc directly in
frequency domain, you have to convolve the frequency domain rectangle
function with the FT of the window.

The fast convolution approach requires that you IDFT the rectangle,
multiply with the window and DFT the resulting windowed sinc, which is
what you are trying to avoid. It is generally the faster method than
direct frequency domain convolution.

However, a certain class of windows have very small convolution
kernels, so frequency domain convolution can be faster than time-domain
windowing. This class of windows is of the form

w[n] = sum_k a_k cos(2 pi k n / (N-1)), for 0 <= k < K,

where K denotes the order of the trigonometric polynomial, and N the
number of window points. The DFT of such windows has only 2K+1 non-zero
coefficients. You will be interested to read Nuttall's classic paper
[1]. Examples of such windows are von Hann (only three coefficients in
frequency domain!), Hamming, Nuttall, Blackman-Harris, etc.

My second problem is to calculate the value of the pre-rolloff non-0
samples in the magnitude, so that if we IFFT'ed it and calculated the
sum of all samples in the frequency domain it would match to 1.

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

abariska@student.ethz.ch wrote:
Michel Rouzic wrote:

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

Note that windowing in time-domain corresponds to convolution in
frequency domain. So to synthesize a windowed sinc directly in
frequency domain, you have to convolve the frequency domain rectangle
function with the FT of the window.

The fast convolution approach requires that you IDFT the rectangle,
multiply with the window and DFT the resulting windowed sinc, which is
what you are trying to avoid. It is generally the faster method than
direct frequency domain convolution.

Yeah, so you see, that's why i'm trying to directly calculate the
frequency domain samples, without any convolution or multiplication. I
thought that maybe there was a way to calculate the proper rolloff
sample values.

However, a certain class of windows have very small convolution
kernels, so frequency domain convolution can be faster than time-domain
windowing. This class of windows is of the form

w[n] = sum_k a_k cos(2 pi k n / (N-1)), for 0 <= k < K,

where K denotes the order of the trigonometric polynomial, and N the
number of window points. The DFT of such windows has only 2K+1 non-zero
coefficients. You will be interested to read Nuttall's classic paper
[1]. Examples of such windows are von Hann (only three coefficients in
frequency domain!), Hamming, Nuttall, Blackman-Harris, etc.

wow now you got me kind of lost with that one. I can't tell whats a
trigonometric polynomial...

Michel Rouzic wrote:
abariska@student.ethz.ch wrote:
Michel Rouzic wrote:

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

Note that windowing in time-domain corresponds to convolution in
frequency domain. So to synthesize a windowed sinc directly in
frequency domain, you have to convolve the frequency domain rectangle
function with the FT of the window.

The fast convolution approach requires that you IDFT the rectangle,
multiply with the window and DFT the resulting windowed sinc, which is
what you are trying to avoid. It is generally the faster method than
direct frequency domain convolution.

Yeah, so you see, that's why i'm trying to directly calculate the
frequency domain samples, without any convolution or multiplication. I
thought that maybe there was a way to calculate the proper rolloff
sample values.

However, a certain class of windows have very small convolution
kernels, so frequency domain convolution can be faster than time-domain
windowing. This class of windows is of the form

w[n] = sum_k a_k cos(2 pi k n / (N-1)), for 0 <= k < K,

where K denotes the order of the trigonometric polynomial, and N the
number of window points. The DFT of such windows has only 2K+1 non-zero
coefficients. You will be interested to read Nuttall's classic paper
[1]. Examples of such windows are von Hann (only three coefficients in
frequency domain!), Hamming, Nuttall, Blackman-Harris, etc.

wow now you got me kind of lost with that one. I can't tell whats a
trigonometric polynomial...

It doesn't really matter. Here's an example: The normalized zero-phase
von Hann kernel is equal to

h_zp_H =[ 1/2 1/4 0 ... 0 1/4 ]

where the ellipses represent 0s to fill the vector to the length of the
FFT (call it N). The zero-phase rectangular window is

r_zp = [ 1 ... 1 1 0 0 ... 0 0 1 1 ... 1 ].

also of length N. The number of 1s and 0s depends on N and the cutoff
frequency of the rectangle. If you circularly convolve these two
vectors in frequency domain you get

r_zp * h_zp_H = [ 1 ... 1 1 3/4 1/4 0 0 ... 0 1/4 3/4 1 1 ... 1 ].

So there you have the transition samples. In time domain, this is
equivalent to truncating a sinc function with a von Hann window of
length N.

To get the linear-phase version, just invert the sign of every second
coefficient. If you want another window than von Hann, take the
appropriate kernel. It really is described very well in that paper [1]
I referenced for you.

abariska@student.ethz.ch wrote:
Michel Rouzic wrote:
abariska@student.ethz.ch wrote:
Michel Rouzic wrote:

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

Note that windowing in time-domain corresponds to convolution in
frequency domain. So to synthesize a windowed sinc directly in
frequency domain, you have to convolve the frequency domain rectangle
function with the FT of the window.

The fast convolution approach requires that you IDFT the rectangle,
multiply with the window and DFT the resulting windowed sinc, which is
what you are trying to avoid. It is generally the faster method than
direct frequency domain convolution.

Yeah, so you see, that's why i'm trying to directly calculate the
frequency domain samples, without any convolution or multiplication. I
thought that maybe there was a way to calculate the proper rolloff
sample values.

However, a certain class of windows have very small convolution
kernels, so frequency domain convolution can be faster than time-domain
windowing. This class of windows is of the form

w[n] = sum_k a_k cos(2 pi k n / (N-1)), for 0 <= k < K,

where K denotes the order of the trigonometric polynomial, and N the
number of window points. The DFT of such windows has only 2K+1 non-zero
coefficients. You will be interested to read Nuttall's classic paper
[1]. Examples of such windows are von Hann (only three coefficients in
frequency domain!), Hamming, Nuttall, Blackman-Harris, etc.

wow now you got me kind of lost with that one. I can't tell whats a
trigonometric polynomial...

It doesn't really matter. Here's an example: The normalized zero-phase
von Hann kernel is equal to

h_zp_H =[ 1/2 1/4 0 ... 0 1/4 ]

where the ellipses represent 0s to fill the vector to the length of the
FFT (call it N). The zero-phase rectangular window is

r_zp = [ 1 ... 1 1 0 0 ... 0 0 1 1 ... 1 ].

also of length N. The number of 1s and 0s depends on N and the cutoff
frequency of the rectangle. If you circularly convolve these two
vectors in frequency domain you get

r_zp * h_zp_H = [ 1 ... 1 1 3/4 1/4 0 0 ... 0 1/4 3/4 1 1 ... 1 ].

So there you have the transition samples. In time domain, this is
equivalent to truncating a sinc function with a von Hann window of
length N.

To get the linear-phase version, just invert the sign of every second
coefficient. If you want another window than von Hann, take the
appropriate kernel. It really is described very well in that paper [1]
I referenced for you.

alright, well as you probably understood, i want to make it really as
optimized as possible, so i'll rather precalculate the rolloff samples
instead of performing a frequency-domain convolution with a window
function.

maybe i'll do it the simple way and take the 5 values I already talked
about, but i'd like firstly to look for better ways to do it, like for
example, have less than 5 rolloff samples, do you have an idea of the
minimum number of samples i can have for the rolloff?

Having as few as
possible would mean i would need smaller kernels to achieve the same
filtering, so that's a pretty much important question. i wish I had a
way to find out by myself tho, but i can't think fo any.

Michel Rouzic wrote:
abariska@student.ethz.ch wrote:
Michel Rouzic wrote:
abariska@student.ethz.ch wrote:
Michel Rouzic wrote:

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

Note that windowing in time-domain corresponds to convolution in
frequency domain. So to synthesize a windowed sinc directly in
frequency domain, you have to convolve the frequency domain rectangle
function with the FT of the window.

The fast convolution approach requires that you IDFT the rectangle,
multiply with the window and DFT the resulting windowed sinc, which is
what you are trying to avoid. It is generally the faster method than
direct frequency domain convolution.

Yeah, so you see, that's why i'm trying to directly calculate the
frequency domain samples, without any convolution or multiplication. I
thought that maybe there was a way to calculate the proper rolloff
sample values.

However, a certain class of windows have very small convolution
kernels, so frequency domain convolution can be faster than time-domain
windowing. This class of windows is of the form

w[n] = sum_k a_k cos(2 pi k n / (N-1)), for 0 <= k < K,

where K denotes the order of the trigonometric polynomial, and N the
number of window points. The DFT of such windows has only 2K+1 non-zero
coefficients. You will be interested to read Nuttall's classic paper
[1]. Examples of such windows are von Hann (only three coefficients in
frequency domain!), Hamming, Nuttall, Blackman-Harris, etc.

wow now you got me kind of lost with that one. I can't tell whats a
trigonometric polynomial...

It doesn't really matter. Here's an example: The normalized zero-phase
von Hann kernel is equal to

h_zp_H =[ 1/2 1/4 0 ... 0 1/4 ]

where the ellipses represent 0s to fill the vector to the length of the
FFT (call it N). The zero-phase rectangular window is

r_zp = [ 1 ... 1 1 0 0 ... 0 0 1 1 ... 1 ].

also of length N. The number of 1s and 0s depends on N and the cutoff
frequency of the rectangle. If you circularly convolve these two
vectors in frequency domain you get

r_zp * h_zp_H = [ 1 ... 1 1 3/4 1/4 0 0 ... 0 1/4 3/4 1 1 ... 1 ].

So there you have the transition samples. In time domain, this is
equivalent to truncating a sinc function with a von Hann window of
length N.

To get the linear-phase version, just invert the sign of every second
coefficient. If you want another window than von Hann, take the
appropriate kernel. It really is described very well in that paper [1]
I referenced for you.

alright, well as you probably understood, i want to make it really as
optimized as possible, so i'll rather precalculate the rolloff samples
instead of performing a frequency-domain convolution with a window
function.

If you only work with FIRs that have an on/off frequency response
(rectangular bandpasses where the DFT coefficients consists of 1s and
0s), then you can replace each [ ... 1 1 0 0 ... ] with [ ... 1 3/4
1/4 0 ...] and similarly for [ ... 0 0 1 1 ... ]. This again
corresponds to windowing with a von Hann window. Only if you have an
arbitrary frequency response you need to circularly convolve with the
von Hann kernel.


maybe i'll do it the simple way and take the 5 values I already talked
about, but i'd like firstly to look for better ways to do it, like for
example, have less than 5 rolloff samples, do you have an idea of the
minimum number of samples i can have for the rolloff?

The von Hann window has three samples. You need an odd number of
samples to get a real time-domain window, so three samples seems to be
the smallest non-trivial window.

Having as few as
possible would mean i would need smaller kernels to achieve the same
filtering, so that's a pretty much important question. i wish I had a
way to find out by myself tho, but i can't think fo any.

Michel, for the last time: read that paper! That is the way to find it
out by yourself. You can get it at http://ieeexplore.ieee.org/.

Michel Rouzic wrote:
abariska@student.ethz.ch wrote:
Michel Rouzic wrote:
abariska@student.ethz.ch wrote:
Michel Rouzic wrote:

The program I'm working on right now relies heavily on convoluting a
signal with many different FIR kernels. In order to optimize it, I want
to generate the windowed-sinc function directly in the frequency
domain, so it could get much more efficient than generating a
windowed-sinc function in the time domain and then performing a FFT on
it.

Note that windowing in time-domain corresponds to convolution in
frequency domain. So to synthesize a windowed sinc directly in
frequency domain, you have to convolve the frequency domain rectangle
function with the FT of the window.

The fast convolution approach requires that you IDFT the rectangle,
multiply with the window and DFT the resulting windowed sinc, which is
what you are trying to avoid. It is generally the faster method than
direct frequency domain convolution.

Yeah, so you see, that's why i'm trying to directly calculate the
frequency domain samples, without any convolution or multiplication. I
thought that maybe there was a way to calculate the proper rolloff
sample values.

However, a certain class of windows have very small convolution
kernels, so frequency domain convolution can be faster than time-domain
windowing. This class of windows is of the form

w[n] = sum_k a_k cos(2 pi k n / (N-1)), for 0 <= k < K,

where K denotes the order of the trigonometric polynomial, and N the
number of window points. The DFT of such windows has only 2K+1 non-zero
coefficients. You will be interested to read Nuttall's classic paper
[1]. Examples of such windows are von Hann (only three coefficients in
frequency domain!), Hamming, Nuttall, Blackman-Harris, etc.

wow now you got me kind of lost with that one. I can't tell whats a
trigonometric polynomial...

It doesn't really matter. Here's an example: The normalized zero-phase
von Hann kernel is equal to

h_zp_H =[ 1/2 1/4 0 ... 0 1/4 ]

where the ellipses represent 0s to fill the vector to the length of the
FFT (call it N). The zero-phase rectangular window is

r_zp = [ 1 ... 1 1 0 0 ... 0 0 1 1 ... 1 ].

also of length N. The number of 1s and 0s depends on N and the cutoff
frequency of the rectangle. If you circularly convolve these two
vectors in frequency domain you get

r_zp * h_zp_H = [ 1 ... 1 1 3/4 1/4 0 0 ... 0 1/4 3/4 1 1 ... 1 ].

So there you have the transition samples. In time domain, this is
equivalent to truncating a sinc function with a von Hann window of
length N.

To get the linear-phase version, just invert the sign of every second
coefficient. If you want another window than von Hann, take the
appropriate kernel. It really is described very well in that paper [1]
I referenced for you.

alright, well as you probably understood, i want to make it really as
optimized as possible, so i'll rather precalculate the rolloff samples
instead of performing a frequency-domain convolution with a window
function.

If you only work with FIRs that have an on/off frequency response
(rectangular bandpasses where the DFT coefficients consists of 1s and
0s), then you can replace each [ ... 1 1 0 0 ... ] with [ ... 1 3/4
1/4 0 ...] and similarly for [ ... 0 0 1 1 ... ]. This again
corresponds to windowing with a von Hann window. Only if you have an
arbitrary frequency response you need to circularly convolve with the
von Hann kernel.


maybe i'll do it the simple way and take the 5 values I already talked
about, but i'd like firstly to look for better ways to do it, like for
example, have less than 5 rolloff samples, do you have an idea of the
minimum number of samples i can have for the rolloff?

The von Hann window has three samples. You need an odd number of
samples to get a real time-domain window, so three samples seems to be
the smallest non-trivial window.

Having as few as
possible would mean i would need smaller kernels to achieve the same
filtering, so that's a pretty much important question. i wish I had a
way to find out by myself tho, but i can't think fo any.

Michel, for the last time: read that paper! That is the way to find it
out by yourself. You can get it at http://ieeexplore.ieee.org/.