>> 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.