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

251 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 1 - Basics of Fourier Analysis

- Paolo PrandoniLecturer

School of Computer and Communication Science - Martin VetterliProfessor

School of Computer and Communication Sciences

Okay, so far we have looked at DFT as an analysis tool.

Let's now spend some time thinking about the synthesis properties of the DFT,

how we build the signal starting from DFT coefficients.

And to better understand how the DFT reconstruction formula works,

it's useful to look at the standard sinusoidal generator that works

one the standard frequencies in the Fourier basis.

So here you have a complex exponential with a frequency,

which is a multiple of 2pi over N and with an initial phase 5k.

The way this generator works is by successively generating points on the unit

circle starting at the phase 5k, and proceeding in increments of 2pi over N.

We could draw this concisely with this notation, where here, inside,

you have an index of the Fourier frequency that the generator will produce, and

the input parameters for the generators are, of course, the initial phase, here,

and a gain factor Ak that will lead to Ak times e to the j (2pi over N kn + phi k.

So DFT reconstruction formula can be drawn graphically

like a machine composed of N sinusoidal generators,

each one of which will be initialized with a gain factor and with a phase factor.

All their outputs will be summed together and

this will give us back the original signal.

How do we initialize each one of these blocks?

Well the amplitude will be the amplitude of the corresponding Fourier analysis

coefficient normalized by N.

And the phase will be the phase of the corresponding Fourier analysis

coefficient.

So let's look at an example.

Let's take a simple signal, seven point long signal, that looks like a triangle.

And we perform a Fourier analysis on this vector, and

we get seven Fourier coefficients that we list here in terms of amplitude and phase.

Now we initialize the seven generators with the As and the phis that we found

in the analysis part, and then we turn the crank seven times and

we will sum the outputs together to obtain the original signal.

So here is how it works.

In the first line, we will show the output of each generator in turn,

starting for k = 0, up to k = 6.

And here on the bottom line,

we will show the cumulative sum of the outputs as k proceeds from 0 to 6.

So the first generator is the one for k = 0,

so the frequency is 0, and the output will be simply a constant.

As a matter of fact, the value of this constant will be equal to A0.

And so the cumulative sum now has only one term, so

the output at this point will look like a constant.

For k = 1, we have now a sinusoid that will have a certain initial phase and

a certain amplitude.

And we can see that, as we add this to the previous constant,

here in gray, you see the previous sum and, here, the updated sum for k = 1.

The real part of the signal starts to look a little bit like a triangle.

We also have a significant, non-negligible, imaginary part which will

have to disappear in the end because, remember, we started from a real signal.

So as we proceed for k = 2, we see that the coefficient amplitude is very small,

and so this will be just small adjustments in the sum.

It's very hard to see the difference between this step and previous step.

k = 3 is very similar, small adjustments.

For k = 4, we're going in the counter-clockwise part of the spectrum, so

more adjustments still that will start to bring down the imaginary part to zero.

Here you see another small adjustment, and then finally k = 6,

the last coefficient will completely kill the imaginary part and

give us back exactly the signal we were starting from.

So why do we think about the DFT reconstruction formula as a machine?

Because, in reality, these machines were used in the past, for instance,

to predict the tides.

The tide a periodic phenomenon, and, once you find the modes,

you could actually use the experimental data to predict the evolution of the tide

as a superposition of sinusoidal components.

So this machine,

that was originally invented by Lord Kelvin, is nothing but a mechanical

implementation of the DFT reconstruction machine that we just saw before.

So here's a question.

What happens turn the crank of the machine more than N times?

Well it turns out that the output will become periodic.

In other words, x[n + N] = x[n].

This is actually quite apparent from the structure of the synthesis and

analysis formulas of the DFT.

Let's start from the synthesis formula.

So, in theory, the output index, n, should go from 0 to N- 1.

But you can see that it only appears here, inside this complex exponential.

Now this guy is 2pi periodic, so if you push n over N- 1,

this will simply cycle over, once again,

as if N was looping over the 0 to N- 1 range.

So in the end, you can actually safely take N to be from the set of integers and

the output will be an N-periodic signal in a time domain.

Actually, the same holds for the analysis formula.

You can let the index, k, roam over the entire set of integers.

And since it appears only in this complex exponential here,

again, it will be as if k was looping over the 0 to N- 1 range.

So what happens, really, is that you can consider the sequence of DFT coefficients

as an N-periodic signal in the frequency domain.

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