Welcome to module 5.4.
The time has come to look at filters from
the frequency domain prospective.
And the starting point is this amazing
result.
If you take a complex exponential and
process it with a linear time invariant
filter.
What you get at the output is a complex
exponential at the same frequency as the
input, only the phase and the amplitude
may have changed.
This has all sorts of interesting
implications when we consider the Fourier
representation of the elements involved in
a filtering operation.
We will derive what is called the
frequency response of a filter, and we
will use that to classify filters in the
frequency domain.
We will also revisit our friends the
moving average, to linking to greater, and
even the carpal strong algorithm and see
how they fair In frequency.
Welcome to module 5.4 of digital signal
processing.
A module in which we will look at
filtering from the vantage point of the
frequency domain.
And to do so we will introduce the concept
of Eigensequences.
Which despite the fancy name are just
complex exponential.
We will derive the convolution theorem,
after having obtained a frequency
representation of filters.
And then we will look frequency of phase
response of filters we know.
What happens if we take a linear time
invariant filter h, and we use as the
input a complex exponential of known
frequency omega zero?
Well let's write out the convolution.
Then we exploit the fact the, that the
fact the convolution is commutative, and
we, exchange the order of the terms in the
convolution product.
At which point we can start writing out
the convolution with some explicitly and
we have the sum for k that goes from minus
infinity to plus infinity of h of k that
multiplies e to the j omega 0 and minus k.
Now, we can take out the constant term,
doesn't depend on k, out of the sum, and
we have a Lydian term of e to the j omega
0 n, that multiplies the sum for k that
goes from minus infinity to plus infinity
of h of k times e to the minus j omega 0
k.
Now this guy here, we know very well what
it is, is the DTFT of the impulse response
computed in a mega zero.
So it's big h of e to the j omega zero,
which multiplies our original input e to
the j on the omega 0 n.
Hence, the name Igo sequences, just like
Igo vector is a vector that when
multiplied by a matrix, gives a scaled
version of itself.
An Igo sequences is a sequence that when
Input to a linear time invariant filter,
returns the sequence itself times a
scaling factor.
Which happens to be the value of the DTFT
of the impulse response at the frequency
of the input.
So the first fundamental property that we
can glean from this derivation is that a
linear time invariant system cannot change
the frequency of a sinusoidal input.
And so since the sinusoidal input is a
pure frequency component it's clear that
the DTFT of the impulse response fully
determines the frequency characteristic of
a filter at a given frequency.
Let's examine a little bit more, what
happens when we process a complex
exponential with a linear time invariant
filter.
If we write the value of the DTFT of the
impulse response at omega 0.
As a times e to the j theta, where a is a
real number and theta, of course is an
angle between minus pi and pi if you will.
Then we have the processed complex
exponential, is the original complex
exponential, which has been scaled by the
amplitude a, and has been delayed or
advanced, by a phase term theta.
So if a is larger than 1, then we have an
amplification.
If a is less than 1, then we have an
attenuation of the input sinusoid.
And the phase shift again, if it's bigger
than 0 then we have an advancement of the
sinusoid.
And if it's less than 0 then we have a
delay.
The convolution theorem tries to
generalize this result by asking the
question, what is the DTFT of the
convolution of the two sequences.
Or in another words what are the DTFT of
the output of a filter?
The intuition here is that the DTFT
reconstruction formula tells us that any
signal is made up of infinitely many
sinusoidal components of the form x to the
e to the j omega times e to the j omega n.
And if I were to process a single
sinusoidal component independently by
filter h, I would get a value like so, h
to the j omega, e to the j omega n.
So I wouldn't be surprised if the DTFT of
the convolution of two sequences was just
a product of the Fourier Transform.
So let's go see how we can drive this more
formally.
If we write out the DTFT of the
convolution of 2 sequences well, we can
write out initially the formula for the
DTFT which is the sum from n from minus
infinity to infinity of the value of the
convolution in n times e to the minus j
omega n.
Then we expand the formula for the
convolution inside of the DTFT n summation
and we get a double summation over the
indices n and k of the convolution product
here times this complex exponential here.
In the next step we do a little trick
where by we add and subtract k from the
argument n.
So instead of putting n, we write n minus
k plus k, and in so doing we managed to
split the complex exponential into 2
components here that we will distribute
across the summations.
And now here we collect the terms that do
not depend on n.
And here we put the rest, this first term
here is the DTFT of x of n.
That's really easy to see, the 2nd term,
looks like a DTFT, we might be confused by
the fact that the indices here and here or
n minus k instead of n.
But the fact that the index n ranges from
minus infinity to plus infinity makes this
term completely irrelevant.
And so, indeed we have the product of 2
DTFTs.
The product of the DTFT of the impulse
response times the DTFT of that impulse.
The Fourier Transform of the impulse
response is called the frequency response.
And just like in the case of a single
complex exponential, we can split the
significance of the product in the
frequency domain.
By separating the effects of the magnitude
and those of the phrase.
So the magnitude of the frequency response
will determine weather certain frequencies
of the input signal is going to be
amplified or attenuated according to
whether the frequency response is larger
than 1 or smaller than 1 in magnitude in
certain frequency bands.
Defects of the phase are a little bit more
difficult to qualify right now but it will
be clearer later on that the phase will
determine whether the signal will conserve
its shape in the time domain or its shape
will be altered.
Let's go back now to our friend the moving
average and compute it's frequency
response.
The moving average has an impulse
response, which is just the indicator
sequence for the interval 0 to capital M
minus 1 divided by capital M, we have
already computed the DTFT of such a signal
in module 4.7.
If we consider now the magnitude of the
DTFT we find out that it's just 1 over
capital M multiplies the absolute value of
sin of omega over 2 times m divided by
sign of omega over 2.
An interesting thing to remember is that
the magnitude response is going to be 0 at
multiples of 2 pi over m except in 0.
So here you see that you have indeed, M
minus 1 0s along the frequency axis.
We can plot the magnitude of the response
for increasing values of M so for instance
here you have the frequency response for m
equal to 20 and you can count the 19 0s
along the frequency axis and here you have
the frequency response for M equal to 100.
And you can see that the frequency
response is very concentrated around the
origin.
We will see the significance of that later
on.
Let's go back to our denoising example
that we studied in the time domain in the
previous module.
And look at its development in the
frequency domain.
So remember we had azimuth signal here
we're talking time domain.
So we had azimuth signal that was
corrupted by some additive noise that we
represent here in orange.
In the frequency domain, the spectrum of
the smooth signal looks like this.
Most of its energy is concentrated around
low frequencies so it's low-pass signal,
and the Fourier Transform of denoise looks
like noise in the frequency domain as
well.
So when we put things together we have the
spectrum of the smooth signal.
We have the spectrum of noise and the sum
is denoise spectrum of the measured
signal.
When we use the moving average to filter
this noisy signal, in the frequency domain
we're multiplying this spectrum by the
frequency response of the moving average,
and in magnitude it looks like this.
So here we're using, for instance, a nine
point average as you can see from the
number of zeroes along the frequency axis.
So the product in magnitude determines a
very deep attenuation of the high
frequency and therefore most of the noise
that was contained in these bands has been
eliminated.
At the same time though, if you compare
the result of the filtering operation with
the original spectrum you see that the
filtering has eliminated parts of the
original spectrum that actually had every
right to be there.
So that proves that there's no free long
signal processing as well.
And in order to remove the noise sometimes
you have to remove some of the good part
with it as well.
Before we move on let's look once again at
the same denoising operation in the time
domain now that we know what's going on
and the frequency domain.
And we can see that when we use a moving
average of say, length 12, we are indeed
smoothing out the highest components of
the noise but not so much the ones that
are slower moving and that we are ready,
starting to alter a little bit the
curvature of the signal, as explained by
the spectrum we just derived.
So what about the phase?
The best way to understand the effects of
the phase on a signal is to distinguish
three different cases.
The first one is zero phase, which means
the spectrum is real.
The second case is linear phase where the
phase is proportional to the frequency by
a, a real factor d.
And the third case is nonlinear phase
which covers all other possibilities.
To understand what phase does to a signal,
let's take a very simple discreet time
signal made up of the sum of 2 sinusoid x
of n is equal to 1 half sine of omega 0
times n plus cosine of 2 omega 0 times n.
So it's 2 sinusoid at frequencies 1 double
of the other.
And the sum looks like this signal that we
plot here in this graph.
We can call this signal, a zero phase
signal, because the phase associated to
each sinusoidal function is zero.
Now, let's add a phase term to each
component, and make sure that the phase is
proportional to the frequency of the
sinusiod.
So what we add is theta 0 to the first
component at frequency omega zero.
And we add 2 theta zero to the second
component, whose frequency is 2 omega
zero.
The value of theta zero is actually
irrelevant, but we can see that when we
add a phase term to the sinusoidal
components.
That it's proportional the, the frequency
of this sinusoid.
The net effect in the time domain is just
a shift of the signal.
The shape of the signal remains exactly
the same.
If now we add a phase that is non
proportional to the frequency, so in this
case, we change the phase to the first
term to zero and we'll leave a phase term
of two theta zero to the second term while
the frequencies of the two components have
not changed, the shape of the signal in
the time domain has changed significantly.
Please note that in all 3 cases, the
spectrum of x of n remains exactly the
same in magnitude.
To understand that the linear face term is
simply a delay in time domain.
Consider the following system, where we
have a filter d that simply produces a
delayed version of its input.
The input output relationship is this one
here.
And in the frequency domain, we can take
Fourier Transforms left to right and we
obtain that big Y of e to the j omega is
equal to e to the minus j omega d times
big X of e to the j omega.
This is really equivalent to saying that
the frequency response of this delaying
filter is simply e to the minus j omega d.
So, again, we have a linear phased term.
Where the phase introduced by the filter
is proportional to the frequency via a
factor d.
Which actually represents the delay in
time domain.
In general, if we can split the frequency
response of the filter into the product of
a pure real term and a pure phase term, it
means that the filter operates by
combining the action of a zero phase and,
therefore, zero delay component that only
affects the magnitude of the input
followed by a delay by these samples.
And this delay is inevitable in the case
of causal filters for instance.
Let's consider the moving average again,
the frequency response is the product of a
real term here and a pure phase term here
where the delay d is exactly n minus 1
over 2 which represents half the length of
the support of the impulse response.
And this is indeed the delay introduced by
the moving average.
So we've looked at the moving average and
by now you know that what comes next is
the leaky integrator.
And indeed, let's consider the impulse
response which you remember is 1 minus
lambda times lambda to the power of n
multiplied by uni step so an exponentially
decaying sequence.
If we take the Fourier Transform of that,
we've done that in detail in module 4.4
and here is the result.
Big H, lead to the j omega is 1 minus
lambda divided by one minus lamda times e
to the j omega.
Now to find the magnitude and the phase of
this animal, we need to use a little
algebra and we need to recall this very
simple result.
If you have one over a plus jb, you can
always rewrite that as a minus jb divided
by a squared plus b squared.
So if the number x is actually 1 over a
plus jb, the magnitude square of x is 1
over a squared plus b squared and the
phase of x is the inverse tangent of minus
b over a.
This applies to the leaky integrator in
the sense that we can rewrite the
frequency response as 1 minus lambda
divided by 1 minus lambda cosine of omega
which is the real part of the denominator,
minus j times sine of omega, which is the
imaginary part of the denominator.
And by applying the formula that we just
saw, we find out that the magnitude
squared of the leaky integrator is 1 minus
lambda squared divided by 1 minus 2 lambda
cosine of omega plus lambda square, and
the phase of the leaky integrator is the
inverse tangent of lambda sine of omega
divided by 1 minus lambda cosine of omega.
So you can see that the phase is
definitely non-linear in, in this case.
If we plot the magnitude we can see that
we have a characteristic that is very
similar to that of the moving average
although we don't have any zeros and the
characteristics is monotonic rather than
the [unknown].
As lambda goes closer to 1 we see that
once again the frequency response
concentrates around the origin and for
lambda very, very close to 1.
We have something that resembles the
frequency response of a moving average
computed over a large number of tabs.
The phase looks like this, it's a non
linear characteristic and as lambda
changes the steepness of the transition
between positive and negative phase
increases as well.
What is interesting in terms of the
combination between the magnitude and the
phase response is that what interests us
is the part of the filter where the
attenuation is not too big, because that's
where the frequencies will pass through
whereas here there will be fundamentally.
And in that area where the frequency
response has a magnitude that is
sufficiently close to 1, the phase is
actually more or less linear so we can use
the leaky integrator without incurring
excessive phase distortion in the
[inaudible].
Finally, let's revisit another classic
namely the Karplus-Strong Algorithm.
And let's try to analyze its behavior
using the convolution theory.
Remember the Karplus-Strong Algorithm is
initialized with a finite support signal x
of support capital M and then we use the
feedback loop with a delay of capital M
taps to produce multiple copies of the
original finite support signal.
Scaled by an exponentially decaying factor
alpha.
So for instance, if we initialize the
algorithm with one period of a sawtooth
wave, what we get in the end is multiple
repetitions of that period scaled by an
exponentially and decaying emblem.
In the time domain we can write this out
explicitly as such.
Here we have the first period of the
output signal is just a copy of the known
0 values of the finite support signal.
Followed by another copy of the no 0
values of the finance support signal
scaled by alpha, followed by another copy
scaled by alpha square and so on and so
forth.
The key observation to analyze in the
algorithm within the paradigm of the
convolution theorem is to see that the
output can be expressed as a convolution
of the finite support input with a
sequence w of n that we build in the
following way.
W of n is equal to a to the power of k for
values of the index n.
There are the k multiple of capital M and
it's zero, otherwise.
So if I was to draw the sequence it would
look like so.
So it would be one and zero, it would be
alpha and m alpha square in 2 m, and it
would be zero in between, so a series of
exponentially decayed deltas spaced n
points apart.
With this, we can write the convolution
theorem, and we say okay, the output you
simply in frequency the product of the
fully transformed of the finance support
signal times the fully transformed of the
signal w of n.
Well, and now we can proceed exactly like
in module 4.4.
If we consider the example of a sawtooth
wave.
We know that the Fourier Transform of one
period is this one, whereas the Fourier
Transform of the sequence w of n is the
rescaled Fourier Transform of the
exponentially decaying sequence, which
means we will have several peaks happening
in the minus pi, pi interval.
We put them together graphically, we have
the Fourier Transform in magnitude of the
sawtooth period; we have the Fourier
Transform.
A magnitude of the staggered exponential
sequence, we take the product of the two
and we obtain the same spectrum that we
derived in module 4.4.