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

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

- Paolo PrandoniLecturer

School of Computer and Communication Science - Martin VetterliProfessor

School of Computer and Communication Sciences

In a nutshell,

multirate signal processing addresses the question of how to change the underline

sampling rate of discrete-time sequence entirely in the discrete-time domain.

Consider the following scenario.

You have an input signal x(t) and you convert this into a discrete-time sequence

via a sampler, at a sampling rate T1.

And we will denote the discrete-time sequence as xT1(n)

to express the dependence on the sampling period.

Now, if you change the sampling period, you will get a different type of sequence.

So here's the question.

Given a sample sequence xT1(n),

can we build a discrete time machine that produces another sequence,

let's call it xT2(n)?

Once we know the relationship between T1 and T2.

And in multirate signal processing we will address two scenarios.

The first is when T1 is a multiple of T2.

And the second one is when T2 is a multiple of T1 where N and

M are integers.

In the first case, the second sequence will be faster than the first one, so

it will increase the number of samples per second.

And in the second case, we will have to reduce the number of samples per second.

But in reality the actual physical values of T1 and T2 are immaterial,

all that matters is their relationship.

In the first case, as we will see,

we will simply output capital N points in the new sequence for each input sample.

And in the second case we will discard capital M minus one input points for

every output sample.

Let's start with the easier case in which we increase the number samples.

This is called up sampling and we can create an up sample sequence from any

discrete time sequence simply by building a sequence where we output one sample

of the original sequence followed by capital N minus 1 new samples.

What do we put in this new samples?

Well, we don't know yet.

So for now, let's just put zeroes.

The upsample sequence indicated by xNU(n) where capital N here

is the upsampling factor will be equal to a sample from your regional sequence,

when the index is a multiple of N, and 0 otherwise.

Graphically we indicate the upsampling operator with a circle

containing the upsampling factor, and an arrow pointing up.

Let's look at an example.

Assume this is the original sequence.

Of course, you know it's an infinite sequence so

it continues outside of the plot.

To build an upsample sequence by a factor of four, we take each sample in

turn the original sequence we output it, and we follow it by three zeroes.

The result is something like this.

So you see here the indexing has changed.

The values remain the same but their indexes are now different.

This is zero, one, two, three, four, five, six, seven, eight, and so on, so forth.

So all multiples of four are points that belong to the original sequence,

all the others are zeroes.

What is a spectral representation of an upsample sequence?

This is very easy to find if we use the z transform as a first step.

So we write the z transform of the upsample sequence and

this is the standard summation that defines the z transform.

But now we know that in the sum only one term out of N will be none zero.

So we can simplify the sum here, by using a change of variable.

And by eliminating all the zero terms in this sum, we end up with this summation

for k that goes to minus infinity to infinity of x[k].

So samples of the original sequence times z to the power of -Nk.

So this is the z transform of the original sequence,

computed in z to the power of capital N.

If we restrict the z transform to the unit circle to find the Fourier transform, we

have the spectrum of the upsample sequence is simply the spectrum of the original

sequence where we have contracted the frequency axis by a factor of capital N.

So what used to be, say the minus pi pi interval will become

the minus N pi to N pi.

We can see this graphically.

Here in the top plot, we've showed the spectrum of the original sequence.

Now in multirate signal processing,

it's fundamental to remember that discrete time spectra are two pi periodic.

To make that more explicit, we can show the same spectrum over a larger interval.

And so here we have the classic two biperiodic pattern for

this [INAUDIBLE] spectrum.

As I said, the interval, -5pi will now be contracted so

that it will include the -2pi, 2pi interval.

And this will be mapped to the minus pi, pi interval in the upsample sequence,

so the result in spectrum for the upsample sequence will be this one.

Let's change the upsampling factor to get a better feel for

what upsampling does in the frequency domain.

Same pattern here, original spectrum.

Original spectrum showed over a larger interval.

And now we're upsampling by three, so

so it will be this interval here that will be mapped onto the minus pi,

pi interval in the upsampled spectrum, and it will look like so.

In general, for an upsampling factor of capital N,

you will have capital N copies of the original spectrum pooled in the minus pi,

pi interval for the new upsample sequence.

If N is odd as in this case, you will have three neat copies like so.

And if N is even like in the previous example,

you will have one full copy plus one half here and one half there.

Let's look at another example with a slightly different

spectral shape that is not full band, and an upsampling factor of four.

