Learn the fundamentals of digital signal processing theory and discover the myriad ways DSP makes everyday life more productive and fun.
3.1.b The DFT as a change of basis
Loading...
Do curso por École Polytechnique Fédérale de Lausanne
Processamento Digital de Sinais
292 classificações
Na lição
Module 3: Part 1 - Basics of Fourier Analysis
Conheça os instrutores
Paolo PrandoniLecturer
School of Computer and Communication Science
Martin VetterliProfessor
School of Computer and Communication Sciences
Let's start with finite length signals, which are the easiest to handle.
We have seen that a finite length signal is simply a vector in CN.
It turns out the free analysis in this case, is simply a change of bases in CN.
Now remember a change of bases is a change of perspective.
And a change of perspective can reveal things.
You're looking at things from a different angle.
So for example, imagine you have the signal like this.
This is a 1,024 points signal.
And as you look at it in the time domain, yeah you can see some
oscillatory behavior, but it's not really clear what's going on.
Well, if we perform an appropriate change of basis, and
we will show shortly how to do that, the signal will look like this.
So in the Fourier basis, the same signal will have this structure.
And it is clear here that we have two very different things going on at
the same time.
We have two spikes, and we will see very shortly what the spikes mean.
And then we have something that looks like noise in the bottom.
Well, Fourier analysis allows us to separate these two elements
that in the time domain were indistinguishable.
So here is the Fourier bases for CN.
Remember CN as I mentioned N.
So we will need N different vectors each one of which will have length N.
So K will be the index that indicates different vector.
And K will go from 0 to big N-1.
And then we will use small n to indicate the index of the element with image
vector, and small n would also range from 0 to big N -1.
The N signals will have this form.
So remember k is the index of the signal, and
small n is the index of the element within each signal.
And each element is simply e to the j Pi over big N and k.
What does that mean?
This is simple complex exponential at a frequency omega
which is two Pi over big N times k.
So the index of the vector or of the signal,
gives you the fundamental frequency of the complex exponential.
We claim that this constitutes a set of orthogonal vectors in CN.
We can express the signals in vector notation, so remember our
convention we use bold face letter to indicate vectors, a superscript in
parentheses will give you the index of the vector when the vector comes from the set.
In this case it comes from the set of big N vectors and
a subscript will indicate the element within each vector so again w of k
of n is simply equal to e to the j 2 pi over N and k.
We can quickly get a feeling for what these vectors look like if we remember
the complex explanational generating machine we saw a few modules back.
So here for instance we show the components of w1,
the second vector in our basis.
And as we go through the components, so this would be the first component of
the vector, it would be equal to 1, the second component would translate
the point around the circle by an angle 2 pi over N and so on and so forth.
Remember, w 1 of n will be equal e to the j 2 Pi over big N and
so we're going around the circles in increments of 2 Pi over big N.
Now the second vector in the basis,
w2 of n will be of the form te to the j two Pi over big N, 2N.
And so this vector will move in increments of two Pi over N times 2.
So the points for that would actually be these guys and so on.
Okay so let's look to at a concrete example by setting big N equal to 64 and
look at the Fourier basis for the space C 64.
Here we're looking at the real and imaginary components of each basis vector.
This, if you think of the point moving around in circles in the complex plane,
will be the cosine and
sine of its subtangent angle as the point moves along the circle.
So here we have the first factor in the basis, w0 and
each component of this factor will be simply ej 2 pi over big N 0 times N.
And because of the multiplication by 0, the exponent will be always 0 and so
this vector is identically equal to 1.
Its real component therefore is one for all instances, and
its imaginary component is zero everywhere.
The next vector is w1, and
here the fundamental angle of the complex exponential is omega 2 pi over N.
What this means is that the point will complete one full revolution over 64
points and we can see this in the plots of its real and imaginary components.
Here we have a full cosine period for the real part and
a full sine period for the imaginary part.
The next vector goes twice as fast.
Now the fundamental frequency of the complex exponential
will be 2 pi over big N times 2.
And indeed we have two periods
of the cosine and two periods of the sine in the imaginary part.
The next vector is w 3.
And the fundamental frequency will be 2 pi over big N times 3.
So we have three periods both in the real and in the imaginary Pi.
By now you underhand what's going on.
And as we go up with the Basis index,
the vectors will start moving faster and faster.
Because of the discrete nature here,
it will be hard at one point to recognize that we have sinusoids.
Here, for instance,
you have w16 that moves very quickly, but you have to imagine that
the movement captures a rotation that goes very fast around the unit circle.
Here, for instance, we have only four points because the angle of the complex
exponential turns out to be 2 Pi over 64 times 16, which is equal to Pi over 2.
From here, the point will move between these four points.
And if you look at the coordinates in the real and
imaginary part, you see exactly this behavior.
As we increase the index of our Fourier vector,
the underlying frequency increases as well.
Now, the discrete nature of the vector makes it a little bit hard to understand
the signs of the shape of the signal.
But you can see for instance here that we are in the high frequency range
because the sign of the samples changes at every step.
So the sign alternation is a tell tale sign of a high frequency sitazoid.
Finally, we reach the highest frequency that discrete time complex exponential
can have.
So here it happens for K equal to 32 where our frequency
becomes 2 pi over 64 times 32, which is equal to pi.
At this point,
we will be moving from this position to this position in the complex plane.
And this is clearly indicated by the real and imaginary components of the vector,
which are alternating plus and minus one in the real part and
identical to zero in the imaginary part.
As we go forward index, as we saw in model 2.2,
the apparent speed of the point decreases and
the direction of the rotation changes from counterclockwise to clockwise.
So here as the index increases from 32 up to 63, we see
that the apparent speed of the sinusoid decreases back to 0.
But the sign that we're past pi, as far as the angular increment at each step is
concerned, comes from the phase of the imaginary part, which is inverted with
respect to the equivalent frequency that we have seen for low values of the index.
So here, for instance, if you compare this basis vector to w of 2, you would
see that the real part is the same, but the imaginary part has a sign in version.
In w of 2, it would be like this.
Same goes for w63,
real part is equal to w1, but imaginary part has a sided version.
Okay, so this is all nice and fun.
We just showed a very beautiful family of little vectors, but in order for
these vectors to be a basis of CN,
we have to prove that they are orthogonal to each other.
Orthogonality requires that the inner product between
any two vectors of the family is zero.
So we write out the inner-product between w of k and w of h.
We write out explicitly the inner product by considering
each component of the first vector.
Conjugate the component and
multiplied by the corresponding component of the second vector.
And we obtain a sum for n as small n goes from 0 to big N minus 1 of
e to the j 2 Pi over N h minus k times n.
So how do we solve this formula?
Well there are two cases.
First of all let's assume h is equal to k.
So we're actually taking the inner product of a vector with itself.
At this point all these elements in the sum will be equal
to one and so the sum will converge to n.
In case h is not equal to k,
then this is a sum of the form small n that
goes from 0 to big N minus 1 a to the n.
And we know that this is equal to 1- a to the big N, 1- a.
So we plug the complex exponential into this formula and we obtain this ratio.
But now this guy here on top is e to j two Pi times H minus K.
This guy is an integer and
therefore this is E to the J times an integer multiple of 2 pi.
So what that means is that no what the value of h-k is,
we're in this point here on the complex plane.
And so 1-1 will be 0, and this will be 0 for all h not equal to k.
So, the vectors are orthogonal and therefore they form a basis for CN.
Now, note that the vectors are not orthonormal
because w(h), w(h)=N as shown before.
The normalization factor will be one over square root of n, but
you will see later that we usually keep this normalization factor
explicit rather than implicit for computational reasons.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
