Why not just filter directly in the frequency domain using the fft and ifft?

I am relatively new to DSP and I have what seems like a simple
question, but I have not been able to find in answer to it by reading
DSP books.

If the goal is to design a frequency-selective filter, then is there
any reason not to simply take the FFT of a signal (or a window
thereof), apply our filter by directly multiplying the filter amplitude
response with the FFT of our signal, and then take the IFFT (inverse
FFT) to get back the filtered signal?  Is there any disadvantage to
doing this as opposed to using an FIR or IIR filter?

For the mathematically inclined ...
Suppose we have a signal x(k) and it's DFT (calculated via FFT) is
X(f).
We also have a desired filter specification represented by it's
amplitude response, A(f).  Then, a filtered version of this signal,
y(k) can be found:
y(k) = IFFT { X(f) A(f) }

I tried doing this using MATLAB and some noisy data for the specific
case of a highpass filter with a cutoff frequency very close to DC, and
it worked great.  I simply used an ideal highpass filter
characteristic.  Is there something I'm missing?  If it is this simple,
then why do DSP books focus so much on FIR and IIR filters?  I figure
I'm missing something important and probably "obvious".  Please
enlighten me ... politely.

On a related note .., I was trying to design an FIR filter (using a
windowed truncated impulse response) to filter this same data.  The
problem I was having is that there was an initial transient of
relatively long duration and of an amplitude that was several orders of
magnitude larger than the "good" filtered data.  Is there a way to
avoid this - i.e. is there a way to eliminate or greatly minimize this
transient?  I tried using an IIR filter and the problem was even worse.
For this particular application, the data is logged and then stored on
a computer, so the processing doesn't need to be real-time, any type of
filter (non-causal, etc.) should be fine.  Any advice/insight would be
appreciated.

todd.leonhardt@gmail.com wrote:

> I am relatively new to DSP and I have what seems like a simple
> question, but I have not been able to find in answer to it by reading
> DSP books.
> 
> If the goal is to design a frequency-selective filter, then is there
> any reason not to simply take the FFT of a signal (or a window
> thereof), apply our filter by directly multiplying the filter amplitude
> response with the FFT of our signal, and then take the IFFT (inverse
> FFT) to get back the filtered signal?  Is there any disadvantage to
> doing this as opposed to using an FIR or IIR filter?

Provided that you don't attempt to filter too vigorously, it can work
just fine. It's relatively easy when you can FFT the entire signal at
once, but not many circumstances allow that. If you need to operate on
the signal piecemeal, then special procedures are needed to stitch the
filtered signal back together. Look up "overlap-save" and overlap-add".
> 
> For the mathematically inclined ...
> Suppose we have a signal x(k) and it's DFT (calculated via FFT) is
> X(f).
> We also have a desired filter specification represented by it's
> amplitude response, A(f).  Then, a filtered version of this signal,
> y(k) can be found:
> y(k) = IFFT { X(f) A(f) }
> 
> I tried doing this using MATLAB and some noisy data for the specific
> case of a highpass filter with a cutoff frequency very close to DC, and
> it worked great.  I simply used an ideal highpass filter
> characteristic.  Is there something I'm missing?  If it is this simple,
> then why do DSP books focus so much on FIR and IIR filters?  I figure
> I'm missing something important and probably "obvious".  Please
> enlighten me ... politely.
> 
> On a related note .., I was trying to design an FIR filter (using a
> windowed truncated impulse response) to filter this same data.  The
> problem I was having is that there was an initial transient of
> relatively long duration and of an amplitude that was several orders of
> magnitude larger than the "good" filtered data.  Is there a way to
> avoid this - i.e. is there a way to eliminate or greatly minimize this
> transient?  I tried using an IIR filter and the problem was even worse.
> For this particular application, the data is logged and then stored on
> a computer, so the processing doesn't need to be real-time, any type of
> filter (non-causal, etc.) should be fine.  Any advice/insight would be
> appreciated.