Again the periodicity made explicit looks like so.

And when we upsample by four, we will take the -4pi to 4pi interval and

map it to -pi, pi to obtain this spectrum here.

Again, sampling factor is even so

you'll have three copies of the spectrum, plus one half here and one half here for

a total of four copies brought into minus pi, pi interval.

Okay, so we have created an upsampling machine that fulfills the basic

requirement of output in capital N samples for every input sample.

But, the result, we don't really like for a couple of reasons.

In the time domain the signal doesn't look natural.

You have one nonzero sample then followed by a run or zero samples.

This is not a signal you would find in nature.

And similarly in the frequency domain we have this extra copies of the spectrum

that are brought in the band and we don't like that.

That's extra content that we want to eliminate.

Now the cool thing is that the two problems are exactly one in the same.

To understand why that is so, let's look again at the upsampling problem.

Let's take the same signal as before, but

now we look at it over a larger interval so we can see that the signal is smooth.

Now we upsample it, say, by a factor of four.

And let's focus on the smaller region of this smooth signal.

So we start with this, we upsample, and we introduce the zeros.

Now the signal is no longer smooth,

because it jumps from non-zero to zero every four samples.

How can we make it smoother?

Well, suppose that instead of inserting zeros

what we do is repeat the previous non-zero samples three times.

The resulting signal looks like so.

So we repeat each sample four times, and

we get a signal that although still a little bit blocky,

certainly looks better than jumping back to zero every four samples.

How can we obtain this?

Well, it's a simple case of zero order hold interpolation

done in the discrete time domain.

We take our signal, we do the standard upsampling where we insert zeros, and

then we convolve this with the impulse response of the discrete time,

zero-order hold, that looks exactly like so.

Four 1s from 0 to 3.

Of course, for a generic of sampling factor of capital N,

we will use a zero-order interpolator whose impulse response is equal to 1 for

n that goes from 0 to capital N- 1.

In the frequency domain,

the response of this filter is well known, we've studied before.

And for capital N = 4, shown in this picture here.

So you have a low pass characteristic that, as you can already foresee,

will help us eliminate the copies of the spectrum that are brought in,

the -pi/pi interval.

We will see that in a second, but

first, let's consider what happens if we want an even smoother upsample signal.

As per usual, the next step in smoothness is moving

from the zero order hold interpolator to the first order interpolator, which,

as you remember, corresponds to connecting the dots in the output signal.

In discrete time, this is exactly the same thing.

So we will get a signal that is like this.

Although it appears very, very smooth, if you look closely,

you will see that the intermediate samples in the upsample sequence are simply

a linear interpolation between the two neighboring samples.

We know how to obtain this, it's simply the convolution of

the standard upsample sequence where we insert zeros.

With a first order interpolator whose

impulse in discrete time is the familiar triangular shape.

So in this case for n = 4, it will be a triangle that goes from -3 to +3, like so.

We also remember that to obtain this triangular characteristic, all we need to

do is to convolve two zero-order hold impulse responses of half the length.

This helps us find the frequency response of the first-order interpolator in

discrete time, which in magnitude is the square magnitude of a zero-order hold.

So what you have is the same general shape of the zero-order hold,

but with the steeper low pass characteristic due to the fact

that the frequency response is raised to the second power.

Let's look at what happens in the frequency domain.

Remember, this is the spectrum of the original sequence,

shown with explicit periodicity in the second panel.

And this is the spectrum of the standard upsample sequence where we introduce 0s.

Now, when we convolve with the discrete time interpolator,

we are multiplying the spectrum of the upsample sequence

with the frequency response of the interpolator.

In the case of the zero-order hold, we have a bland low-pass

characteristic that will make the signal smoother in the time domain.

And will almost remove the copies of the spectrum in the frequency domain.

This is probably not entirely acceptable, so

we move on to the first order interpolator in most cases.

And we will have a higher rejection of the high frequency component.

It is exactly the same problem as interpolation in the continuous time

domain, except that here, we're working entirely in the discrete time domain.

In the limit, if we would like to have a perfect rejection of the extra copies

of the spectrum that are brought in the -pi pi interval,

we should use an ideal low pass with the cut-off frequency of pi/N.

This means that the ideal digital interpolator is composed of two elements,

an upsampler by capital N where we insert zeros in the original sequence.

And an ideal low pass filter with an impulse response that is a sinc.

