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

339 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 5: Sampling and Quantization

- Paolo PrandoniLecturer

School of Computer and Communication Science - Martin VetterliProfessor

School of Computer and Communication Sciences

The interpolation question is very elementary.

You have a sequence, x[n], you want to generate x(t),

and you would like to fill the gaps between the samples.

How should we best do this?

So here is an example.

We have five blue samples, indicated by the sticks, they are equally

spaced in time, and we fit the red curve smoothly through the samples.

Note that it is exact as the sample values, and is smooth in between.

So the requirements are we have to decide on ts,

the spacing between the samples in the continuous time function.

We have to make sure that x at the location n times

ts is equal to the sample values xn.

And we would like in general that xt is a smooth function.

We'll see more precisely what we mean by a smooth function.

Let us discuss the issue of smoothness in physical terms.

Assume X of T shows the location of an object.

If there is a jump, it would me there is infinite speed.

If there is a second order of discontinuity,

it means it would be infinite acceleration.

In general, we would like interpolators to be infinitely differentiable, so

they make also physical sense.

A natural solution for this is polynomial interpolation.

So how to do polynomial interpolation.

Well if you have N points,

there is a polynomial of degree N minus one that can go through these N points.

For example, give me two points.

I can draw straight line.

Give me three points I can draw a parabola, et cetera.

So we have P of T which is an N minus one-th degree polynomial, and

we simply fit the polynomial to the sample.

So p of zero has to be equal to x zero.

P of Ts x[1] etcetera, up to P of N minus one times Ts.

Introduce an interval symmetric about the origin so

call it In from minus capital N to N.

Set Ts equal to one.

We can always.

So we scale the axis to achieve an ETS.

And then we want to fit p(-N) to the sample x[-N],

etc., p(0) to the sample x[0], up to p(N) to the sample x[N].

The natural solution to this interpolation problem is given by

Lagrange interpolation.

Take PN the space of degree-2N polynomials over the integral IN.

The basis for PN is a family of 2N + 1 Lagrange polynomials,

given by this formula.

Let us just do a small example, namely N is equal to one.

So let's write the formula again,

L N of T is this product with K going from minus to capitol N.

Pick capital N is equal to 1.

So we have three polynomials, L minus one, L0, and L1.

Let us calculate L0 of 1.

So L0 of 1 of t is this product

where k cannot be equal to 0 of t-k over -k.

So this is equal to t plus 1 times t minus 1 divided by minus 1.

So that's 1 minus t squared.

We can plot this, and sure enough, it's a parabola, and it is equal to 1.

That's the origin.

And equal to Z what minus 1, and also Z what plus 1.

For completeness, you can calculate L1 of 1, it's t squared plus t over 2,

and l minus 1 of 1, which is equal to t square, minus t, over 2.

Let's plot the next bigger example.

This is capital N is equal to 2, so we have 5 Lagrange interpolators.

So first one is L minus 2,2 of T, it is 1 at minus 2,0 at minus 1 zero 1 and 2.

The second one in blue is L minus 1.

It's equal to 1 at minus 1, and zero at the other integers.

L zero of two which is symmetric around the origin where x = 1 and one of two

which is the plot curve, and finally L two of two, which is the light blue curve.

The important thing is that these polynomials are one at their index n and

they are zero at the other integers.

Each one has exactly this characteristic.

So now, we have a formula.

P(t) can be written as a linear combination, and

going from minus n to N of x(m), the samples and

the respective Lagrange interpolator of index n.

Let us summarize what has been achieved, so

Lagrange interpolation is what we were looking for.

It's a unique solution to the interpolation problem.

It satisfies p(n) = x[n] because of the interpolation property

of the Lagrange polynomial.

Let us return to our problem of interpolating five samples between

minus 2 and plus 2.

We can now do this by writing the solution as a linear combination of

Lagrange interpolators weighted by the sample values.

Let's do this now.

First Lagrange interpolator centered at minus 2.

Then at minus 1 at the origin at 1.

At plus 2.

Summed together we find the red curve that we had seen before.

The key property of polynomial interpolation is that it's maximally

smooth, it can take infinitely many derivatives.

The drawback is that the interpolation bricks each piece we add depends on N,

and each piece actually looks different for

example in the Lagrange interpolation case.

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