Forums

Frequency domain filtering (rectangular window question)

Started by tjuii September 21, 2005
I am new to DSP and have a question regarding filtering in the
frequency domain.  I understand the problem using a rectangular window
for
filtering in the time domain, however, in the frequency domain what are
the
problems that one must be aware of if using a rectangular frequency
domain
window (i.e. a frequency response of 0 outside the pass band and 1 inside
the pass band) and then multiplying that by the FFT of the signal to be
filtered?  It seems to me that a rectangular freq. window/response has
infinitely fast roll-off and a perfectly flat pass-band.  These sound
like
good things to me ... am I wrong?  What am I missing?

TJ


		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com
It is important to remember the relationship between the frequency
domain and the time domain.  An instaneous change in the frequency
domain will take infinite bandwith in the time domain and this isn't
practically realizable.

What ends up happening is that if you use a rectangular window you get
effects such as a large number of side lobes in your frequency
response, which reduces the effectiveness of the filter.  A window
function is used to avoid these instaneous time domain transitions,
resulting in an overall better filter response.

in article OeGdnffDyc7VM6zeRVn-gw@giganews.com, tjuii at tju@lanl.gov wrote
on 09/21/2005 15:02:

> I am new to DSP and have a question regarding filtering in the > frequency domain. I understand the problem using a rectangular window > for > filtering in the time domain, however, in the frequency domain what are > the > problems that one must be aware of if using a rectangular frequency > domain > window (i.e. a frequency response of 0 outside the pass band and 1 inside > the pass band) and then multiplying that by the FFT of the signal to be > filtered? It seems to me that a rectangular freq. window/response has > infinitely fast roll-off and a perfectly flat pass-band. These sound > like > good things to me ... am I wrong? What am I missing? >
are you talking about using the FFT to do "fast convolution" of a real-time stream of data (or a very large file)? if that is the case, the use of the rectangular window is what you want, but you have to learn and understand the "overlap-add" or "overlap-save" methods. or are you doing something else?
> This message was sent using the Comp.DSP web interface on > www.DSPRelated.com
this signature is gonna start looking like "imsumbuddy@aol.com". you guys should at least use Google. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
When I mention a rectangular frequency window, I mean rectangular IN the
freq. domain, NOT the time domain.  Thus what I am doing is taking a
signal (32768 or 65536 samples long, typically), doing an FFT of it.  Then
I create a filter function in freq. domain that contains only 2 values, 0
for the frequencies that I don't want, and 1 for the frequencies that I do
want, so that the "filter function" looks like this:

0 0 0 0 1 1 1 0 0 0 0 0 : 0 0 0 0 0 1 1 1 0 0 0 0

where each bin (i.e. 0 or 1) corresponds to a frequency.  the ":"
character marks the mirror point (Nyquist freq. ... and it's not a bin)
where I need to reflect my filter around in order to account for aliasing.
 This "filter function" is the same length (and on the same scale) as the
FFT of my signal.  Then I just multiply them together ... thus extracting
only the frequencies that I want from my signal.  An inverse FFT then
brings me back to the time domain and gives me my filtered signal. 

I know none of this is new or exciting, I'm just trying to clearly explain
what I'm doing.  I'm not sure what overlap add or overlap save are, but I'm
assuming they must be ways of accounting for aliasing, which I don't need,
since I always deal in powers of 2 (typically > 2^15) and just reflect my
"filter function" about the Nyquist freq.  Am I right in that thinking, or
am I missing something?

The reason I ask about this is that I was using this method and someone
told me that bad things can happen to filtered signals with this method. 
They couldn't explain, and I couldn't think of why that would happen or
what were meant by  "bad things.", so I came here to post the question.  I
will say that I have been investigating the frequency response of FIR
filters with different time domain windows, and noticed that the more
points/taps I used in my filter the more the frequency response looked
like what I call a rectangular frequency window, i.e. the 0's and 1's
thing that I mentioned above.  That got me thinking that maybe it isn't so
bad to just define something with sharp edges (i.e. infinite rolloff and
flat passband) in the frequency domain.

I'm new to all of this (though I've read a lot recently) and am just
wondering if there is something that I am missing here?

Thanks
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com
tjuii wrote:
> When I mention a rectangular frequency window, I mean rectangular IN the > freq. domain, NOT the time domain. Thus what I am doing is taking a > signal (32768 or 65536 samples long, typically), doing an FFT of it. Then > I create a filter function in freq. domain that contains only 2 values, 0 > for the frequencies that I don't want, and 1 for the frequencies that I do > want, so that the "filter function" looks like this: > > 0 0 0 0 1 1 1 0 0 0 0 0 : 0 0 0 0 0 1 1 1 0 0 0 0 > > where each bin (i.e. 0 or 1) corresponds to a frequency. the ":" > character marks the mirror point (Nyquist freq. ... and it's not a bin) > where I need to reflect my filter around in order to account for aliasing. > This "filter function" is the same length (and on the same scale) as the > FFT of my signal. Then I just multiply them together ... thus extracting > only the frequencies that I want from my signal. An inverse FFT then > brings me back to the time domain and gives me my filtered signal.
...
> The reason I ask about this is that I was using this method and someone > told me that bad things can happen to filtered signals with this method. > They couldn't explain, and I couldn't think of why that would happen or > what were meant by "bad things." ...
One experiment to try, that might give you some insight on what happens when using a pure rectangular window in the frequency domain, is to see what happens to any frequencies which are halfway between your fft bins, if you accept that those frequencies are possible, when fed through such a filter. Don't just look at the halfway frequencies which are right next to your 0-1 window edge transition, but also those which are a couple bins away. Is your filter as flat and narrow as you expected? IMHO. YMMV. -- Ron rhn A.T nicholson d.O.t C-o-M
robert bristow-johnson wrote:
>>This message was sent using the Comp.DSP web interface on >>www.DSPRelated.com > > > this signature is gonna start looking like "imsumbuddy@aol.com". you guys > should at least use Google. >
ME TOO!!! -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (603) 226-0404 x536 When you know how things work, the world is one big sandbox. - Avins
Try taking the inverse FFT of your rectangular window.  You should be
able to do this easilly with a program such as Mathcad or Matlab.  You
will see that you get a SINC() function, ie sin(x) / x.  You are
correct that the more samples you take (more filter taps, a longer FFT,
etc) the more the response will represent an ideal brick wall filter.
If you were able to use an infinitely long data stream you would  get
an ideal response.

