# Downsampling: Mathematical derivation

The problem I am having is related to sample rate conversion and more precise to sample rate reduction. I have been working on the paper Interpolation and Decimation of Digital Signals Tutorial Review in  and A digital signal processing approach to interpolation in  where the maths make my understanding difficult.

To start with,bellow is defined a new sequence $w'(n)$

$$w'(n)= \begin{cases} w(n), &\text{if}\quad n=0,\pm M, \pm 2M, \ldots \\[2ex] 0, & \text{otherwise} \end{cases}\tag{1}$$

that is non zero only at multiples of $M$ of the old sampled sequence. Then it is stated that a convinient representation of $w'(n)$ is:

$$w'(n)=w(n)\left(\frac{1}{M}\sum^{M-1}_{l\ =\ 0}e^\frac{j2\pi ln}{M}\right)\tag{2}$$

The term in the brackets corresponds to a discrete Fourier series representation of a periodic impulse train with a period of $M$ samples. That in my understanding means that is a multiplication by a $\delta(n)$ in time domain if the term in the brackets refers to the inverse DFT of one $(1)$. If that is the case then shouldn't that be a convolution?

Then an expression for elaborating on the $z$-domain is derived:

$$y(m)=w'(Mm)=w(Mm)$$

Then $\mathcal Z$-transform is utilized after:

\begin{align} Y(z)&=\sum^{+\infty}_{m=-\infty}y(m)z^{-m}\\ &=\sum^{+\infty}_{m=-\infty}w'(Mm)z^{-m}\\ &=\sum^{+\infty}_{m=-\infty}w(m)\left(\frac{1}{M}\sum^{M-1}_{l\ =\ 0}e^\frac{j2\pi lm}{M}\right)z^{-\frac{m}{M}}\\ &=\frac{1}{M}\sum^{M-1}_{l\ =\ 0}\left(\sum^{+\infty}_{m=-\infty}e^\frac{j2\pi lm}{M}z^{-\frac{m}{M}}\right) \end{align}

and we end up here.

• How to conclude the result bellow?
• What are the steps missing?
• Where has $m$ gone?
• And why do we have the exponential as argument of $W$ in equations $(3)$?

$$Y(z)=\frac{1}{M} \sum^{M-1}_{l\ =\ 0} W\left(e^\frac{j2\pi l}{M}z^{\frac{1}{M}}\right)\tag{3}$$

 R.E.Crochiere and L.R.Rabiner,"Interpolation and Decimation of Digital Signals Tutorial Review",Proceedings of the IEEE,vol.69,pp 300-331,March 1981

 R.W.Schafer and L.R.Rabiner,"A digital signal processing approach to interpolation",Proceedings of the IEEE,vol 61,pp 692-702,June 1973

• Does this help? Jun 15 '17 at 11:58
• Thanks very much for the reference,what am after is actually how to get the very last expression derived by the previous of it(at the referenced post).Maybe are some steps missing or an assumption or something obvious that I can not spot. Jun 15 '17 at 13:00

@MattL 's link solves your problem, but it seems you need more help. Then I would like to provide here the same solution in different approach, expecting it might help.

Analysis of a downsampler block (more specifically the decimator or the compressor block) can be done in a number of ways. I prefer the following approach which I find it easier.

The first step of the analysis begins by observing that the structure of the figure a and figure b produce exactly the same outputs $$y[n]$$ given the same inputs $$x[n]$$, hence they are equivalent:

$$\boxed{ x[n] \rightarrow \boxed{\downarrow M} \rightarrow y[n] ~~~~~~,~~~~~~~~~~~ \text{figure-a} }$$

$$\boxed{ x[n] \rightarrow \boxed{ (\times)} \rightarrow v[n] \rightarrow \boxed{\downarrow M} \rightarrow y[n] ~,~ \text{figure-b} \\ ~~~~~~~~~~~~~~~\uparrow w[n] }$$

Where the multiplier $$w[n]$$ is a periodic impulse train with a period of $$M$$ samples, which constitudes a discrete-time counterpart of a continuous-time impulse train sampler.

$$w[n] = \sum_k \delta [n- kM]$$

Such kind of a structural modification, enables an unambiguous mathematical analysis at the expense of an increased number of steps and structural complexity. We shall analyse the figure-b and map its result to figure-a which is what we want indeed.

Then, as the second step, express the periodic impulse train $$w[n]$$, in the figure-b, by its (DFS) discrete-Fourier series sum: $$w[n] = \frac{1}{M} \sum_{k=0}^{M-1} e^{j \frac{ 2\pi k}{M}n }$$ If you cannot see why this is so, consult a DSP textbook for DFS.

