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

443 classificações

École Polytechnique Fédérale de Lausanne

Processamento Digital de Sinais

443 classificações

Learn the fundamentals of digital signal processing theory and discover the myriad ways DSP makes everyday life more productive and fun.

Na lição

Module 3: Part 1 - Basics of Fourier Analysis

3.1.a The frequency domain5:15

3.1.b The DFT as a change of basis10:49

Conheça os instrutores

Paolo Prandoni
Lecturer
School of Computer and Communication Science
Martin Vetterli
Professor
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.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play