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

Let's start with periodic sequences.

An N-periodic sequence has only N degrees of freedom, and

DFS captures the situation by providing us with a spectral representation for

the sequence that only has N distinct Fourier coefficients.

We can illustrate these points more in detail with the help of the Karplus Strong

algorithm.

You remember how the Karplus Strong circuit works, you have an input,

you have a delay line of length big-M, and that's an iteration factor alpha.

As the samples go in the circuit, they get pushed out to the output, and

they get pushed also to the delay line.

That will be stored here, and

output at the other end of the delay line after big-M samples,

where they get iterated by a factor alpha and summed to the current input.

If we were to describe this mathematically,

we would have what we call a difference equation that relates the current output

to the past output that has gone through the delay line.

So, an output delay by big-M scaled by the attenuation factor and

sum to the original input.

We can use the circuit to generate the simple periodic signal, and to do that,

we choose an input signal, X, that is nonzero only for n between zero and M.

That means that x(n) is actually a finite support sequence, and

that's why we use the overbar notation.

You will only have big-M nonzero samples, and it will be zero everywhere else.

Then we choose alpha equal to 1, so there will be no attenuation in the loop.

If we input this signal to the Karplus Strong circuit,

we will see that the output consists of a periodic signal, where each period is

constituted of the M nonzero samples of the input finance support signal.

Suppose, for instance, that our finance support signal looks like these,

has a nonzero support of 32 points and

over the support it looks like a straight line, and it's zero everywhere else.

So if we use this as an input to the algorithm, we will get a periodic

repetition of this shape, which overall will look like a sawtooth wave.

If we take the DFT of this signal considered as a 32 point

finite length signal, The DFT will look like this.

Computing the exact value of the DFT coefficients is left as an exercise.

Just note, for instance, that the coefficient is 0.

Is 0 because the signal is actually centered around 0 so it's average is 0.

What happens then if we take the DFT of two periods?

So we consider the first 64 points that came out of the carplestrom algorithm and

we take the DFT of this.

Well, if we go through the math algorithm and we put this into analytical package,

we will see that shape of the DFT coefficient, the envelope, so to speak,

is the same As the one for just the first 32 points.

However for every DFT coefficient there is an extra DFT coefficient with value 0.

In other words, the DFT coefficients have been with 0 valued coefficients.

To get an intuition as to why it is so, let's go back to the definition of DFT.

Each DFT coefficient will be the inner product between the appropriate

basis vector and the Fourier basis for c 64.

And this signal that we see here.

So let's see graphically how these inner products are computed.

Let's start with the first basis vector.

We will show here in blue just the Ideal shape of this basis vector.

We don't really care about the real and

imaginary part because we're just interested in the structure.

The first vector is just the constant one.

And the result of the inner product will be the non-normalized average

of this signal in red.

We know the average to be zero, the same holds for two periods.

So the first coefficient is zero, for k =1 we have the first basis vector and

this will be a sinusoid that will spend a full period over 64 points.

What that means is that the first 32 points will be multiplied by a shape

that is exactly the inverse Of the shape for the next 32 points.

And so this subsum of the inner product plus this will get 0.

For k = 2, on the other hand,

the Fourier vector will span 2 periods over the space of 64 points.

And so here we simply have Twice the same thing,

this half of the inner product will be equal to the second half and

the DFT coefficient will be twice the original DFT coefficient.

K equals to three we have another situation of anti symmetry

between the first part of the fora vector and the second part.

And so these two parts will cancel each other out and we will see that in general.

All odd inde coefficients will b zero for these wo periods seen so

we can prove this for a number between the number of periods,

suppose y of n is finite length signal that is composed of l.

Repetitions of the same big M points.

So we said that over bar X of n is a finite support signal

that is zero everywhere except in a portion here.

So we take this portion, this is M points.

And we build y of n by putting

L of this pieces together.

So this would be L of it.

Before you transform y[n] is simply given by the sum for

that goes from zero to LM-1.

LM being the length of this signal now.

Of y of n times e to the minus j 2 pi over LM times n times k.

And k ranges form zero to LM minus 1.

So this is standard stuff.

The only difference is that the length of our signal is LM.

We can split this sum in the following way.

We have an outside sum where we span the number of periods and

an inner sum where we go through the points in the period.

And so here we simply replace k with n

+ pM So k was ranging over the entire signal.

Now we split this into period plus index inside the period.

We can do the same inside the complex exponential, and so then we can split

the complex exponential and we see that The inner sum is this one here,

and this term depends only on p, so we can bring it forward and have

a product of two sums where we have this term here that ranges over the p index,

and this term here that ranges over the n index, and the two are independent.

Now, this guy here, we've seen before.

This is exactly the same formula that we used to prove the orthogonality

on the DFT basis.

And so we know that this sum will be equal to big L

if k is a multiple of L Or zero otherwise.

So with this knowledge, we can plug this back into the formula for the transform

of L periods and find out that the coefficient will be equal to L times

the original coefficient that you have computed for the final support signal.

If k is a multiple of l, and 0 otherwise.

So, given the DFT of L periods,

you will have only one nonzero DFT coefficient out of L, and

this will be equal to L times the original DFT coefficient.

Well this was a long way to show that once again, all the spectral information for

a periodic signal Is contained in the DFT of a single period.

And that's why for periodic signal, in the end, we use a DFS.

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