Unless an FIR filter is filled with data, the output doesn't follow what
the whole filter was designed to do. The not-filled beginning and end
are transients.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"Jerry Avins" <jya@ieee.org> wrote in message 
news:317h9pF32kcphU1@individual.net...
> todd.leonhardt@gmail.com wrote:
>
>> I am relatively new to DSP and I have what seems like a simple
>> question, but I have not been able to find in answer to it by reading
>> DSP books.
>>
>> If the goal is to design a frequency-selective filter, then is there
>> any reason not to simply take the FFT of a signal (or a window
>> thereof), apply our filter by directly multiplying the filter amplitude
>> response with the FFT of our signal, and then take the IFFT (inverse
>> FFT) to get back the filtered signal?  Is there any disadvantage to
>> doing this as opposed to using an FIR or IIR filter?
>
> Provided that you don't attempt to filter too vigorously, it can work
> just fine. It's relatively easy when you can FFT the entire signal at
> once, but not many circumstances allow that. If you need to operate on
> the signal piecemeal, then special procedures are needed to stitch the
> filtered signal back together. Look up "overlap-save" and overlap-add".
>>
>> For the mathematically inclined ...
>> Suppose we have a signal x(k) and it's DFT (calculated via FFT) is
>> X(f).
>> We also have a desired filter specification represented by it's
>> amplitude response, A(f).  Then, a filtered version of this signal,
>> y(k) can be found:
>> y(k) = IFFT { X(f) A(f) }
>>
>> I tried doing this using MATLAB and some noisy data for the specific
>> case of a highpass filter with a cutoff frequency very close to DC, and
>> it worked great.  I simply used an ideal highpass filter
>> characteristic.  Is there something I'm missing?  If it is this simple,
>> then why do DSP books focus so much on FIR and IIR filters?  I figure
>> I'm missing something important and probably "obvious".  Please
>> enlighten me ... politely.
>>
>> On a related note .., I was trying to design an FIR filter (using a
>> windowed truncated impulse response) to filter this same data.  The
>> problem I was having is that there was an initial transient of
>> relatively long duration and of an amplitude that was several orders of
>> magnitude larger than the "good" filtered data.  Is there a way to
>> avoid this - i.e. is there a way to eliminate or greatly minimize this
>> transient?  I tried using an IIR filter and the problem was even worse.
>> For this particular application, the data is logged and then stored on
>> a computer, so the processing doesn't need to be real-time, any type of
>> filter (non-causal, etc.) should be fine.  Any advice/insight would be
>> appreciated.
>
> Unless an FIR filter is filled with data, the output doesn't follow what
> the whole filter was designed to do. The not-filled beginning and end
> are transients.
>
> Jerry

Subject to Jerry's cautions, multiplication in frequency (with an 
appropriate filter response - thus Jerry's "Provided that you don't attempt 
to filter too vigorously") can be more computationally efficient by quite a 
large margin.

Fred 

"todd.leonhardt@gmail.com" wrote:
> 
> I am relatively new to DSP and I have what seems like a simple
> question, but I have not been able to find in answer to it by reading
> DSP books.
> 
> If the goal is to design a frequency-selective filter, then is there
> any reason not to simply take the FFT of a signal (or a window
> thereof), apply our filter by directly multiplying the filter amplitude
> response with the FFT of our signal, and then take the IFFT (inverse
> FFT) to get back the filtered signal?  Is there any disadvantage to
> doing this as opposed to using an FIR or IIR filter?

Yes, filtering in the frequency domain is far more computationally 
expensive than doing it in the time domain for most sensible filters. 
By sensible filters, i just about any IIR filter or any FIR filter
with less than 1000 coefficients. For really huge FIR filters then
frequency domain methods may be preferable.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"Anyone who considers arithmetical methods of producing random
digits is, of course, in a state of sin." - John Von Neumann (1951)

Erik de Castro Lopo wrote:
> "todd.leonhardt@gmail.com" wrote:
> >
> > I am relatively new to DSP and I have what seems like a simple
> > question, but I have not been able to find in answer to it by
reading
> > DSP books.
> >
> > If the goal is to design a frequency-selective filter, then is
there
> > any reason not to simply take the FFT of a signal (or a window
> > thereof), apply our filter by directly multiplying the filter
amplitude
> > response with the FFT of our signal, and then take the IFFT
(inverse
> > FFT) to get back the filtered signal?  Is there any disadvantage to
> > doing this as opposed to using an FIR or IIR filter?
>
> Yes, filtering in the frequency domain is far more computationally
> expensive than doing it in the time domain for most sensible filters.

> By sensible filters, i just about any IIR filter or any FIR filter
> with less than 1000 coefficients. For really huge FIR filters then
> frequency domain methods may be preferable.
>
> Erik
> --
> +-----------------------------------------------------------+
>   Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
> +-----------------------------------------------------------+
> "Anyone who considers arithmetical methods of producing random
> digits is, of course, in a state of sin." - John Von Neumann (1951)

