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.