In previous videos we have defined the 
spectrum of a discrete time signal. 
The discrete time Fourier transform or a 
DTFT. 
Well, it turns out if you try to apply 
that formula to the computational 
spectrum which you didn't have a formula 
for, example The signal was data, you'd 
be in big trouble. 
it turns out for all kinds of reasons as 
I'll show you, you actually could not 
compute this spectrum of that signal. 
You couldn't find the spectrum at all. 
So we're going to define, the tool, the 
Discrete Fourier Transform or the DFT, 
that allows us to perform spectral 
analysis from discrete time signals. 
I'm going to show you that this is not a 
new transform, it's directly related to 
That the DTFT, but its used for 
computational purposes, we actually can 
compute the spectrum. 
To go for its properties and it shouldn't 
be much surprising that there are some 
details when you actually try to apply in 
applications.So lets worry about actually 
computing. 
The DTFT, and I don't mean analytically I 
mean computing. 
So, there are two problems in computing 
the DTFT. 
The first is, that the, Formula here 
assumes the signal is infinite duration. 
Well, that's a problem because how in the 
world would you even store an infinite 
duration computer much less compute this 
expression. 
So I think it's pretty obvious how we're 
going to fix that. 
That one's not really very difficult. 
But the next one is, and that is F is a 
continuous variable. 
And this expression, F, is a, is a, 
fraction, let's say, going through zero 
up To 1. 
All right because it is periodic with 
period 1 or we have to compute it for 
every value in that interval, reason is 
the inverse transform. 
Let me write the inverse transform so we 
can remember what it was, so we take the 
DTFT multiplied by. 
An integrate. 
The problem is integration. 
We would need to compute this formula for 
every value of f, and there's an 
uncountably infinite number of values. 
In order to find what the original signal 
was. 
We don't want the spectrum to be a dead 
end. 
We want to be able to get back the 
original signal in many applications. 
So this continuous frequency variable is 
a real problem. 
So, we're going to fix these 2 problems 
And the first one will be, fixing the 
first ones easy. 
You're only going to deal with finite 
duration signals, so every signal is 
going to be linked in, as N values and 
we're going to know what N is because 
we're the ones computing the spectra That 
one's not hard. 
The second problem's got an interesting 
solution. 
We're going to sample infrequency. 
So we're only going to evaluate the DTFT 
at a set of values given by k/K. 
Okay, k is the frequency index from 0 up 
to K minus 1. 
And of course, that means we're 
evaluating f, from 0 up to K minus 1 over 
K. 
And that is sampling the interval zero to 
one. 
leaving off the last value because the 
value frequency equalt to 1 is the same 
as the frequency equal to 0. 
We don't need to compute that. 
So the sampling rate is 1/k. 
And that's the separation between these 
frequencies. 
Now, we know from the sampling theorem, 
that we've already talked about, that the 
sample in time we need the spectrum to be 
band limited. 
That's the result. 
Now here, we're sampling in frequency, 
which means in time, it needs to be time 
limited. 
And the reason we know this follows, is 
because of the similarity mathematical 
similarity between the expressions of the 
transform and its inverse transform. 
Well, a finite duration signal is time 
limited. 
So, we know it should work. 
The question is though, how big is k? 
We're going to have to worry about how 
big does k have to be. The bigger k is, 
the higher the sampling rate. 
Because this related to 1 over k. 
How big does it have to be? So, here's 
the expression for the discrete Fourier 
transform, the DFT. 
It is a sampled version of the DTFT 
specialized for finite duration signals. 
We always take that duration the 
so-called support To be over zeroed and 
minus one it's just the standard the 
notation for DFT is just S of K. 
We don't bother sticking in the detailed 
expressions for the DDFT and then saying 
evaluate it at, at frequencies of little 
K over big K just simply write it as S of 
K. 
k if the sequence were little k is the 
frequency index. 
This corresponds to a frequency of zero. 
And this index corresponds to Z of k 
minus 1 over K. 
All right, again, how long should, how 
big should k be? That's where we want to 
Figure out. 
Well I'm not going to appeal to the 
sampling theorem here. 
What I'm going to do is do, it in a 
slightly different way. 
And that is because we know the inverse 
transform has to look like this. 
It's going to fit in with every thing we 
know. 
it's going to have to be a sum over the 
DFT values times e to the plus j2 pi nk 
over capital K. 
What have I waited over the signals 
support with where it's defined be 
originally, what it's duration was. 
And if I take this expression, plug it 
into here, I better get back s of n to do 
something proportional to it. 
Well, how big does K have to be, in order 
to make that true? In order that we avoid 
aliasing and we get back our original 
signal at least to a constainable 
portionality. 
And, it's, shouldn't be too surprising, 
to see that the result is That big K has 
to be greater than or equal to the N. 
N is the derision of the signal. 
The details of are shown, are shown in 
the notes. 
you sh, you could do it yourself, it's 
not terribly difficult. 
There are a few little things you have to 
look out for, but it's pretty Pretty 
easy. 
Now, I have called this transform length. 
Let me go into that. 
If you look at this expression here, I 
can write it like this. 
I can write it like that. 
Notice I changed this upper limit here. 
Where, since I know that big K is greater 
than or equal to N, I know that S(n) is, 
is non zero, only from 0 to n minus 1, 
well I can make S(n) [SOUND], I can 
define a new S(n) if you will, at 0 not 
to K minus 1. 
Change what it is, and I'm now computing 
a D, DFT, whose length is given by this 
new duration. 
That's the same thing as taking a longer 
transform. 
So, if you wanted to sample infrequency 
more finely, all you do is take a longer 
transform, longer means. 
I have my original signal here, and I 
just add extra zeros. 
To the end of it, until I get to K - 1. 
Well, that's called padding, and it's 
something we do all the time. 
we want to evaluate the DFT. 
and for many reasons, the length greater 
than the signal's duration. 
Let me just call that padding, and just 
adding extra zeros to the end of it. 
Since we know what capital N is, there's 
no ambiguity. 
When we compute the Inverse DFT formula, 
we're only going to look over the result 
of this computation, where we know the 
original signal values were. 
So that's another difficulty, we won't be 
confused by these extra zeros. 
Not a big problem. 
Adding, your going to, as your going to 
discover, is a very important idea. 
So, let's, Show our DFT and inverse DFT 
formulas. 
And, what happens when you go through the 
details is that this normalization of 1/K 
occurs in the inverse DFT formula. 
And of course we need K>=M. 
Now, most of the routines that compute 
the inverse DFT formulas like the ones 
that come with octave or matlab take care 
of this normalization for you. 
So you don't need to worry about it. 
But, if you were going to write your own 
Or, if you try to find, problems with 
routines that you may be using, you need 
to know about this normalization. 
So, they look very similar to each other 
as you might expect and these 2 formulas 
allow us to go between the. 
Discrete the, the time domain if you will 
for a discrete time signal. 
In the, in its frequency domain, where we 
are sampling the actual continuous 
frequency. 
We're sampling it right. 
These values, I Emphasize that. 
And we'll see how this works in an 
example in just a second. 
So, we're evaluating at those 
frequencies. 
So, to show you what it looks like. 
Here's a constant signal, which I'm going 
to be using in my examples. 
And it's a constant, because it goes from 
between 0 and N - 1, and in, all of those 
values are 1. 
When we take a longer transform, what 
we're essentially doing is. 
Padding with 0s out to the new 
transformer and then we evaluate the dft 
expression here with the K essentially 
being the transformer. 
With the added zero stuck on. 
Now, I want you to notice something about 
the inverse DFT formula. 
So, I can evaluate, this expression for 
any value of n I want. 
I know that's where the signal is, but 
what about the other values of N? and 
what you can see, because of the 
properties of that complex exponential, 
that the Inverse DFT formula is periodic. 
With a period equal to capital K, the 
transform length. 
So, if you were to evaluate this inverse 
DFT expression For all possible values of 
n this is what you'd get. 
You'd get a periodic repetition, of the 
original signal. 
But the period, is k, not n but k because 
that's the transform link, that you were 
using. 
Essentially up here. 
So, what does this mean? That means that 
when you actually look at the inverse 
DFTs result you just ignore everything 
outside the range where you know where 
the signal is. 
The other pieces out here are just 
periodic repetitions, and they're, we 
know to ignore them, and we can ignore 
the padding, because we know why it's 
there. 
It's there just to sample in frequency 
more finely. 
And we didn't really need to do it. 
But sometimes, you do it for all kinds, 
you do it for all kinds of reasons that 
we'll talk about a little bit later. 
So anyway, the original signal only 
exists there. 
And that's all you need to evaluate. 
Alright. 
So, let's go through an extended example, 
using our constant signal There's our 
signal. 
It's, zero outside the interval. 
0 to n-1. 
And we're going to compute its DTFT. 
So this is, if you will, the true 
spectrum. 
This is the Fourier Transform. 
Like I keep saying, if you don't have a 
formula for your s of n, you'd be you 
could be in very great difficulty trying 
to compute this thing for all 
frequencies. 
so that's why you're DTFT is an int. 
But let's compute it analytically for 
this example. So the way we do that is 
use the finite geometric series formula. 
So, I think you'll agree that this and 
this are the same thing when alpha is e 
to the minus j, 2 pi f, okay? So all we 
need to do is plug that in to this 
expression for the finite geometric 
series which you should have seen. And 
after some simplification, which involves 
pulling out at the phase, and the complex 
exponentials that you get is something 
similar we have already done before, 
we get this result that the DTFT is given 
by expression that looks very similar to 
what we had for the, in the analogue 
world, when they computed a Fourier 
transform of pulse, we get a very similar 
looking expression. 
Except it's not sine x over x, it's sine 
in x over sine x and this is called the 
digital sinc function. 
So recall back when we were doing this 
for analog, we had to define this 
function as called the sinc function. 
And here, what happened in the discrete 
time worlds, you get the discreet sync 
function and it's so called and it's a 
sine Nx over sine X. 
It looks, going to look very similar to 
the sin x over x, and the real difference 
is, and the importance difference this 
has to be periodic in N. 
And this is the way we make it periodic. 
So, there's our signal again and now we 
may compute the DFT. 
And expressions is going to look very 
similar because I'm just sampling The DTF 
one, the DTFT format we already did so we 
get exactly the same kind of expression 
that we had before using the finite Q 
method series and of course that is the 
same as sampling the DTFT. 
So this is the DFT, and this is the DTFT 
evaluated at these frequencies. 
Okay. 
So, this just goes to show you there's a 
sample version that I think that's pretty 
obvious. 
So, what does it look like? So, I'm going 
to be plotting this only over frequencies 
going from 0 to 1/2. 
Because we know that it has to be 
conjugate symmetric, and periodic. 
So the DTFT can be evaluated on and on, 
but this corresponds to positive 
frequencies in the range 0 to 0.5. 
So, this is what the digital sink looks 
like, which should be very familiar 
looking kind of thing, except it's going 
to be periodic. 
It's going to, return, re-, repeat 
itself. 
The phase, looks like this, has this 
linear expression. 
And we understand why this jump by pi 
here, has to do with the fact that the 
digital sync function goes, is really 
negative here. 
And magnitudes don't go negative. 
So we have to, make it positive. 
And that means we have to have a phase 
jump a pie. 
And that's what all of these jumps are 
here. 
They're, they're due to the fact it goes 
negative. 
So it is just a linear phase, 
and, 
and then the values with this technical 
requirement that having had the chance to 
pop. 
Alright, so, what does our sample version 
look like? So, capital N is 10, 
and what we get for a transform, which is 
exactly the same length as the signal's 
duration, is we get something very 
similar. 
It may be a little hard to see here, but 
you get the value there, and the rest are 
zero. 
I'm again, only showing this from little 
k equal to 0. 
Little k equal to capital K over 2, 
because the rest is negative frequencies 
and I don't need to repeat those values 
for you to see it. 
So, I've hidden the fact that the value 
at the origin there is 10 which has to do 
with the link to the transformer. 
So, this looks kind of weird is that 
really the spectrum? Doesn't, we've 
sampled and sort of missed all the. 
Nice parts that wiggle, that only focused 
on value of the origin and the values 
were zero. 
Can you actually get the original signal 
back? Lets worry about that first. 
So, does the original signal equal to 1 
over K times the sum over k of K in a 
formula that we got for the DFT here.. 
Is that, because this is a unit sample at 
the origin, then it's zero everywhere 
else. 
And e plus j 2pi nk over K. 
Well, the delta k just means the only. 
A term that's non-zero, corresponds to k 
equal to 0. 
And these cancel so what we get is e 
squared plus j pi n k over k With this 
thing evaluated always at k equal to 0, 
which is just 1. 
Well, that was our original sequence for 
any value of n. 
So the inverse d of t works. 
So, even though the spectrum is high-, 
looks highly undersampled. 
It turns out it's not. 
Even though we're missing all these 
values, we don't need it in order to add 
an inverse transform. 
So if you take a longer transform now, 
you start to see the details in the 
spectrum. 
And, this is one of the reasons why If 
you're interested in what the spectrum 
looks like, like looking at the spectrum 
of speech, you take longer transforms and 
then the length of that data you have. 
Like here I just doubled the length and 
it filled in the guise of the spectrum, 
at the halfway point, if you will. 
Notice that the frequency index now goes 
from 0 to 10 and that's because K equal 
to 20. 
So again, this corresponds to a At the 
frequency variable named hat and it 
repeats. 
And here, I just took any transform of 
length 64 and that really goes in the 
details. 
And if you're interested in that detail 
and seeing what the spectrum looks like, 
this is what you'd do. 
However you don't really need it if all 
you want to do, is to do some signal 
processing for example, hop/g into the 
frequency domain. 
do some things and come back. 
You can take shorter transforms, and 
there's no error. 
We can get, go back and forth with no 
problem. 
Okay. 
So, the DFT. 
We can now. 
Compute the sample spectrum of any 
discrete time signal, we don't need a 
formula for it. 
We can, now find the spectrum any way we 
want. 
and it's not a new transform. 
The DFT is not a new Fourier Transform, 
it's just a sampled version. 
With the DTFT, which in some sense is the 
true spectrum. 
Which is still we don't want to compute 
it for all those different frequencies. 
And it's often true that we padd to 
calculate the transform longer than the 
signal's duration. 
I'm showing you that You can really 
sample the spectrum more. 
Finally this'll get a better idea of 
what's going on. 
I've routinely did that for example in 
this spectrogram calculation that I'm 
going to show you in a later video, how I 
actually did that. 
But I, they're seeing something really 
important to realize and that is positive 
frequency values occur. 
When little k, the frequency index is in 
that range, and negative frequency occurs 
at the higher indexes. 
Turns out this is what the, DFT packages 
return. 
They will return the values over the 
entire range zero to capital K minus 1. 
Well this is the only part that makes any 
sense. 
This is negative frequency. 
We don't need to worry about that. 
That's positive frequency. 
So, negative frequencies over here. 
So when plotting, I'm always just 
chopping off the second half because this 
is really not needed. 
And if you'll note here there's a little 
bit of overlap here and that's because 
the value at a frequency f=1/2 is a 
little ambiguous. 
Is that positive or negative frequency? 
doesn't really matter. 
for lots of applications but they do 
overlap. 
So, succeeding videos we're going to find 
out how padding really pays off 
especially if you want efficient 
algorithms for computing the DFT.