My understanding was that the computational efficiency advantages
kicked in for far fewer FIR filter coefficients than that.
Chapter 18 of Stephen Smith's 'The Scientist and Engineer's Guide to
Digital Signal Processing', available at www.dspguide.com, reckons
around 40 to 80 coefficients. Smith gives a concise description of FFT
convolution.
In answer to the original poster's question, and to re-iterate what
others have already said in response, it's a good idea! Have a search
for 'overlap-add', 'overlap-save' or 'fast convolution'.
Picking up on the original poster's phrase 'or a window thereof', note
that rectangular windowing is appropriate in this technique.

Donald

Todd,

> If the goal is to design a frequency-selective filter, then is there
> any reason not to simply take the FFT of a signal (or a window
> thereof), apply our filter by directly multiplying the filter amplitude
> response with the FFT of our signal, and then take the IFFT (inverse
> FFT) to get back the filtered signal?

The crux of the problem here is in choosing the number of samples of the 
signal that you want to apply your FFT-IFFT on. Let's understand this.

When you multiply a signal by a finite width rectangular pulse (scaled 
appropriately) in the frequency domain, it is equivalent to convolving 
the time domain samples with the inverse transform of the rectangular 
pulse in the time domain. The inverse transform of a finite width 
rectangular pulse, happens to be a sync pulse, that stretches infinitely 
from [-inf, +inf] in the time domain. This means that you need to have 
input signal samples from [-inf, +inf] to do this, that is, take samples 
from [-inf, +inf], apply the FFT, multiply, and then apply IFFT.

Now, you might say that you're just going to take a small subset of the 
input samples and do this same operation on that subset. But remember, 
that the moment you decide to take a subset, say from [T1 T2], you're 
implicitly truncating the impulse response of the filter, that is, 
you're saying that your infinitely stretching sync pulse now only 
stretches from [T1 T2]. Try taking the FFT of this truncated sync pulse, 
and you'll see that its shape in the frequency domain is no longer a 
rectangular pulse! Instead, you'll see that the truncation in the time 
domain caused distortions in the frequency characteristics of your 
filter - both in the passband and in the stopband.

So now, you need to redesign your filter by applying some constraints - 
such as passband ripple, etc. And this opens up a multitude of "windows" :-)


Cheers!
Ravi Srikantiah

> Now, you might say that you're just going to take a small subset of the 
> input samples and do this same operation on that subset. But remember, 
> that the moment you decide to take a subset, say from [T1 T2], you're 
> implicitly truncating the impulse response of the filter, that is, 
> you're saying that your infinitely stretching sync pulse now only 
> stretches from [T1 T2]. Try taking the FFT of this truncated sync pulse, 
> and you'll see that its shape in the frequency domain is no longer a 
> rectangular pulse! Instead, you'll see that the truncation in the time 
> domain caused distortions in the frequency characteristics of your 
> filter - both in the passband and in the stopband.

Sorry, I didn't present this properly.

The moment you decide to take a subset of the samples in the time 
domain, in effect, you're multiplying the time domain signal by a 
rectangular pulse. Doing so is equivalent to convolving the spectrum of 
the infinite signal with a sync pulse in the frequency domain. This 
means that the signal you're working with now is not the original signal 
but a spectrally distorted one. As you increase the number of samples in 
your time domain, the sync pulse in the frequency domain gets narrower 
and narrower until it approaches the ideal impulse (when T1 and T2 are 
-inf and +inf respectively)

You have to be very careful about what you are doing in the frequency domain, 
and think about the corresponding effects in the time domain. If you simply 
brick wall in the frequency domain, then you get serious time aliasing - the end 
of  your signal begins to appear at the beginning. The brick wall filter is 
infinitely long in the time domain, and cannnot be represented accurately with 
FFT / IFFT's.

Windowed FIR designs are the first crack at handling this. They essentially 
truncate and smooth out the ends of the infinitely long sequence. This produce 
effects though in the frequency domain - ripple in the passband, finite 
attenuation, and a transition width between passband and stopband.

Windowed FIR designs are not optimal in any kind of way. Other FIR design 
techniques allow tradeoffs between the effects I mentioned in the frequency 
domain (ripple, attenuation, transition width).

The FIR's can be implemented using FFTs but to filter a very long time sequence 
you have to look at techniques like "overlap and save" or "overlap and add", 
these are techniques to handle the blockiness of the FFT and dividing your input 
data up into chucks that fit into an FFT.

