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 École Polytechnique Fédérale de Lausanne

Processamento Digital de Sinais

283 ratings

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 2 - Advanced Fourier Analysis

- Paolo PrandoniLecturer

School of Computer and Communication Science - Martin VetterliProfessor

School of Computer and Communication Sciences

The situation so far is the following.

The N-point finite length signals we will use a DFT.

For N-point periodic signals, we will use a DFS.

One category is missing, and

that is the category of infinite length non-periodic signals.

We can use the Karplus-Strong algorithm to generate one such signal

simply by putting the gain factor alpha to less than 1.

In this case, we will have an infinite length signal that is non periodic.

Because for every repetition of the endpoint sequence,

the gain factor will decrease.

So the first period will be unaffected, the second period will be scaled by alpha,

the third period will be scaled by alpha squared, and so on and so forth.

So what is a good spectral representation for this signal?

We can start with the DFT, and

we can see what happens when the length of the signal goes towards infinity.

Intuitively the fundamental frequency in CN.

Remember, the fundamental frequency of the Fourier basis in CN is omega = 2pi/N.

As N goes to infinity, omega becomes smaller and smaller.

And the set of frequencies in the 0, 2pi range becomes denser and denser.

In the limit, the set of multiples of the fundamental frequency 2 pi/N will become

so dense that we will try to replace this by a real valued variable omega.

And this real valued variable will spend the 0, 2 pi interval.

So if we replace that in the formulation for the DFT,

we get a sum now over all the points in the signal.

And instead of having multiples of the fundamental frequency we have a real

variable.

Does this make sense, mathematically at least?

So let's try and

give a formal definition of what we call the Discrete-Time Fourier Transform.

A Fourier transform geared at infinite length non periodic signals.

We'll require that our infinite signal is square summable, that means finite energy.

It's a reasonable requirement to prevent summations from blowing up.

We define now a function of a real valued variable omega.

And remember this is the function, not a sequence.

And the definition goes like so, F of omega is the sum for n that goes from

minus infinity to plus infinity of x of n times e to the minus j omega n.

When this value exists, we can actually invert it and

retrieve our sequence values by taking the integral from minus

pi to pi of F of omega, E to the J omega, N and the omega.

And normalizing the integral of 1 over 2pi.

It's easy to verify that this is so.

If you replace F omega inside here by this definition, and

you invoke the fact that x of n is square summable.

Now F of omega is 2 pi periodic.

We can see that because it depends on e to the minus j omega n, and

this animal is 2pi periodic in omega.

To stress the periodicity of the DTFT, instead of writing F of omega for

a sequence x of n, we will write the DTFT as x to the e of j, omega.

So although the free variable is omega,

we will write e to the j omega as the argument of the function.

This will remind us that this is a Fourier transform and that it is 2pi periodic

no matter what happens because the argument of the function is 2pi periodic.

Another difference with respect to DFT is that the DTFT,

we choose the minus pi, pi interval as the representative interval for the transform.

So these are conventions of a historic nature, and

although they are a little bit confusing.

It's particularly unfortunate for instance that the difference between DFT and

DTFT is just a T here.

We will preserve the nomenclature and the conventions in order to be compatible or

congruent with the DSP literature out there.

So let's look at an example of DTFT.

Let's take a simple sequence and exponentially decaying sequence,

we know the sequence from the introduction of this class.

And we know that it is a non periodic infinite support sequence.

When alpha is less than 1, we also know that this sequence is finite energy, so

we can compute the DTFT.

We do that, so we write the formal definition, this is the sum

from minus infinity plus infinity of x of n times e to the minus j omega n.

Here we use the values for the sequence.

The sequence is one sided, there's a unit step here.

So that means that the index of the sum will start in 0.

And for n=0 or larger, the value of xn will be alpha to the power of n.

We can collect the two powers under the same exponent and we can see that this is

simply a geometric series with ratio alpha e to the minus j omega.

And so the result will be in the end 1 over 1 minus alpha e to the minus j omega.

The magnitude of the Fourier transform is easy to compute.

It will be 1 over 1 plus alpha square minus 2 times alpha cosine of omega.

And when we plot this, remember now the commission is that are plotting

frequencies from minus pi to pi rather from 0 to pi.

So the the positive frequencies will be on right hand side of the frequency axis.

The negative frequencies the one that turn clockwise will be on the negative side of

the frequency axis.

The low frequencies will be now centered around 0, and

the high frequencies will be on the extremes of the bound.

With this connection in mind, we can look at the spectrum of the exponential

decay in sequence, and it looks like this for say, alpha equal to 0.9.

So it's a signal that contains energy in the frequency domain, mostly around

the low frequencies of course, because it moves rather slowly to 0.

However, never forget the inherent periodicity of the Fourier transform.