Of course, we cannot achieve this in practice,

but what we can do is use as good as an approximation

as possible to this ideal low pass with cutoff frequency pi/N.

And this is our digital interpolator that will increase the underlying

sampling frequency of a discrete time sequence entirely in discrete time domain.

This is a discrete time filter.

So upsampling increases the implicit sampling rate of a signal

by creating new output samples for each input sample.

The converse operation is called downsampling, and it reduces the implicit

sampling rate by keeping only one output sample out of capital N input samples.

Or alternatively, by discarding n- 1 input samples every n input samples.

The fact that we're discarding samples should raise all sorts of alarms.

And indeed, we have to be careful when we use downsampling, because downsampling is

affected by a discrete time version of the phenomenon, as we will see shortly.

Upsampling, by contrast, is a harmless operation because it only adds samples,

which can be removed later on, if necessary.

Formally, a downsample sequence is obtain simply by retaining

one sample out of capital N samples.

And the symbol for the downsampling operator is a circle with

the downsampling factor and an arrow pointing downwards.

Graphically, if you have a signal like so and we downsample it by 4,

what we do is we retain only one sample out of 4.

So the orange samples here will be the survivors and

the resulting signal will be the following.

As you can see, there is a significant loss of information.

And we have to make sure that this loss of information is not irreversible.

The spectral representation of a downsample sequence

is a little bit trickier to derive than in the case of upsampling.

Like before, we start with the z transform of the downsample sequence and

the expression for the z transform is now the sum for k that goes from minus

infinity to plus infinity, of the surviving sample, so x[kN]z to the -k.

This expression is not really easy to take apart as is, so

here comes the first trick.

Consider an auxiliary z transform, A(z),

which is the sum for all values of k of x[kN] like before.

But now you multiple this by z to the -kN.

If we knew the z transform A(z), then the z transform of the downsample

sequence would be just A computed in z, to the power of 1/N.

And then when we bring this to the unit circle like before, we would have

an expansion of the frequency axis by a factor of N before we had the contraction.

So now the question is, how do we find the value of A(z)?

So here comes the second trick.

A(z), as we saw, is the sum of x[kN]z to the -kN.

So you see that all the indices here are multiplied by capital N.

So we're hopping over multiples of capital N.

We can rewrite this as the z transform of the original

sequence x[k] times an auxiliary sequence xi[k],

that is used to kill all terms in the sum where k is not a multiple of N.

So xi[n] is an indicator sequence that only selects

samples whose index is a multiple of capital N.

As an example, here's the graphical representation of xi[n] for capital N = 4.

You will have one sample that is equal to one followed by three zero samples, and

so on and so forth.

Now here comes the third trick.

We can remember the formula for the orthogonality of the roots of unity, and

we can express xi[n] as the sum for

m that goes from 0 to N- 1 of e to the j 2 pi over capital N times m,

times n, normalized by capital N.

With this, we're ready to compute the expression for A(z).

Because now A(z) is the standard z transform of the product between xi[n] and

x[n].

So we replace in the expression for the z transform the value of xi[n]

using the roots of unity, and we have a double summation.

The external summation is over this phase terms.

And the z transform will be computed for the original sequence.

And now we collect the exponents and we bring this phase term here together with z

to obtain 1 over n that multiplies the sum Of capital N

copies of the original z transform of the input sequence,

computed for different phase offsets of z, okay?

So we're taking z, we're multiplying this by pure phase factor and

computing z transform and then summing all these copies together.

Okay, so A(z) was just an intermediate quantity

that we needed to compute the actual z transform of the down sample sequence

as A(z) computed in z to the power of 1/N.

So the expression for the z transform is this one, but

we're more interested in the restriction of the z transform to the unit circle,

because that gives us the spectrum of the down sample sequence.

And the expression for that is the following.

There's 1/N normalization factor in front,

that multiplies the sum of capital N copies of the original spectrum,

where each copy has been shifted by a multiple of 2 pi/N, and

where the frequency axis has been stretched out by a factor of capital N.

So the interval -pi/ N,

pi/N becomes the interval -pi, pi.

Let's look at the graphical example where we're downsampling by 2.

On the top panel, we have the original spectrum of the input sequence.

In the middle panel, we will compute the auxiliary z transform A(z),

restricted to the unit circle.

So remember this will contain two terms,

two shifted copies of the same spectrum, one shifted by 2pi/2x0, so