In the third step observe that you can treat $$v[n]$$ as an expanded version of $$y[n]$$. Based on this, express Z-transforms of the expanded signal $$v[n]$$ in terms of Z-transform of $$y[n]$$ which is a lot easier to derive than the inverse operation of downsampling; more specifically: $$V(z) = Y(z^M) \longrightarrow Y(z) = V(z^{\frac{1}{M}})$$

In the fourth step, we shall express Z-transform $$V(z)$$ of $$v[n]$$ in terms of Z-transform $$X(z)$$ of $$x[n]$$, based on the following two properties of Z-transforms: $$\sum_k x_k[n] \longrightarrow \sum_k X_k(z) ~~~ , ~~~ \text{linearity}$$ $$e^{j\omega_0 n} x[n] \longrightarrow X(e^{-j \omega_0} z) ~~~ , ~~~ \text{complex modulation}$$

Then express $$v[n] = x[n] w[n]$$ and apply the above two properties: $$v[n] = x[n]w[n] = x[n] \frac{1}{M} \sum_{k=0}^{M-1} e^{j \frac{ 2\pi k}{M}n } = \frac{1}{M} \sum_{k=0}^{M-1} e^{j \frac{ 2\pi k}{M}n } x[n]$$

$$V(z) = \frac{1}{M} \sum_{k=0}^{M-1} X( e^{-j \frac{ 2\pi k}{M}} z)$$

In the final step, merge the above result with the result of step-3 by replacing $$z$$ with $$e^{j\omega}$$ to convert the result from Z-transform to discrete-time Fourier transform:

$$Y(z) = V(z^{1/M})$$ $$V(z) = \frac{1}{M} \sum_{k=0}^{M-1} X( e^{-j \frac{ 2\pi k}{M}} z)$$ $$Y(z) = \frac{1}{M} \sum_{k=0}^{M-1} X( e^{-j \frac{ 2\pi k}{M}} z^{1/M})$$ $$Y(z) = \frac{1}{M} \sum_{k=0}^{M-1} X( e^{-j \frac{ 2\pi k}{M}} e^{j \omega/M})$$

which is the relation between the discrete time Fourier transforms of the input $$x[n]$$ of a compressor and its output $$y[n] = x[Mn]$$ as: $$Y(e^{j\omega}) = \frac{1}{M} \sum_{k=0}^{M-1} X( e^{j \frac{w- 2\pi k}{M}})$$

Interpretation of the final result is as follows: The discrete time Fourier transform $$Y(e^{j\omega})$$ of the the downsampled signal $$y[n] = x[Mn]$$ is given by the shifted and scaled sum of $$M$$ copies of DTFT $$X(e^{j\omega})$$ of $$x[n]$$ scaled in magnitude by $$1/M$$ and expanded in frequency by $$M$$ and each copy shifted by $$2\pi$$ to the right.

This expansion in frequency $$\omega$$ by M of the DTFT $$X(e^{j\omega})$$ can be pictured as follows: Consider the original input frequency spectrum $$X(e^{j\omega})$$, which is bandlimited to $$\omega = \pi/M$$ for preventing aliasing due to subsequent downsampling. Being a DTFT, by default, It's periodic by $$2\pi$$ having its centers at $$\omega = ... -2\pi, 0 , 2\pi, 4\pi, 6\pi ...$$. Now expanding the frequency axis by M yields a function $$X(e^{j\omega/M})$$ such that it's periodic by $$2 M \pi$$ and it has its centers at $$\omega = ..., -2M\pi, 0 , 2M\pi, 4M\pi, 6M\pi ...$$. This spectrum has complete zeros at those frquencies $$\omega = 2\pi, 4\pi, (M-1)2\pi ...$$, due to frequency axis scaling, and those M copies of these expanded spectrums are added to each other after being shifted by $$2\pi k$$ to the right, for $$k=0,1,2,M-1$$, and therefore filling the gaps in between $$\omega = 0$$ and $$\omega = M2\pi$$ of the spectrum of $$X(e^{j\omega/M})$$, hence having a period of $$2\pi$$, $$Y(e^{j\omega})$$ is now a proper DTFT.

• It was the complex multiplication (scaling property) where I was after...thanks for your time.Can I also ask if you are sure about the second figure?Do we further down sample after we have multiplied by u(n)? Jun 18 '17 at 19:02
• Yes you must downsample. Multiplication by $w[n]$ only selects and retains the samples at $n=Mk$ while setting all other to zero, but the rate of the signal is still at the original rate. That's like a zero filled (stuffed) signal. When you downsample by M, you physically discard the zero valued samples. Jun 18 '17 at 19:11