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.