it will be centered in 0 and this is the original copy.

And then you will have another copy centered in 2pi/2x2, which is equal to pi.

So here's a second copy of the original spectrum shifted by pi.

Note that like before in the second panel we're showing the spectrum with explicit

2pi periodicity.

So we're using a larger support than -pi.

And finally, we have this expansion of the frequency axis, where the -pi/2

to pi/2 interval will be mapped to -pi pi, and so this is the resulting spectrum.

So we have started with a spectrum that was half-bent, and because the spectrum

was half-bent, we had a sufficient gap in the periodic replica of the spectrum

to fit another copy of the spectrum without overlap and without aliasing.

So this downsampling by 2 operation actually does not result in irreversible

loss of information, because we have enough room between the non-zero parts of

the spectrum to fit another copy of the spectrum in there snugly without overlap.

Which actually means that the original sequence had been sampled

at the sampling frequency, which was at least twice the minimum sampling frequency

stipulated by the sampling theorem.

So by downsampling it,

we're bringing it back implicitly to the critical sampling rate.

Let's see what happens when this is not the case.

This is, for instance, a spectrum that goes over to 3pi/4, okay?

So when we build this intermediate quantity A(z) restricted to unit circle,

we have one copy centered in 0, we're still downsampling by 2.

So there will be a second copy now centered in pi,

and of course this will overlap with the previous copy of the spectrum.

The sum of the two will be like so, indicated by the red line,

and then the remapping or the stretching of the frequency axis will result in

a spectrum for the downsample sequence that is like so.

So you see here this part and this part are affected by aliasing.

What we can do in discrete time like we did in continuous time,

is prevent aliasing by first filtering the original signal, so

that its spectral occupancy is small enough so

that there will be no overlap between the copies.

And it's very easy to see that for instance in the case of downsampling by 2,

what we require of the signal is to be badly emitted in discrete time 2pi/2.

So what we can use is an ideal low pass filter with cutoff pi/2.

This will remove, of course, some of the information here, but

in a controlled fashion, so that we're not victims of aliasing, but

simply of a trade off to reduce the sampling right.

With this filtering operation, now the overlap will not occur, and

the copies will sit neatly side by side.

And finally, the resulting spectrum of the downsample sequence will look like so.

In general, to avoid aliasing, we have to filter the input sequence

with a low-pass filter with cutoff frequency pi/N,

where N is the downsampling factor that will follow.

Downsampling and

upsampling change the implicit sampling rate by an integer factor.

But we can combine them so

that the resulting sampling rate change will be an arbitrary fractional number.

The combination always goes in the sense that we first upsample the signal,

which is the operation that does not change the information content

of the original sequence, and then we perform downsampling.

In doing so, we can combine the filters associated to the interpolation for

upsampling.

So if we have an upsampler followed by an interpolating low-pass filter, we

know that this low pass filter will be a low pass with cutoff frequency pi/N, okay?

And then the downsampler will be preceded by an anti-alias filter.

With low-pass cutoff frequency pi/M.

So we can combine these two filters, because they would act as a cascade,

and since they're both low-pass filters, the smallest cutoff frequency will win.

And so we will just use a simple low-pass filter

where the cutoff frequency is the minimum between pi/N and pi/M.

A practical example that requires a Rational Sampling Rate Change

is the conversion format between DVD audio and CD audio.

In compact discs, the nominal sampling frequency is 44.1 kilohertz,

whereas in DVD audio the nominal sampling frequency is 48 kilohertz.

If we take the ratio of these two sampling frequencies and simplify the fraction,

we get a ratio of 160/147.

These are rather large co-prime terms and they are so by design.

The reason is, DVD audio follows the specifications of an earlier standard for

digital audiotapes.

Digital audiotapes were the first consumer device that allowed people to make

perfect digital copies of a medium, so

you could go from tape to tape without loss of quality.

If the sample rate of digital audiotapes had been the same as that of CDs,

people could have made exact digital copies of CDs and

the industry was obviously afraid of this.

So a decision was made to make the sampling frequency of digital audiotapes

close to that of CDs, but sufficiently inconvenient so

that you could not do a direct copy and you could not

use a simple sample rate conversion to move from one standard to the other.

But as we will see in the next module, there are clever ways to circumvent

this limitation and change from CD to DVD sampling

rates without using externally high-rate upsamplers and downsamplers

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