Hi and welcome to module 4.4 of digital
signal processing.
In this module we will explore how Fourier
analysis applies to
the three different classes of signals
that we introduced in our course.
Namely finite line signals, periodic
signals and infinite signals.
We have already looked in detail at the
case of finite
length signals where the DFT is the
Fourier tool of course.
We have also shown in passing
that for periodic signals the DFT extends
naturally into the DFS.
Which is a natural presentation for
periodic sequences.
And in the rest of the lecture today we
will introduce, finally,
the DTFT which is the Fourier tool of
choice for infinite length sequences.
And the rest of this module we will use
the Karplus-Strong algorithm, which we
first saw in module 2.3, to illustrate the
key points of each different
Fourier representation.
Let's start with periodic sequences.
An N-periodic sequence has only N degrees
of
freedom and the DFS captures the situation
by
providing us with a spectral
representation for the
sequence that only has N distinct Fourier
coefficients.
We can illustrate these points more in
detail with the help of the Karplus-Strong
algorithm.
You remember how the Karplus-Stong curcuit
works.
You have an input,
you have a delay line ff length big M, and
matt generation factor alpha.
As the samples go into the circuit they
get pushed out
to the output and they get pushed also to
the delay line.
They were stored here and output at the
other end of the delay line after
big M samples where they get accelerated
by
a factor alpha and summed to the current.
If we were to describe this mathematically
we would
have what we call a difference equation
that relates the current
output to the past output that has gone
through the delay line.
So an output delayed by big M, scaled by
the attenuation factor and summed to the
original input.
We can use this circuit to generate a
simple periodics signal.
And to do that we choose an input signal x
that is non-zero only for n
between zero and m.
That means that x of n is actually a
finance
support sequence and that's why we use the
over bar notation.
You will only have big M non-zero samples
and it will be zero everywhere else.
Then we choose alpha equal to one so there
will be no attenuation in the loop.
If we input this signal to the
Karplus-Strong circuit we
will see that the output consists of a
periodic signal where
each period is constituted of the M
non-zero samples of the input finite
support signal.
Suppose, for instance, that our finite
support signal looks like this, has a
non-zero support of 32 points, and over
the support it looks like a straight line.
And it's zero everywhere else.
So if we use this as an input to the
Karpus-Strong algorithm we will get a
periodic repetition of this shape which,
overall, will look like a saw-toothed
wave.
If we take the DFT of this signal,
considered as a
32 point finite length signal, the DFT
will look like this.
computing the exact value of the DFT
coefficients is left as an exercise just
note,
for instance, that the coefficient of zero
is
zero because the signal is actually
centered around
zero so its average is zero.
What happens, then, if we take the DFT of
two periods?
So we consider the first 64 points that
come out
of the Karplus-Strong algorithm and we
take a DFT of this.
Well, if we go through the math or even if
we put this into a numerical package
we will see that the shape of the DFT
coefficient, the envelope so to speak, is
the same
as the one for just the first 32 points.
However for every DFT coefficient there is
an extra DFT coefficient with value zero.
In other words, the DFT coefficients
have been interleaved with zero valued
coefficients.
To get an intuition as to why it is so
let's go back to the definition of DFT.
Each DFT coefficient will be the inner
product between
the appropriate basis vector in the
Fourier basis
for c64 and this signal that we see here.
So let's see graphically how this inner
products are computed.
Let's start with the first basis vector.
We will show here in blue just the ideal
shape of this basis factor.
We don't really care about the real and
imaginary part because we're just
interested in the structure.
The first factor is just the constant one
and
the result of the inter-product will be
the non-normalized average of this signal
in red.
We know the average to be zero.
The same holds for two periods, so the
first coefficient is zero.
For k equal to one we have the first basis
vector and this
will be a sinusoid that will spend a full
period over 64 points.
What that means is that the first 32
points will be multiplied by a shape that
is exactly the inverse of the shape for
the next 32 points.
And so this sub sum of the inner product
plus this will give zero.
For k equal to two, on the other hand, the
Fourier vector will span two periods over
the space of 64 points and so here we
simply have twice the same thing.
This half of the inner product
will be equal to the second half and the
DFT coefficient will be twice the original
DFT coefficient.
For k equal to three we have another
situation of anti-symmetry between the
first part of
the Fourier vector and the second part and
so these two parts will cancel each other
out.
We can see that in general all odd index
coefficients will be zero for this two
period signal.
So we can prove this for an arbitrary
number of periods.
Suppose y of n is a finite length signal
that
is composed of L repetitions of the same
big M points.
So we said that over bar x of n is a
finite support signal that is zero
everywhere except in a portion here.
So we take this portion, this is M points,
and we build y of n by putting
L of these pieces together.
So, this will be L of that.
Before you transform of y of n is simply
given by
the sum for n that goes from zero to LM
minus one.
LM being the length of this signal now.
Of y of n times E to the minus j two pi
over LM times n times k.
And k ranges from zero to
LM minus one.
So this is standard stuff, the only
difference
is that length of our signal is LM.
We can split the sum in the following way,
we have an outside sum where we span
the number of periods and an inner sum
where we go through the points in the
period.
And so here we simply replace k with n
plus pm.
So k was ranging
over the entire signal now we split this
into period plus index inside the period.
We can do the same inside the complex
exponential
and so then we can split the complex
exponential
and we see that the inner sum is this one
here and this term depends only on p.
So we can bring it forward and have a
product of
two sums where we have this term here that
ranges over
the P index and this term here that ranges
over the N index.
And the two are independent.
But now, this guy here we've seen before.
This is exactly the same formula that we
use to prove the orthogonality
of the DFT basis.
And so we know that this sum will be
equal to big L if' k is a multiple of' L
or zero otherwise.
So with this
knowledge we can plug this back into the
formula for the Fourier Transform
of' L periods and find out that the kth
DFT coefficient will be equal
to L times the original DFT coefficient
that you could have computed for the
finite support signal if K is a multiple
of L and zero otherwise.
So given the DFT of L periods
you will have only one known zero DFT
coefficient out of L
and this will be equal to L times the
original DFT coefficient.
Well this was a long way to show that,
once again, all the spectral
information for a periodic signal is
contained in the DFT of a single period.
And that's why for periodic singal in the
end we use a DFS.
So the situation so far is the following.
For N-point finite length signals we will
use the DFT.
For N-point periodic signals we will use
the DFS.
One category is missing and that is
the category of infinite length,
non-periodic signals.
We can use the Karplus-Strong algorithm to
generate one such signal
simply by putting the gain factor alpha to
less than one.
In this case we will have an infinite
length signal
that is non-periodic because for every
repetition of the m
point sequence the gain factor will
decrease.
So the first period will be unaffected.
The second period will be scaled by alpha.
The third period will be scaled by alpha
square and so on and so forth.
So what is a good spectral representation
for this signal?
We can start with a DFT and we can see
what happens when the length of the signal
goes towards infinity.
Intuitively, the fundamental frequency in
cn, remember, the
fundamental frequency of the Fourier basis
in cn is omega equal to two pi over n.
As n goes to infinity omega becomes
smaller and smaller and
the set of frequencies in the zero to pi
range becomes
denser and denser.
In the limit the set of multiples of the
fundamental frequency two pi over n will
become so dense that we will try to
replace this by a real valued variable
omega.
And this real valued variable will span
the zero to pi interval.
So if we replace that in the formulation
for the DFT we get
a sum now over all the points in the
signal and instead of having
multiples of the fundamental frequency we
have a real variable.
Does this make sense mathematically at
least?
So let's try and give a formal definition
of what we call the Discrete-Time Fourier
Transform, a Fourier transform geared at
infinite length known periodic signals.
We require that our infinite signal is
square syllable.
That means finite energy.
It's a reasonable requirement to prevent
summations from blowing up.
We define now a function of a real valued
variable omega, and remember
this is a function not a sequence, and the
summation goes like so: F
of omega is the sum for n that goes from
minus infinity to
plus infinity of x of n times e to the
minus j omega n.
When this value exists we can actually
invert it and retrieve
our sequence values by taking the integral
from minus pi to
pi of F of omega e to the j omega n
into omega and normalize in the integral
by one over two pi.
It's easy to verify that this is so.
If you replace F omega inside here by this
definition and invoke
the fact that x of n is clear solvable.
Now f of omega is two pi periodic.
We can see that because it depends on e to
the minus
j omega n and this animal is two pi
periodic in omega.
To stress the periodicity of the DTFT,
instead of writing f of omega
for a sequence x of n, we will write the
DTFT as x
of e to the j omega.
So, although the free variable is omega,
we will write
e to the j omega as the argument of the
function.
This will remind us that this is a Fourier
transform and that it is two
pi periodic no matter what happens because
the
argument of the function is two pi
periodic.
Another difference with respect to DFT is
that for the DTFT we choose the
minus pi pi interval as the representative
interval for the transform.
So these are conventions of a historic
nature
and although they're a little bit
confusing it's
particularly unfortunate, for instance,
that the difference between
DFT and DTFT is just a T here.
We will preserve the nomenclature and the
conventions in order to be compatible or
congruent with the DSP literature out
there.
So let's look at an example of DTFT.
Let's take a simple sequence, an
exponentially
decaying sequence, we know the sequence
from the
introduction of this class and we know
that
it is a no periodic infinite support
sequence.
When alpha is less than one we also know
that
this sequence has finite energy so we can
compute the DTFT.
We do that.
So we write the formal definition.
This is the sum from minus infinity to
plus infinity of'
x of' n times e to the minus j omega n.
Here we use the values for the sequence.
The sequence is one-sided.
There's a unit step here.
So that means that the index of the sum
will start in zero and for n
equal to zero or larger, the value of xn
will be alpha to the power of n.
We can collect the two powers under
the same exponent and we can see that this
is
simply a geometric series with ratio alpha
e to the minus
j omega and so the result will be, in the
end,
one over one minus alpha e to the minus j
omega.
The magnitude of the Fourier transform is
easy to compute.
It will be one over one plus alpha square
minus two times alpha cosine of omega.
And when we plot this remember now the
convention is that we're
plotting frequencies from minus pi to pi
rather than from zero to pi.
So the positive frequencies will be on the
right-hand side of the frequency axis.
The negative frequencies,
the one that turned clockwise, will be on
the negative side of the frequency axis.
The low frequencies will be now centered
around zero and
the high frequencies will be on the
extremes of the bat.
With this convention in mind we can look
at the spectrum of the exponentially
decaying sequence and look like this for
say alpha equal to zero point nine.
So it's a signal that contains energy
in the frequency of the main mostly around
the low
frequencies, of course, because it moves
rather slowly to zero.
However, never forget the inherent
periodicity of the Fourier transform.
If we expand the frequency axis outside of
the minus pi pi interval, and we can
certainly do that because omega is a real
valued variable, what we find is that the
shape
of the spectrum repeats outside with a
periodicity of two pi.
So the fundamental interval is this but as
we
plot outside we get further copies of the
spectrum.
Again, fundamental interval, first
repetition, second repetition, and the
positive axis and same thing on the other
side.
So let's go back to the Karplus-Strong
algorithm.
Try to generate a non-periodic infinite
support signal and then compute its
spectrum according to the new DTFT
paradigm.
So we start with the same shape as before
for the initial data for this
Karplus-Strong algorithm since we're going
to be
presice in the the derivation of the
spectrum.
It is useful at this point to look at the
analytical formulation for
this shape so x of n between zero and 31
is equal to
two n divided by big M minus one minus one
where big M in this case is 32.
If we put in a decay factor
in the Karplus-Strong algorithm equal to
zero point
nine you see that the repetitions
generated by
the Karplus-Strong algorithm have a
exponentially decaying envelope.
And can we can express the output as alpha
to the power of the Flour of n divided by
big M that multiplies the periodic signal
obtained by putting
copies of the pattern we saw in the
previous picture one after the other and
all of
this is multiplied by the unistep because
we assume
that the signal starts at n equal to zero.
So zero everywhere here and exponentially
decaying
saw tooth wave for N greater than zero.
Analytically, the Fourier transform of
this signal can be computed like so.
Remember the definition.
So y of e to the j omega, the DTFT of the
signal we just showed in the picture, is
equal to the sum for
n that goes from minus infinity to plus
infinity of the value
of the signal in n times e to the minus j
omega n.
Just like we did before we split the sum
into two parts.
An outer sum that spans every quote
unquote repetition of the basic shape.
Although, of course the standard
signal is not periodic, so each repetition
will be scaled by a different factor.
And an inner sum that goes inside each
repetition.
Inside each repetition we have the values
for the basic pattern and alpha to
the power of p an exponentially decreasing
gain factor that creates the decaying
envelope.
We can split the exponent in the complex
exponential
again as p big M plus n and by doing so
we can split the sum into the product of
two sums.
The first term is something that looks
like a DTFT.
Notice that the index is p and we add
alpha to the
power of p then multiplies e to the minus
j omega big MP.
So if it wasn't for the big M here this
would be a discrete
time for the transform of the sequence
that starts at zero and goes
to infinity and whose samples take the
value offered to the power of p.
Namely, this is the DTFT of an
exponentially decaying sequence except for
this factor here.
We'll see how to take care of this in a
second.
The second factor is equal to the DTFT of
a signal that is equal to the basic
pattern from
zero to big M minus one and zero
everywhere else.
So we can write this as the product of two
DTFTs.
The first one is the DTFT of
the exponentially decaying sequence that
we saw before.
And the factor of M in the exponent
propagates to the argument of the DTFT
and simply means that we are contracting
the frequency axis by a factor of M.
It's just a re-scaling of the frequency
axis.
The second term we'll compute in just a
second.
So let's look back at what the
Fourier transform of the exponential decay
looks like.
The fact that there is a factor of M in
the
exponent simply implies that there's a
scaling of the frequency axis.
So we're contracting the frequency axis by
a factor of big M.
But be careful because this contraction
will
actually have to take periodicity into
account.
So when big M is equal to one we have the
standard spectrum of decaying exponential.
When M is equal to two we're bringing in
two
copies of the spectrum inside the minus pi
pi interval.
So what before was periodic over two pi
now becomes periodic over pi.
And when M is equal to three you will have
three copies of the basic
spectrum that fall into the minus pi pi
interval and so on and so forth.
This is, for instance, the case for M
equal to 12.
Now onto the second term of the product.
As we said, that was the DTFT of a finite
support
sequence that is linear between zero and
big M minus one.
The result is a little bit ugly and a
little bit cumbersome to drive so we leave
that as an exercise and we put some slides
in the end of detail how to compute this.
But fundamentally this is the result and
if you plot the magnitude of this function
you have something like this.
In the figure you have the magnitude of
the DTFT of the 32 point saw tooth period
that we saw before.
This is known zero between zero and 31.
And indeed if you count the local maxima
here there are 32 of them.
Okay, to compute the final spectrum we
have to multiply
the first term which is, remember, 32
repetition of the
basic spectrum of a decaying exponential
times the spectrum we just computed.
It turns out that these peaks in a of e to
the j omega M align with local maxima of
the spectrum of the first period so that
the final
result looks like this where the peaks of
the first term
in the product slim down the lobes of the
second term.
So here we have derived the DTFT, namely
the spectrum
of an infinite non-periodic signal that is
not a trivial signal.
Now so far we have treated the DTFT as a
formal operator and in the next module
we will see how the DTFT relates to the
concept of change of basis
in an appropriate Gilbert space.