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

Loading...

Do curso por Escola Politécnica Federal de Lausana

Processamento Digital de Sinais

241 ratings

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

- Paolo PrandoniLecturer

School of Computer and Communication Science - Martin VetterliProfessor

School of Computer and Communication Sciences

Let's start with a little warning, to make the most of this lecture you have to be

familiar with the notation E to the power of jx, where j is the imaginary unit.

If you're not, perhaps a little review of your complex algebra textbook is in order.

We are said that in nature oscillations are everywhere,

from the heartbeat to engines to waves to musical instruments.

And the fact is,

the sustainable dynamic systems must exhibit an oscillatory behavior.

Somehow you have to have something that comes back to it's initial state,

because things that don't move in circle cannot really last for a long time.

So, for instance, a bomb has a lot of energy but

the release of energy is unidirectional, and so not sustainable.

Rockets, same way, and unfortunately, human beings as well,

although many parts inside our bodies do work in circular patterns.

An oscillation is the product of a rotation, you take a point on the plane,

you make it go around in a circle, you create an oscillatory behavior.

If you put a coordinates systems around the center of the oscillation,

you can describe the vertical and horizontal displacement of this

point as it goes around the circle with a cosine and the sine function.

So you always have two trigonometric functions that work together to describe

the position of something that turns around in circles.

Perhaps it's easier use a complex reference system centered on the origin of

the oscillation.

And use a complex exponential to describe the position of the point on the plane.

So we will say that the position of the point is described by a complex

exponential e to the j omega t, where omega is the rotation frequency.

So here we are in standard algebraic terms where t is a real variable that

indicates time, in discrete-time things are a little bit different.

The discrete-time oscillatory heartbeat has three fundamental ingredients,

a frequency omega, where the units are radians and not radians over seconds.

Because our "time variable is adimensional",

it has initial phase phi and an amplitude A, and

the discrete-time sequence is Ae to the j (omega n + phi).

We can use Euler's formula to decompose this into a real and imaginary part,

that's why we have A[cos(omega n + phi) + j sin(omega n + phi)].

So, why use complex exponentials instead of explicit sine and cosine functions?

Well, first of all, while building our own digital signal processing world,

we said we can use complex numbers in digital systems, so why not?

But it makes sense because every circle or

motion is always a sine and cosine intertwined and

Euler's formula compactly brings them together in one single function.

And it makes math simpler because trigonometry becomes simple algebra, for

instance, let's try and

change the phase of a cosine In the old-school trigonometric way.

So if we have cos(omega n + phi),

then we have to remember the trigonometric identities for the sum of angles.

And we know that the result will be something like a cos of

the first term + b sin of the first term.

But do we remember if it's plus or minus or do we remember the values for a and

b and so on, so forth?

So it's kind of a mess and very much error prone, conversely, if we try and

change the phase using complex algebra, we have the cos(omega

n + phi) is simply the real part of e to the j(omega n + phi).

Now we can decompose this complex exponential into the product of two

complex exponentials.

We have no problem performing the multiplication of two complex numbers when

we separate the real and imaginary parts.

And then we get the result without any numonic effort, so sine and

cosines live together, phase shift becomes simple multiplication and

the notation is way simpler.

Okay, so the complex exponential is our friend,

let's get to know it a little bit better.

The complex number e to the j alpha is a complex number with real

part consign of alpha and imaginary part sin of alpha.

A magnitude e to the j alpha is always equal to 1, so the point e to the j

alpha always lives on the unit circle, and how we find this point?

Well we travel along the unit circle counterclockwise until we reach

an angle equal to alpha, where alpha's expressed in radians, and

that is the position of our complex exponential.

If we have any point on the complex plane, and

we multiply this point by e to the j alpha, we are rotating

this point counterclockwise by an angle alpha on a circle,

centered in the origin, and with radius equal to the magnitude of z.

So we can use multiplication by a complex exponential

to rotate any point on the complex plane.

This is actually at the heart of complex exponential generating machine that will

create all these complex exponential signals that we will use in the future.

So a sequence like x[n] = e to the j omega n,

where omega is the frequency of the complex exponential sequence.

Can be obtained at each step by multiplying the previous point in

the sequence by e to the j omega, okay?

So this is how we recursively generate a complex exponential sequence, and

if we plot the sequence of points on the plane, it'll all start at one location.

So let's assume that x[0] = 1, and so

the next step will be 1 times e to j omega, and

we will have moved here by an angle omega, counterclockwise around the unit circle.

And then in next step we will move by another angle omega, and so on and

so forth, and that's how we generate a complex exponential signal.

Here in this example you see that after 12 steps we go back to the original point,

so clearly we can say that omega = 2pi divided by 12.

Because in 12 steps we have gone back to the starting point,

after going around the circle the sequence repeats.

Of course, initial point need not be 1,

we can start at any arbitrary point on the complex plane, and

the complex exponential sequence will proceed exactly in the same way.

Where we advance counterclockwise by an angle omega at each step,

and here, for instance, we keep the same frequency of 2pi over 12.

And so we will repeat the pattern once again every 12 steps, now so far,

there haven't been many surprises with respect to standard complex algebra.

But here is a one key fact about discrete-time complex exponentials,

