>> In this video we're going to discuss the implementation of digital filters, and
I don't mean what kind of software environment or issues like that.
What I'm more concerned about are efficiency and using filters that have the
characteristics that I really want in my application.
So we're going to talk a little bit about IIR.
Iir versus FIR filters. Turns out that FIR filters are used
frequently as are IIR. The choice really depends on some details.
We're then going to talk about the con, computational complexity.
Whether you want to implement a filter in a time-domain, what I mean by that is just
program the difference equation. Or whether you want to implement frequency
domain which means using 4a transforms. We're going to find that in many cases
frequency-domain filtering despite the idea you might say well geez taking all
those transforms can't be that good. Ah,turns out it winds up being efficient
in many cases because of. Properties of the FFT.
Now, let's consider the IIR filter first and what we can start is worrying about a
time domain of limitation ie, we use the difference equation.
And it's pretty easy to see That, for each output p multiplies and p minus 1
additions for what I call the IIR part, and q plus 1 and q for the FIR part.
And putting all these together in terms of complexity For each output the complexity
is order p plus q. Now even if the input is a finite duration
the output for an IIR filter is infinitely long.
This has an infinite duration units impulse response.
So. The number of computations is
theoretically infinite. What happens in practice is that once the
last input has been passed into the filter the succeeding calculations the filter
does produce an output but usually it settles down after a while being used.
Seems to stop the computations, but that depends on a host of values not the least
of which are the values of the, of the a coefficients, so it turns out, for all
practical purposes IIR filters are. An infinite computational complexity but
in practice we actually have fewer but that's hard to judge here.
I'm going to point out by the way that we are not going to talk much about filter
design. There are, as you might expect, software
programs that design these filters for you.
In other words, you give it. Specifications of let's say you have a low
pass. You want to know what the cut off
frequency is and you give that. It will come back with a set of
coefficients, values for p and q and a set of coefficients that will do the job.
Job. And that, turns out.
So, the filter design problem is really nothing more than running some software.
There's software out there for FIR filters, too.
It's very different, But it works very well, too.
What you discover is that the number of. Coefficients for an FIR filter to do a
specific filter job is going to be more than the total number of coefficients for
an IRR filter. In general, this is true.
Not always. But in most cases, it takes more
coefficients to. Compute the Fir filter all the B's, then
it does some of the A's and B's for the FIR filter.
But anyway, we now can compute complication complexity because this is an
FIR filter. The complexity for each outfit is order Q.
And therefore if the input has a duration n, the output is going to have a duration
of n plus q. Notice that the duration of the unit
sample response here runs from zero to q, so the duration's q plus 1.
So using my old formula for the duration of the output is n.
Notice that the duration of the input was the duration of the mid sample response
minus 1. And that gives us the n plus q.
So the complexity is q times n plus q. Okay.
So that's the complexity. And, We can use this to consider whether
we want to actually implement that f-r filter in the frequency domain.
So, this brings up the issue of a frequency domain implementation.
Now, we know it's true, because this is the way the mathematics works, that the
DTFT. The output is equal to the DTFT of the
sample response times the DTFT of the, note that this is always true.
However as we've talked about, you actually can't compute these things
because the frequency interval f, that's the stumbling block.
F has a uncountably, infinite number of values you'd have to compute it for, and
you could never get there. So we have to use the DFT.
Now, the DFT is a sampled version of these.
So y k is a sampled version of the y e to the j 2 pi f.
We kept, these are sample versions. This is a sample version.
And this is a sample version.So there's some issues we need to talk about.
So but let me go through what the frequency domain implementation is.
You have some input. The idea is, we're going to take its DFT,
obviously using the FFT algorithm, to get the sampled spectrum of x.
We're then going to multiply that by the sampled spectrum of the transfer function.
Now, I didn't show taking the Fourier transform of the.
The example response because usually that's a fixed quantity.
We know what the filter is, we're just trying to run data through it so there's
usually, you don't consider the complexity of the one time com, computation of this
trans, sample transfer function. We multiply the two together.
That produces, hopefully, the sampled spectrum of the output.
Take the inverse DFT and finally wind up with our output.
So the idea is, this is our linear system. Linear shift and variance system.
I put a box around it. And what we're going to worry about is how
to implement it. We're going to do it in the time domain
with a difference equation or are we going to use this frequency domain
implementation? Now, can we use this implementation in the
frequency domain for an IIR filter? Well, by definition, we, our unit sample
response has infinite duration. To compute the DFT, I need a finite
duration sample. So I can't even compute, this, as a
Fourier transform. I can sample the formula.
For the transfer function, which can be derived from the difference equation to
get an h of k. However, the sampling theorem still
applies. Those sample values correspond to, those
correspond to an alias version. Of the unit sample response if the actual
IIR filter. So you can't really get there, you, you
can't really find anything useful using this approach.
So it turns out IIR filters really can't be implemented in frequency domain it's
just. It goes.
F-r builders though, I think all systems are go here.
It has a finite-duration, output, because little h is a finite-duration, so I can
find this by taking the DTF, and everything's fine.
So we're going to be off and running with this approach.
We're going to talk about frequency domain implementations of FIR filters.
All right. Now, here's where the subtleties come in
of the FIR filters. All transform lengths have to be the same.
It makes no sense to multiply an x times a capital h where these were taken with
different length transforms. Furthermore, the output is derived from a
inverse d of t, so, the duration this transform here has to be of the same limit
as this one, and the one that is implicit here.
So, the transform length that determines it is how long the signal is.
The length of the signal. You have, have to take a transform that's
at least as long as the signal. Well, that means the longest signal.
Is going to be the one. Well, by far and away, the one that's the
longest is the output. And as we know the duration of the output
is the duration of the input plus the duration of the unit sample response minus
1. And that means our transforming has to be
bigger Were equal to n plus q. So.
That means this, this has duration n. This has duration q with a little h and n.
That means we're going to have to pad those and take a transform at least n plus
q long which is going to be The sign, the duration of y then, of course N plus q
might not wind up being counter 2 for using the FFT, so we're going to pad that
even with 0, with 0 so we could get to the power of 2.
So you could be taking fairly long transform.
Especially of h of n, in order to, to meet this requirement because n could be much
bigger than q. Alright, so, but is it more efficient to
go through all that work? Is it better to implement in a time-domain
versus the frequency domain? Now, better does not mean you get better
quality results. Presumably, in today's computers, the
computational accuracy would be about the same.
That's not the issue. The issue is speed.
Which one is faster. Now, the number of computations for a
linked in input in the time domain, is given by this.
We have n plus q output values, we have to compute.
And the complexity for each was 2q plus 1. The formula for the.
Frequency domain approach is rather interesting.
So you see the term over here that relates to the transforms.
I have two transforms I have to compute. They each have the same complexity because
they have to be the same length. And so that's where 5 times N plus q log 2
of N plus q comes from. The six here, which is just proportional
to n plus q has to do with this multiply. This is a complex multiple inspector or
complex value. So you have an a plus jb, times a c plus
jd. And you'd have to multiply that out.
That requires four real multiplies and two addiotions.
And that's where this 6 comes from. So, the question is, which is smaller?
Whichever is smaller is going to be the one.
That we want to choose. We do not want to choose the one that's
bigger. That would mean more computations.
So, let's see how that works. So here I have a plot of the number of
computations it takes versus in the time domain and in the frequency domain.
N is along this axis. Q is along this axis.
And you can that the time domain, while it may be prettier plot, turns out to be
bigger than in the frequency domain for all values of N.
And it's only when the filter length is less than about 20 is the time-domain
small. So N is not the consideration, what
matters is the number of coefficients in the filter.
And it turns out that the filter length gets bigger than about 20 or so.
It is much more effeciant to do things in frequency domain much, much fewer
complitations. So it is worth all that work in most
applications to take transformers and inverse transformers really does make the
filtering occur much more effecintly and quickly.
Frequency domains are ready to go. So, I want to digress a little bit and
talk a little bit about long inputs. So, suppose the input X is a million
points smaller, does this means I have to take a million plus, let's say a 100
length transform of that? Do all those computations at once.
The answer is no because we can use the principle of super position.
And here's the idea. Just like we did for spectrograms, I can
divide up the long input into sections. Okay?
I can filter each separately. Okay?
And because the signal consists of the blue part plus the green part.
They really don't overlap in time. They're at separate times.
But conceptually, since it consists of the sum.
I just need to add up the results. And so, what you get for an FIR filter is
you will, might have a output which looks like this, but's it's going to be longer
than the input, or however long the filter is.
And so, it will extend into the boundary of the next section.
The green signal gets filtered and it produces this which again is longer, but
we now have to use superposition and in the region of what's called overlap, we
have to add them up. Well of course there's some overlap from
the previous. Section here if this wasn't really the
beginning of the sigma. And when all is said and done you get this
beautiful output here which looks like we filtered that entire, long signal at once.
We don't actually have to do that, we actually can do it using sections and
filtering each overlapping and adding the results.
This is sometimes called the overlap add method of doing these.
So you don't, you can actually process these in short pieces.
This makes things run a whole lot quicker. You just add them up and just be
continually producing output as long as you worry about this overlap region.
This is very important to get this overlap correctly.
I want to talk about something else that's in this picture, and those are the dash
red curve. This input that I started with consists of
a sine wave, which I show as a dashed red line.
With noise added. Noise is random signals, usually of a high
frequency content, that just sort of gets in the way.
And, Makes the signal look ugly. And once I added the noise, I got the
signal shown by the stem plot. Which is very erratic.
And you can barely tell there's a sine wave inside.
1 of the great uses of low pass filters is to get rid of high frequency noise.
To try to remove it as much as possible. Some of the noise usually has some power
in the same frequency band as the signal. You can't get rid of that but you can
certainly get rid of the, the noise, the high frequency content that has nothing to
do with the signal. And that's what I did here.
I've used a low pass filter In both these cases.
And I produced a result with is given by the blue output down here.
You can see that it kind of resembles the, sine wave.
But it doesn't quite. And like I said, that's due to the fact
that some of the noise has frequency components that are close to the frequency
of the sine wave, it's hard to remove those.
What's more interesting though is why is it shifted over?
Why is there, why is the peak of the input here.
But the peak of the amplitude is over here.
If you look carefully, it's about the same shift, all the way accross.
What's causing that? The answer is, it's a linear phase shift.
Due to the filter. The filter had to be implemented somehow,
and that always produces a linear phase shift.
Which is very predictable. In other words, I know what that linear
phase shift is, it's a property of the filter, and I understand that it's going
to, the output is going to look like a phase shift.
With respect to inputs of, some sense I could shift back the blue ones to, if I
wanted to, in order to make it look like the input if that were ever an issue.
Okay, so, implementing filters. When you go through the filter design
process. Ok, steady.
Usually true that the FIR, the IIR filter rather is fewer coefficient values than in
FIR filter. It's hard to figure out the computation
complexity of the IIR filter but in most applications is probably going to be true
than an IIR filter is also faster. However people tend to use FIR filters in
very interesting applications. In particular, ones where linear phase
characteristics are involved. Linear phase means a pure delay.
It turns out II filters, IIR filters. Cannot have a linear phase.
You'll get what's called phase distortion, which may be an issue or may not.
One of the more attractive reasons though, for using FIR filters is even though, they
may be, have more coefficient values is that they can be implemented using the
FFT. That really makes it quite Interesting and
attractive that means you can get a chance to look at the signal spectrum while
you're filtering in advanced applications that might be important.
And so in a lot of cases people use the FIR filter and go that way.