| Author |
Message |
Michel Rouzic
Guest
|
 Posted:
Wed Dec 21, 2005 5:16 pm Post subject:
Generating a windowed-sinc function directly in the frequenc |
|
|
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.
My first problem is having a good rolloff. In the polar form, I noticed
that the magnitude goes from some value (here we'll pretend it's 1.0,
although it never is 1.0) to 0 through roughly 5 samples, which values
are near 0.981, 0.846, 0.500, 0.135 and 0.019. I'd like to know how I
can calculate the proper values so the rolloff that would be more
correct than these values mesured from the magnitude of some
windowed-sinc function. Personally the only thing I knew that could get
close to that was the half of a blackman function and it doesn't match
at all.
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. I found
a relation between the length of the kernel and that value, but
couldn't figure out how to calculate it.
All my interrogations are about the magnitude part of the FFT, because
it seems like every single sample of the phase part are -1.0 (correct
me if i'm wrong, who knows, maybe my rectangular-form to polar-form
function is broken) |
|
| Back to top |
|
 |
Michel Rouzic
Guest
|
| Posted:
Wed Dec 21, 2005 5:16 pm Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
abariska@student.ethz.ch wrote:
| Quote: | 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.
| Quote: | 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... |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Wed Dec 21, 2005 5:16 pm Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
Michel Rouzic wrote:
| Quote: | 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.
|
I meant in the time domain, not the frequency domain |
|
| Back to top |
|
|
Guest
|
| Posted:
Wed Dec 21, 2005 5:16 pm Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
Michel Rouzic wrote:
| Quote: | 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.
Regards,
Andor
[1] A H Nuttall: "Some windows with very good sidelobe behaviour"
IEEE Trans ASSP, Vol 29, No 1, Feb 1981 |
|
| Back to top |
|
|
Guest
|
| Posted:
Thu Dec 22, 2005 9:16 am Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
Michel Rouzic wrote:
| Quote: | 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.
Regards,
Andor |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Fri Dec 23, 2005 1:16 am Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
abariska@student.ethz.ch wrote:
| Quote: | 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. |
|
| Back to top |
|
|
Guest
|
| Posted:
Fri Dec 23, 2005 5:16 pm Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
Michel Rouzic wrote:
| Quote: | 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.
| Quote: |
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.
| Quote: | 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/.
Regards,
Andor |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Fri Dec 23, 2005 5:16 pm Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
abariska@student.ethz.ch wrote:
| Quote: | 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/.
|
k thanks, i tried looking for it but i couldn't find it on google |
|
| Back to top |
|
|
Michel Rouzic
Guest
|
| Posted:
Tue Dec 27, 2005 1:16 am Post subject:
Re: Generating a windowed-sinc function directly in the freq |
|
|
abariska@student.ethz.ch wrote:
| Quote: | 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/.
|
I figured out that we forgot something quite important. What we talked
about so far is making a FIR, but it's not ready for the convolution
yet, the reason for that is that if we turn that FIR kernel back to the
time domain, we'll see it takes the whole room, as it should be
zeropadded.
Any ideas on how to make it zero-padded? |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in