We have now encountered several version of
the fully transformed four sequences
finite lengths and infinite lengths.
Namely the Discrete Fourier Transform for
finite length sequences.
So Discrete Fourier series for periodic
infinite length sequences.
And finally, the Discrete Time Fourier
transform or DTFT for infinite length
sequences.
How do these various forms of the Fourier
Transform interact with each other?
So first we are going to look at how to
compute the DTFT of a periodic sequence.
That will involve the delta function
again.
And, we are also going to see how to
compute the DTFT of a finite length
sequence and how it relates to the DFT of
a finite length sequence.
At the end, where we look at a technique
called zero padding, which is a way to
interpolate the spectrum of a finite
length signal using a DFT of a longer
signal which has zero appended to the
initial signal.
So it's a technique that's very often used
to displace spectra so it's important to
understand how it functions.
Module 4.7, relationships between
transforms.
We have seen the Discrete Fourier
Transform, the Discrete Fourier Series, as
well as the Discrete-time Fourier
Transform.
Now we are going to look at the DTFT of
periodic sequences on the one hand and the
DTFT of finite-support sequences.
And create the relationship between these
two cases.
And the DFT or DFS.
Finally, we will look at zero padding,
techniques that is often used to smooth
specra from finite length signals.
The DFT and the DFS can be seen as changes
of basis in c, capital N.
It's obvious, because it's a matrix vector
multiplication.
And we go from the original domain to the
DFT domain.
The DTFT, on the other hand, we introduced
as a, quote unquote, formal change of
basis over l2 of z.
Is a space of finite energy sequences.
So, basis vectors are building blocks for
any signal.
So we can write the signal as a linear
combination of basis vectors.
In the case of the DTFTs, this is formal.
Because the index for the DTFT, which is
frequency omega, is uncountable.
So we don't have a countable basis.
Yet the intuition we have from the DFT or
the DFS carries over in some sense to the
DTFT as we have seen in the preceding
sub-module.
The DFT and the DTFT are really two sides
of the same coin.
The DFT leads to numerical algorithms.
It's essentially linear algebra.
And we can derive fast algorithms based on
this formulation.
The DTFT is more of a mathematical tool.
It comes in handy when we want to make
proofs.
And to see properties of Fourier
Transform.
Transformed.
If we are given finite length signal x n,
which has, capital n non-zero entries.
Say, for n goes from 0 to capital n minus
1.
Then the natural spectral representation
as we have seen is a DFT given by capital
X of Okay, now there are two ways to embed
x n into an infinite sequence.
One is we can do a periodic extension so
we take the index module capital N and
that gives us x tilde of N which is simply
the repetition where the period is of
length capital N.
Another way is it's finite support
extension.
So, we denote this by x over bar which is
equal to xn on the interval 0 to capital N
minus 1 and equal to 0 otherwise.
How does xk, the DFT of the finite link
signal relate to the DTFT of these two
forms of signals.
This is what we shall persue in the next
few slides.
So what is the DTFT of x tilde of n?
Well, it's capital X tilde of e to the j
omega which is a formal power series of x
tilde of n multiplied by e to the minus j
omega n.
In this expression, we placed x tilde of n
as the inverse Fourier series.
Of capital X tilde, it's in the expression
between parenthesis.
This of course is equal to the inverse dft
and we simply reorder the sums, so we take
out the sum over k, in front, and we leave
inside the parenthesis the sum over n,
gathering the e to the j to the various
power terms.
Then we recall that this infinite sum, of
e to the j 2 pi over N, n k times e to the
j omega n.
Is simply the DTFT of a complex
exponential, of frequency 2 pi over
capital N, times n k.
And this we know, is going to be our Delta
tilde signal shifted to the location 2 pi
over capital N times k.
With this we have now a formal expression
for x tilde equals the omega namely it's 1
over n, the sum of the DFD coefficients
capital Xk multiplied by delta tilde
shifted to the frequency 2 pi over capital
N x k.
Let us look at an example and take a good
old friend, the 32-tap sawtooth sequence.
We remember also the DFT of this 32-tap
sawtooth.
The periodic sawtooth sequence is shown in
this figure for a few periods.
The DTFT of the periodic extension now is
this weighted set of deluxe.
So the deluxe sit at multiples of 2 pi
over N and they are weighted by X of k.
So characteristically at the frequency 0
it's equal to 0 because the sawtooth
sequence has an average of zero.
And then because of shapes that we know
from the DFT of the sawtooth sequence.
To recap, this spectrum looks exactly like
capital x of k.
Except that the display different, because
the zero frequency is at the center rather
than at the left hand.
And we have a 2 pi here of the spectrum
where we only show the spectrum between
minus pi and pi.
And of course, rather than having finite
values .
This capital XK.
We have delta as, as is indicated here
with the red arrows.
Let us do the very same exercise.
But now, with a finite support signal.
So x over bar, as we indicated, is equal
to xn over the interval 0 to N minus 1, 0
otherwise.
It's a DTFT denoted by x over bar, e to
the j omega is simply the sum of x over
bar times e to the minus j omega, and
which in this case, is a finite sum
because x n is 0 elsewhere.
So it's a sum from zero to capital N minus
1 of e to the minus j omega N.
Now this looks very much like the DFT
except we don't have K in the exponent we
have omega.
Okay on the second line of this
development we can replace X over bar.
By the inverse dft of the Xk so which is
written between parenthesis.
Then we can take sum over k outside with
the xK and within the parenthesis we
simply have the complex exponential and
the exponent now is only omega minus 2 pi
over N times k multiplied by n.
The key therefore is this expression
between parenthesis.
This finite sum with the exponent omega
minus 2 pi over n times k.
And this, we denote by r over bar with the
Fifth to the location omega minus 2 pi
over capital n times k.
This r over bar is actually the dtft of
the interval indicator signal.
So, indicator is 0 elsewhere, but only
interval 0 n to capital N.
This one.
So we show here r over bar simply in the
case of n is equal to, well let's count,
must be 9 or something like this in this
case here very simple elementary signal.
And we're going to calculate the DTFT of
this r over bar signal.
So R over bar e to the j omega, it's a sum
of e to the minus j omega n from 0 to
capital N minus 1.
This is our good old friend, it's a finite
geometric series, we see this on the
second line, we take out a phase factor,
Factor.
E to the minus j omega, N over 2.
Both upstairs and downstairs.
But downstairs, we also have the capital
N.
And this allows us to replace what's
between square brackets as sine of omega N
over 2 versus, in the denominator, sine of
omega over 2.
And the face factor is simply, factored
out.
We see, now, the DTFT for the case, N is
equal to 9.
And in this case, we show the real part.
And if we center, actually, these signals.
Then the face factor would be equal to
one, and we'd see exactly this.
Now we can finish the computation of the
DTFT of the finite-support signal.
So x over bar of e to the j omega is the
sum from 0 to capital N minus 1 of X k
times Lambda, only got minus 2 pi over n
times k, where lambda of omega is simply
renormalized version of r over bar as a
DTFT of, as a finite interval indicator
signal.
Let us look at what happens if we take a
32-tap sawtooth sequence.
We know the DFT an old trend, it must be
the third time that we see this DFT with a
0 value at the origin 0 and it's
characteristic details on going back up
towards 31.
One.
A finite support extension is shown here
for a support of, I guess, 128, plus -128,
so we see the sawtooth in the middle and
it's zero elsewhere.
Is a DTFT of the finite support extension
is now sketched here by taking the DFT and
smoothing It by interpolating with the R
of E to the G omega function.
So we add one two three, et cetera.
And as we go, we find the smooth
interpolation here between the points of
the DFT that are in Light grey in the
background.
This should look familiar because we have
computed this spectrum already once in
module 4.4 and we got the exact same
result.
As a comparison to the DTFT of the
periodic extension, we see some similarity
but some differences, so here we have a
small spectrum, in the case of Periodic
extension we had a set of D-racks/g, but
of course the coin side, that's the
location of the D-rack, we pass exactly
through with the red function here which
is the smallest interpolation.
Now, this was quite a bit of effort to
actually compute a DTFT of a finite
support signal.
And so what people often do is I'll say
take the finite support signals, the
extended with zero, so called zero
padding.
And then they compute the DFT numerical It
generates definitely nicer plots, and
we'll shall see a few examples in the next
slides.
The DFT of the 32-tap sawtooth,[LAUGH]
again, and we are going to zero pad it.
So here, we zero pad it with 64 zeroes.
So the first 32 entries are equal to the
sawtooth and the next 64 entries are 12
zeroes.
You see the DFT, it has a similar shape as
the DFT of the initial period of length
thirty-two at the origin at If the K is
equal to zero, then it's still zero, so no
suprise there.
So let us compute discrete fully transform
of a zero product signal.
Let's call it capital Xm of h where h is a
frequency, it is a sum from zero to
capital m minus 1 of a signal X prime
which is the extension of the initial
signal.
X and the usual expression, so this a sum
from 0 to capital N minus one of Xn, e
equal minus j 2 pi over capital M, that's
an important point, n times h.
We use the usual trick, by now you should
be familiar with this one, so we have the
sum over Small n and then we replace xn by
the inverse dft of Xn, it's usual
expression.
And we then reorder the summations.
So we take out a summation over k in front
with the x, sub mk.
And between parenthesis, we have this
expression which now looks familiar to sum
from 0 to M minus 1.
And it has exactly the same expression as
the DTFD over finite link symbol, but
instead of having omega, we have 2 pi over
capital N times h.
And so this is simply the expression of x
over bar e to the j omega.
Evaluated at the location Omega is equal
to two point Pi over capital N times H.
The exercise we had done before.
So obviously zero padding does not add any
information that is not already in the DFT
or for that matter in the DTFT.
And so a zero padded DFT is simply a
sampled version of the discreet time fluid
transform of the finance support extension
of the signal.
Let us do this by example again.
Guess what?
We take the 32 tap sawtooth sequence, 0
padded.
So, the 32 point DFT.
And we are, family width, of course.
Here is 1 half of this 32 point, DFT.
And then we have the DTFT of the finite
support signal in blue.
And we.
Simply sample it, for example here we have
the 96 point DFD which was the extension
we have seen just earlier, and we find
indeed the DFD as predicted by sampling.
We do the same exercise now with a 200
point DFT and this is a sampling of the
DTFT of the finite support signal as show
here in blue and the samples in red.