If we expand the frequency axis outside of the minus pi,

pi interval, and we can certainly do that because omega is a real valid variable.

What we find is that the shape of the spectrum repeats

outside with a periodicity of 2pi.

So the fundamental interval is this, but

as we plot outside we get further copies of the spectrum.

Again, fundamental interval, first repetition,

second repetition on the positive axis and same thing on the other side.

So let's go back to the Karplus-Strong algorithm.

Try to generate a non periodic infinite support signal and

then compute it's spectrum according to the new DFT paradigm.

So we start with the same shape as before, for the initial data for

this Karplus-Strong algorithm.

Since we're going to be precise in the derivation of this spectrum,

it is useful at this point to look at the analytical formulation for this shape.

So x of n will be between 0 and 31, is equal to 2n divided by big M

minus 1 minus one where big M in this case is 32.

If we put a decay factor in the Karplus-Strong algorithm equal to 0.9,

you see that the repetitions generated by the Karplus-Strong algorithm

have an exponential decaying envelope.

And we can express the output as alpha to the power of the floor of n divided by

big M that multiplies the periodic signal obtained by putting copies

of the pattern we saw in the previous picture, one after the other.

And all of this is multiplied by the unique step,

because we assume that the signal starts at n equal to 0.

So 0 everywhere here, and

exponentially decaying sawtooth wave for n greater than 0.

Analytically, the Fourier transform of this signal can be computed like so.

Remember the definition, so Y of e to the J omega.

The DTFT of the signal we just showed in the picture is equal to the sum for

n that goes to minus infinity to plus infinity of the value of the signal,

and then times e to minus j omega n.

Just like we did before, we split the sum into two parts.

An outer sum that spans every quote unquote repetition of the basic shape,

although of course, the stand signal is not periodic.

So each repetition will be scaled by a different factor.

And then there are some that goes inside each repetition.

Inside each repetition, we have the values for

the basic pattern and alpha to the basic P.

An exponentially decreasing gain factor that creates the decaying envelope.

We can split the exponent in the complex exponential again as pM

+ n and by doing so we can split the sum into the product of two sum.

The first term is

something that looks like a DTFT, notice that the index is p and

we have alpha to the power of p, that multiplies e to the minus j omega big Mp.

So if it wasn't for this big M here, this would be a Discrete-Time Fourier

transform of the sequence that starts at 0 and goes to infinity.

And whose samples take the value alpha to the power of p.

Namely, this is the DTFT of an exponentially declined sequence except for

this factor here.

We'll see how to take care of this in a second.

The second factor is equal to the DTFT of a signal that is equal to

the basic pattern from 0 to big M-1, and 0 everywhere else.

So we can write this as the product of two DTFTs.

The first one is the DTFT of the exponentially decaying sequence that we

saw before.

And the factor of M in the exponent propagates to the argument of the DTFT.

And simply means we are contracting the frequency axis by a factor of m.

It's just a rescaling of the frequency axis.

The second term we'll compute in just a second.

So let's look back at what the Fourier transform

of the exponential decay looks like.

The fact that there is a factor of m in the exponent

simply implies there is scaling of the frequency axis.

So we're contracting the frequency axis by a factor of big M.

But be careful because this contraction will actually have to take

periodicity into account.

So when M = 1, we have the standard spectrum of the k exponential.

When M = 2,

we are bringing in 2 copies of the spectrum inside the minus pi, pi interval.

So what before was periodic over 2pi now becomes periodic over pi.

And when M = 3, you will have 3 copies of the basic spectrum to

fall into the minus pi, pi interval and so on, and so forth.

This is for instance, the case for M = 12.

Now, on to the second term of the product.

As we said, that was the DTFT of a finite support sequence

that is linear between 0 and big M-1.

The result is a little bit ugly, and a little bit cumbersome to derive.

So we'll leave that as an exercise,

and we'll put some slides in the end detail, how to compute this.

But fundamentally this is the result, and

if you plot the magnitude of this function, you have something like this.

In the figure, you have the magnitude of the DTFT of the 32

point sawtooth period that we saw before, this is no 0 between 0 and 31.

And indeed if you count the local maximum here, there are 32 of them.

To compute the final spectrum, we have to multiply the first term.

Which is remember 32 repetition of the basic spectrum

of a decaying exponential times the spectrum we just computed.

It turns out that these speaks in a of e to the j omega m align with

the local maxima of the spectrum of the first period.

So that the final result looks like this where the peaks of the first term

in the product slim down the lobes of the second term.

So here we have derived the DTFT, namely the spectrum of

an infinite non periodic signal that is not a trivial signal.

Now so far we have treated the DTFT as a formal operator.

And in the next module we will see how the DTFT relates to the concept of

change of basis in an appropriate Hilbert space.

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