[SOUND]
Hi and welcome to module 4.5 of digital
signal processing.
In this module we will continue the
exploration of the DTFT.
And we will consider, in particular,
conditions related
to its existence, its properties, and how
we
can look at it as a special type
of basis expansion in the space of
infinite sequences.
So existance means simply
that the sum that defines the DTFT does
not blow up.
This is easy to prove for absolutely
summable sequences, if
you take the magnitude of the DTFT at any
point omega.
This is equal to the sum for N that goes
from minus infinity to plus
infinity of X of N times e to the minus J
omega N in magnitude.
Now every time you have absolute value of
the
sum, you know that this is maximized by
the sum
of the absolute values of the elements of
the sum.
So we do this, and because the magnitude
of the complex exponential is 1,
this is actually equal to the sum of the
absolute values of the sequence.
Since our initial hypothesis was that the
sequence
was absolutely summable, this is less than
infinity.
And therefore, the DTFT exists for all
values of omega.
Similarly, we can invert the DTFT very
easily
if we assume absolute summability of the
underlying sequence.
As we showed in the previous module, the
inversion
formula is 1 over 2 pi times the integral
between minus pi and pi of the DTFT times
e to the J omega n in the omega.
So we replace x of e to the j omega by the
definition of the
DTFT in here, and because of the absolute
summability of
the sequence we can invert the summation
and the integral.
When we do that we have the sum for k that
goes from
minus infinity to plus infinity of x of k
time this integral here.
So each element of the sequence in the sum
is multiplied by this integral, which
depends on k.
But now look at the numerator of this
fraction, here.
This is a complex exponential, and if n is
different than k, this will span an
integer number of periods in the minus pi,
pi integral, and therefore the integral
will be 0.
So what that means is that integral is 0
unless
n is equal to k, at which point all the
elements in the sum will be killed except
for x of n, and so in the end, we have the
result we're looking for.
The DTFT looks exactly like an inner
product in the space C infinity.
If you take this inner product here
between an
infinite sequence and the sequence e to
the j
omega n, and you write the definition of
the
inner product, you get exactly the
formulation for the DTFT.
The problem here is that C infnity is not
really a well definied vector space.
There are sequences that do not converge
in C infinity.
Nonetheless, if we manage to establish a
formal parallel between a change of basis
and the DTFT, it will mean that everything
that we discovered about a
DFT which is a well defined entity, will
apply to the DTFT as
well and all our intuition about the
frequency domain will translate to the
DTFT.
Now, the basis here that we're
talking about is not really a basis,
because it's an infinite
and uncountable set of vectors, indexed by
a real value variable omega.
So something breaks down, really.
We start with sequences, but we end up
landing in the space of functions.
On top of it all, although we just proved
existence
and invertability for absolutely summable
sequences, in reality the DTFT exists,
for all square summable sequences, which
is a larger set of sequences.
But in that case the proofs we just gave,
become
much more technical, and so we will skip
them here.
Let's sum up the situation so far.
For finite length signals, we start in CN,
and via a change of
basis, we compute their representation,
the frequency domain,
which as well, lives in CN.
We can go back to the original sequence
via the inversion formula.
And the basis that allows us to go from
the
time domain to the frequency domain is the
DFT basis.
The Fourier basis for the DFT, which is a
countable set of N Fourier basis vectors.
The DFS is exactly the same.
The expansion and reconstruction
formulas are the same, except that in this
case, we assume that everything is
periodic underneath.
And now we have the DTFT.
We start from the space of a square
summable
sequences, and via a formal change of
basis, so basis
here is in quote, we end up in the space
of square integrable functions, on the
integral minus 5 pi.
By looking at the DTFT as a formal
basis of expansion the linearity property
follows
easily from the linearity of the inner
product.
So, the DTFT of a linear combination of
two
sequences will be the linear combination
of the DTFTs.
A second property that is easy to prove
from
the definition of the DTFT is the time
shift property.
So if we take a sequence and we shift it
in time by big M samples,
the DTFT of this shifted sequence is equal
of the DTFT of
the original sequence, times a delay
factor e to the minus J omega
big M, which is very similar to what we
obtained in the
case of the DFS, when we took the shift of
a periodic sequence.
To dual of this property is the modulation
property of the
DTFT, so if we take a sequence and we
multiply this by
a complex exponential at frequency omega
0, what happens in frequency
is that we have a shift of the spectrum by
omega 0.
The time reversal property tells us that
the
Fourier transform of a time reverse
sequence, a sequence
where we flip the values across the origin
will be equal to a frequency reversed
Fourier transform.
And the conjugation property says
that if you conjugate every value of the
sequence
the Fourier transform will be both
conjugated and frequency reversed.
Now, some particular cases that are very
useful to remember because they appear
often.
First of all, if the sequence is
symmetric, then the DTFT is symmetric as
well.
If the sequence is real, then the DTFT is
Hermitian-symmetric.
The reality of the sequence can be
expressed mathematically by saying that
x of n is equal to the conjugate of x of
n.
This infrequency implies that the Fourier
transform of the sequence is equal to
the conjugate and Frequency reversed
version of the Fourier transform.
A simple corollary of this property is the
fact that if
x of n is real then the magnitude of the
DTFT
is symmetric.
You can verify this simply by taking the
magnitude of both terms of this equation.
And an even more special case states that
if x of n is
real and symmetric then x of j omega is
also real and symmetric.
So this all looks nice and fine.
It looks like we have a full fletched
basis expansion,
and that the DTFT is just another version
of the DFT.
And indeed,
some things would lead us to believe so.
For instance, if you take the DFT of the
delta function, you remember you have the
constant 1.
And similarly, the DTFT of the delta
function expressed as the inner
product between the pseudo basis function
and the delta function is again 1.
However, some things are not okay at all.
The DFT of the constant 1 is very well
defined, and it's equal to
n times the delta function in frequency.
But the DTFT of 1 is, by definition, the
sum from n that goes
from minus infinity to plus infinity of e
to the minus j omega n.
Now to see that there is a problem with
this sum, just
put omega equal to 0, and you see that the
sum diverges.
The problem is that there are too
many interesting sequences that are not
square summable.
And of course the constant
1 is one of them.
So, in order to be able to keep
using the change of basis paradigm, even
for sequences
that are not square summable, we have to
introduce
a little mathematically trick called the
direct delta function.
This little animal here, which is usually
indicated by the symbol delta, but now
delta
of the real variable t, not the
delta sequence, is defined by the sifting
property,
that looks like this.
If we take a delta function.
We center it in s, where s is a variable
in r.
And then we multiply this delta functional
by any function of a real variable t.
And then we take the integral from minus
infinity to plus infinity.
Then what we get is the value of f in the
point s.
Graphically, we usually represent delta
functional as an upwards pointing arrow,
we centered this in s, we multiply this by
any function of
a real variable t and then we integrate
from minus infinity to
plus infinity and we get the value of the
function in s.
In order to develop some intuitions for
the properties of the
direct delta functional, let's consider a
family of so called localizing
functions, r k of t.
Where k is an interger index, and t is a
real valued variable.
The properties of this family of functions
are two.
The support of each function is inversely
proportional to the index k.
But regardless of an index k, the area of
each function, the
integral from minus infinity to plus
infinity of each function, is constant.
As an example,
take direct function.
Direct function is a classic indicator
function that is equal to 1 from minus one
half to one half, and 0 everywhere else.
So this function has a support of 1, and
an area of 1.
We can use this function to build a family
of localizing functions like so.
We multiply the rect by a factor k,
and we shrink the support of the rect by a
factor k.
So r k of t in this case will have a
support that goes from
minus 1 over 2k to 1 over 2k, so the
support is 1 over k.
And the area is 1.
If we plot some functions in this family,
this is what we get for k equal to 1.
The value here is 1.
For k equal to 5, the support has shrunk
to 1 over 5.
And the area is still 1 because the value
here is 5.
We go to 15, it will look like this.
And to 40 it will go like this, and we
could on to infinity.
Now, consider the integral between minus
infinity and plus infinity of the product
between rk of t, and any function f of a
real variable t.
Rk of t is non-zero only between minus 1
over 2k and
1 over 2k.
So these are the new integration image of
this product.
The value of rk of t over the integration
interval is k.
So we can bring this outside of the
interval.
And inside we have simply the integral of
the function over this interval.
Now we invoke the mean value theorem.
You can go back to your calculus textbook
to revise its proof,
and the mean value theorem says that the
value of this integral here will be
equal to f of gamma for some point gamma
within the integration integral.
Now, we don't know where gamma is inside
this integral, but we do know that it
exists.
Now as k goes to infinity, the support of
the indicator function becomes smaller and
smaller and so gamma which is somewhere in
the integration interval,
will be sandwiched between interval limits
that grow closer and closer.
And in the limit, f of gamma will be f of
0,
because the width of the interval has
shrunk down to an infinitesimal width.
So the delta functional is really a
shorthand for this limiting operation.
Instead of writing the limit of the
inegral for a family
of localizing functions, We just use the
delta notation, and what is
interesting is that the shape of the base
function that we use
to build the family of a localizing
function, is not really critical.
We can use pretty much any shape, and as
long
as two properties of shrinking support and
constant area are satisfied,
the limit will converge to the point-wise
value of the function.
Okay, so now a last technicality before we
understand why we're doing all this.
We will be using the direct delta
functional in the frequency domain.
Now we know that all DTFT spectra are 2 pi
periodic.
So if we want to use this tool in the
frequency domain, we have to periodize it.
The periodic version of Dirac delta
functional is
called the pulse train and it is built by
placing copies of the
delta function every 2 pi and by scaling
the whole signal by 2 pi.
So if you w to represent that in the
frequency domain, with the usual
upward arrow notation, we see that there
will be a pulse every 2 pi.
Okay, now we can let the show begin.
Let's consider the inverse DTFT of the
pulse train.
Well, we apply the definition, and we have
1 over 2 pi times the integral between
minus pi and pi, of the pulse train times
e to the j omega n into omega.
So, the first thing to remark is that
since the periodized delta is scaled by
a factor of 2 pi, this cancels
the normalization factor in front of the
integral.
Then, we are integrating only between
minus pi and pi,
in this interval we only have one
pulse, so we can remove the implicit
periodization.
And then, because of the sifting property
of the
delta functional, this integral will be
just the value
of this function of the real valued
variable omega
in 0, because this delta is centered in 0.
And so the value of e to the j omega n for
omega equal to 0 is equal to 1.
This is formally similar to the fact that
the inverse DFT
of N delta of k is
actually equal to 1.
So, by using the delta functional, we have
established another formal parallel
between the DFT and DTFT.
So if the inverse DTFT of the delta
functional is 1,
then it means that the direct DTFT, the
forward Fourier transform
of the constant 1 is formally equal to the
pulse train.
Does this make sense?
Well, we could try to compute numerically
the partial sums that
are involved in the computation of the
DTFT of the constant 1.
So define Sk of omega as the sum that goes
from
minus k to k of e to the minus j omega n.
As k goes to infinity as k of omega,
should converge to the DTFT of the
constant one.
So if we plot these partial
sums in magnitude for increasing values of
k, we have something
like this for k equal to 5 we have this
shape.
And as we increase, the index, we see that
this
family of partial sums looks like a family
of localizing functions.
So, the support gets narrow and the area
stays constant.
So, it really makes sense to
say that in the limit, this partial
sums will converge to the direct delta
function.
With this fundamental result in our
pocket, we can now proceed
to derive some other interesting DTFT
pairs for non-square summable sequences.
With the same technique we used before, we
can show that the inverse DTFT
of a shifted pulse train a pulse train
shifted by a frequency omega 0.
Gives a
complex exponential of frequency omega 0
in the time domain.
So if the DTFT of 1 is the pulse train
centered in 0.
The DTFT of an arbitrary complex
exponential of frequency
omega 0, is the pulse train shifted by
omega 0.
By using Euler's relation and the
linearity of the
DTFT, we can derive the DTFT of the cosine
of omega 0 n which is just one half times
the sum of 2
pulse trains, one centered in omega 0 and
the other one centered in minus
omega 0.
And the DTFT of the sine of omega 0 n,
which is minus j over 2, times a pulse
train centered in the omega 0, and another
pulse train centered in minus omega 0.