in discrete time, not every sinusoid is periodic.

As a matter of fact, if you'll choose an arbitrary omega,

there's a high probability that you will never end up on any of the previous points

in your complex exponential sequence, as you can see in this picture here.

What happens, in fact, is that the complex exponential is periodic in

n only if the frequency is a rational multiple of 2 pi.

So it is of the form of a fraction, a ratio of two integers times 2pi,

it is rather easy to see why it must be so.

So remember, the condition for periodicity for

a discrete-time sequence is the following x[n] = x[n + N],

where N is an integer indicating the period of the sequence.

If we now use complex exponential sequences explicitly,

we have e to the j (omega n + phi) = e to the j (omega (n+N) + phi),

so omega and phi are arbitrary frequencies and phase.

We can now dismantle this equation by splitting the complex exponentials

into products of individual terms, like in this line here.

And if we now simplify the terms that are left and right, we obtain

that the condition of periodicity is simple e to the j omega N = 1.

This poses a condition on omega because this

expression is true only when omega N is a multiple of 2pi,

that's when the complex exponential hits the unit on the complex plane.

So we can rewrite this as omega N equal to an arbitrary multiple of 2 pi, so

let's call that 2M pi, with M an integer again.

And we obtain, finally, the condition on the frequency for the complex exponential,

which is what we said, a rational multiple of 2pi.

Now let's go back to an arbitrary point on the unit circle,

e to the j alpha, it is clear that we can add any multiple of 2pi,

positive or negative, to alpha and land exactly in the same position.

In other words, the same point on the unit circle can

have many names, it could be e to the j alpha, or

e to the j2pi + alpha or say, e to the j6pi + alpha.

Alternatively, it could be e to the j-2pi + alpha and so on and

so forth, so one point, many names, this we call aliasing.

The consequence of aliasing, the consequence of this natural property

of the complex exponential is that in discrete time, it puts a limit on how fast

we can go around the unit circle with the discrete-time signal.

You may have experienced the consequences of this upper limit on the speed that we

can achieve in discrete time when looking, say, at an old western movie.

And you have a stage coach that rolls into the frame of the movie, and

although the stagecoach is moving in one direction.

The wheels appear to be moving alternately backwards and forwards in a sort of

unpredictable pattern, as in the example that we're playing right now.

To see why this happens,

let's go back to the concept of this complex exponential generating machine.

It is rather intuitive to see that the frequency of this machine is restricted

to the interval 0 to 2pi, if we try and use a frequency that is larger than 2 pi,

what happens is we incur automatically to aliasing.

Remember, for instance if, at each step, we're moving by an angle

omega in creating the next sample, well we would have exactly the same

result if we use a step which is omega plus an arbitrary multiple of 2pi.

So whenever we go outside of the zero 2 pi range,

because of the inherent 2 pi periodicity of the complex exponential,

we fall back via a modular operation into the 0 2pi range.

But even within that range, we have to be careful about the backwards and

forwards motions, so let's analyze this in more detail.

Here in the picture you have the first 12 samples of a discrete-time complex

exponential at the frequency 2pi/12.

So this sequence takes 12 samples to go one full revolution around the unit

circle, if we want to go faster, then we have choose a faster frequency.

So, for instance, if we pick omega = 2pi/6,

t will only take six steps to complete a full revolution, let's go even faster.

2p/5 will require five steps, 2pi/4 will require four steps,

2pi/3, three steps, and finally, if we take a frequency of 2pi/2 = pi,

we have a rotation that is not really a rotation.

We're just oscillating between this point and this point, so

we're completing half of the circle at each step, can we go any faster than that?

Well, the answer is not really, if we try to take a frequency that is

bigger than pi, so say omega bigger than pi and less than 2pi,

we will be travelling more than half the circle in one step.

But another way to look at this move if you want, is that the point

has traveled omega -2pi in the clockwise direction instead,

and this angle is a magnitude smaller than this angle.

So in the sense, trying to go faster than pi at each step,

corresponds to going slower in the other direction.

The thing is exacerbated if we take frequency omega = 2pi- alpha,

with alpha small, so now at each step we're going almost a full circle, right?

So the first step will be like so,

we go all the way around minus a little tiny alpha here, and then we continue and

at each step we repeat the same large movement.

As we accumulate these angles, you can see that the apparent motion,

even at the slow speed at which I'm changing the slides,

correspond to a clockwise motion at the speed of alpha.

And remember alpha is very small, so

that's really what's happening to the wheels of the stagecoach,

they're moving too fast with respect to the frame rate of the film camera.

To illustrate, and using a more dramatic detail, here's a video obtained by

artificially rotating the picture of a bicycle wheel with four spokes.

So this wheel has a four-fold symmetry, and the aliasing angles will alternate

faster than if we had a single point rotating around the unit's circle.

As the angular velocity increases, and the angular velocity is displayed in

degrees per frame in the top left corner of the video.

We can see that the motion alternates between a forward motion to a backwards

motion, and then a sense of stationarity as the angle is around 45 degrees.

And then forward motion again and so on and so forth, but

if we look at the hub of the wheel, which is not perfectly symmetric in the picture.

Then we can see that the actual motion of the frames is always forward at

an increasing angular speed.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.