The input transient you discovered is a result of causality. Using a simple 
brick wall filter (no phase) in frequency assumes you know the what the data is 
before it arrives - which sadly most of us don't (I don't want to discuss time 
travel :) ). You can think of this as time shifting your infinitely long (brick 
wall) filter in time to the right i.e. a time delay.

FIR filters get longer when you want less ripple, more attenuation and a smaller 
transition width. The closer you get to your brick wall filter in frequency 
domain the closer your FIR filter gets to becoming an infinite sequence.

IIR's are a trade off you can achieve similar magnitude response as an FIR, but 
with much fewer taps (coefficients). Unfortunately you pay for this with the 
phase. IIR filters have non-linear phase - this may or may not be important 
depending on your application.

FIR can have linear phase if they are symmetric - for more info you'll have to 
look it up. Most FIR design techniques produce symmetric FIR's (have linear 
phase - you can think of this as a constant time shift of the signal).

Hope that helps.

Cheers,
David

<todd.leonhardt@gmail.com> wrote in message 
news:1101957855.721740.171340@f14g2000cwb.googlegroups.com...
>I am relatively new to DSP and I have what seems like a simple
> question, but I have not been able to find in answer to it by reading
> DSP books.
>
> If the goal is to design a frequency-selective filter, then is there
> any reason not to simply take the FFT of a signal (or a window
> thereof), apply our filter by directly multiplying the filter amplitude
> response with the FFT of our signal, and then take the IFFT (inverse
> FFT) to get back the filtered signal?  Is there any disadvantage to
> doing this as opposed to using an FIR or IIR filter?
>
> For the mathematically inclined ...
> Suppose we have a signal x(k) and it's DFT (calculated via FFT) is
> X(f).
> We also have a desired filter specification represented by it's
> amplitude response, A(f).  Then, a filtered version of this signal,
> y(k) can be found:
> y(k) = IFFT { X(f) A(f) }
>
> I tried doing this using MATLAB and some noisy data for the specific
> case of a highpass filter with a cutoff frequency very close to DC, and
> it worked great.  I simply used an ideal highpass filter
> characteristic.  Is there something I'm missing?  If it is this simple,
> then why do DSP books focus so much on FIR and IIR filters?  I figure
> I'm missing something important and probably "obvious".  Please
> enlighten me ... politely.
>
> On a related note .., I was trying to design an FIR filter (using a
> windowed truncated impulse response) to filter this same data.  The
> problem I was having is that there was an initial transient of
> relatively long duration and of an amplitude that was several orders of
> magnitude larger than the "good" filtered data.  Is there a way to
> avoid this - i.e. is there a way to eliminate or greatly minimize this
> transient?  I tried using an IIR filter and the problem was even worse.
> For this particular application, the data is logged and then stored on
> a computer, so the processing doesn't need to be real-time, any type of
> filter (non-causal, etc.) should be fine.  Any advice/insight would be
> appreciated.
> 

Thanks for the feedback everyone.  I appreciate it.  I think I now
have a decent understanding of the advantages/disadvantages.

"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message
news:41AEB6EF.6E1FF508@mega-nerd.com...
> "todd.leonhardt@gmail.com" wrote:
> >
> > I am relatively new to DSP and I have what seems like a simple
> > question, but I have not been able to find in answer to it by reading
> > DSP books.
> >
> > If the goal is to design a frequency-selective filter, then is there
> > any reason not to simply take the FFT of a signal (or a window
> > thereof), apply our filter by directly multiplying the filter amplitude
> > response with the FFT of our signal, and then take the IFFT (inverse
> > FFT) to get back the filtered signal?  Is there any disadvantage to
> > doing this as opposed to using an FIR or IIR filter?
>
> Yes, filtering in the frequency domain is far more computationally
> expensive than doing it in the time domain for most sensible filters.
> By sensible filters, i just about any IIR filter or any FIR filter
> with less than 1000 coefficients. For really huge FIR filters then
> frequency domain methods may be preferable.

In addition, if you are writing the code yourself from scratch, time-domain
filtering can be a whole lot easier to code up than FFT<->filter<->IFFT.  A
biquad IIR takes just a handful of lines of code, and an FIR with a circular
buffer even less.  On the other, if you have libraries available to do the FFT
already, then maybe it's not an issue.  Time-domain uses less memory as well and
can be run on a sample-by-sample basis rather than buffering, waiting for a
block to arrive, etc. which may be an issue for real-time implementation.  YMMV.
-Jon