While it is certainly acceptible to use a rectangular window, generally
speaking, other window functions will give you a superior frequency
response.

I would also recommend reading "Understanding Digital Signal
Processing" by Richard Lyons.  The first couple of chapters deal with
your question very thoroughly.

in article MdOdneHCg9lWhq7eRVn-rQ@giganews.com, tjuii at tju@lanl.gov wrote
on 09/22/2005 17:02:

> I know none of this is new or exciting, I'm just trying to clearly explain > what I'm doing. I'm not sure what overlap add or overlap save are, but I'm > assuming they must be ways of accounting for aliasing, which I don't need, > since I always deal in powers of 2 (typically > 2^15) and just reflect my > "filter function" about the Nyquist freq. Am I right in that thinking,
maybe not.
> or am I missing something?
probably. you say you want to do "Frequency domain filtering". can you tell us what signal is getting filtered? is it much longer than an FFT buffer or a real-time stream? if "yes", you are doing filtering that has an end result that is the same as regular old IIR or FIR filtering. if it is the latter (FIR), you can do that in the frequency domain, using overlap-add or overlap-save, BUT THEN your frequency domain transfer function MUST be the DFT (or FFT) of a *finite* impulse response (that is significantly shorter than the FFT buffer size). you cannot have any arbitrary frequency response and do "frequency domain filtering" of a continuous stream of data or a very long file. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
robert bristow-johnson wrote:
> in article MdOdneHCg9lWhq7eRVn-rQ@giganews.com, tjuii at tju@lanl.gov wrote > on 09/22/2005 17:02: > > >>I know none of this is new or exciting, I'm just trying to clearly explain >>what I'm doing. I'm not sure what overlap add or overlap save are, but I'm >>assuming they must be ways of accounting for aliasing, which I don't need, >>since I always deal in powers of 2 (typically > 2^15) and just reflect my >>"filter function" about the Nyquist freq. Am I right in that thinking, > > > maybe not. > > >>or am I missing something? > > > probably. > > you say you want to do "Frequency domain filtering". can you tell us what > signal is getting filtered? is it much longer than an FFT buffer or a > real-time stream? if "yes", you are doing filtering that has an end result > that is the same as regular old IIR or FIR filtering. if it is the latter > (FIR), you can do that in the frequency domain, using overlap-add or > overlap-save, BUT THEN your frequency domain transfer function MUST be the > DFT (or FFT) of a *finite* impulse response (that is significantly shorter > than the FFT buffer size). > > you cannot have any arbitrary frequency response and do "frequency domain > filtering" of a continuous stream of data or a very long file.
Hell, man, you can't even have an arbitrary frequency response even if the signal fits in the buffer. All one can do is pick the response of bin centers. Between those frequencies, the response can go wild. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
in article 4vednZjaL6fqy6neRVn-iA@rcn.net, Jerry Avins at jya@ieee.org wrote
on 09/23/2005 15:24:

> robert bristow-johnson wrote: >> in article MdOdneHCg9lWhq7eRVn-rQ@giganews.com, tjuii at tju@lanl.gov wrote >> on 09/22/2005 17:02: >> >> >>> I know none of this is new or exciting, I'm just trying to clearly explain >>> what I'm doing. I'm not sure what overlap add or overlap save are, but I'm >>> assuming they must be ways of accounting for aliasing, which I don't need, >>> since I always deal in powers of 2 (typically > 2^15) and just reflect my >>> "filter function" about the Nyquist freq. Am I right in that thinking, >> >> >> maybe not. >> >> >>> or am I missing something? >> >> >> probably. >> >> you say you want to do "Frequency domain filtering". can you tell us what >> signal is getting filtered? is it much longer than an FFT buffer or a >> real-time stream? if "yes", you are doing filtering that has an end result >> that is the same as regular old IIR or FIR filtering. if it is the latter >> (FIR), you can do that in the frequency domain, using overlap-add or >> overlap-save, BUT THEN your frequency domain transfer function MUST be the >> DFT (or FFT) of a *finite* impulse response (that is significantly shorter >> than the FFT buffer size). >> >> you cannot have any arbitrary frequency response and do "frequency domain >> filtering" of a continuous stream of data or a very long file. > > Hell, man, you can't even have an arbitrary frequency response even if > the signal fits in the buffer. All one can do is pick the response of > bin centers. Between those frequencies, the response can go wild.
it depends on how short the FIR is. the shorter, the less wild the frequency response can be around the bins or in between. the frequency response of the FIR has infinite resolution (i'm not saying that *we* can define it arbitrarily at any frequency, only that the frequency response is defined for every frequency < Nyquist), but when we do circular convolution, that FIR *plus* padding gets periodically extended and the frequency response for that is defined only at the bin frequencies. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."