# Prove that, in DFT, Upsampling in time domain is equal to replication in frequency domain

Given:

$$x[n]$$ is an $$N$$-point sequence whose DFT is $$X[k]$$

$$x[n]\xrightarrow{\mathcal{DFT}} X[k]$$

then,

Prove that: DFT of the same sequence after insertion of $$(M-1)$$ zeroes between successive samples is $$M$$ times repetition of DFT of original Sequence .

\begin{aligned}x\left[\frac{n}{M}\right]\xrightarrow{\mathcal{DFT}}\{&X,0,0,\dots,0,\\&X,0,0,\dots,0,\\&X,0,0,\dots,0,\\&\vdots\\&X[N-2],0,0,\dots,0,\\&X[N-1],0,0,\dots,0 \}\end{aligned}

My attempt:

$$\mathcal{DFT} \left\{x\left[\frac{n}{M}\right] \right\}=\displaystyle\sum_{n=0}^{n=MN-1}x\left[\dfrac{n}{M}\right]W_{N}^{nk}$$

replacing $$n\to{ nM}$$

$$\text{LHS}=\displaystyle\sum_{n=0}^{n=N-\frac{1}{M}}x[n]W_{N}^{Mnk}\neq \big(X[k]\big)^M$$

I'm doing some mistake that is why i'm not getting $$\text{RHS}=\big(X[k]\big)^M$$.

Can anyone help me in proving this property?

Note:

$$x[n]$$ have period $$N$$ so, $$x[\frac{n}{M}]$$ will be having period $$MN$$.

$$W_{N}$$ is twiddle factor $$=N$$ th root of unity$$=\exp\left(-j\tfrac{2\pi}{N}\right)$$

• some of your notation is strange. $[n/M]$ is not an integer so you shouldn't be using this as a subscript – Hilmar Aug 23 '19 at 19:58
• @Hilmar:suppose $x[n]=[a,b,c,d]$ then,$x[n/3]=[a,0,0,b,0,0,c,0,0,d]$ ,$x[n/4]=[a,0,0,0,b,0,0,0,c,0,0,0,d]$..and similarly for $x[n/M]$. now i'm trying to prove say DFT of $x[n/4]$ is equal to DFT of $x[n]$ repeated 4 times .please help – user33321 Aug 23 '19 at 20:30
• Sampling in the time domain causes replication in the frequency domain, not interpolation. interpolation is sorta the opposite operation of sampling. interpolation causes the repeated replicas to disappear. interpolation in the time domain reverses or undoes replication in the frequency domain. it doesn't cause it. – robert bristow-johnson Aug 23 '19 at 21:53
• I don't know how to deal with an upper limit to your summation of $n=N-\frac1M$. that doesn't make sense to me. – robert bristow-johnson Aug 23 '19 at 22:17

We start with $$X[k] = \sum_{n=0}^{N-1} x[n] \cdot W_{N}^{nk}$$ Let's define a new sequence of $$y[r]$$ of length $$R=M \cdot N$$, where $$R, M, N \in \mathbb{Z} > 0$$

$$y[r] = \begin{cases} y[n \cdot M] = x[n] \qquad & r = n \cdot M \\ \\ 0 \qquad & \text{otherwise} \\ \end{cases}$$

Transform it $$Y[k] = \sum_{r=0}^{R-1} y[r] \cdot W_{R}^{rk}$$

Now most of the samples of $$y[r]$$ are zero, so we can eliminate them from the sum

$$Y[k] = \sum_{r=0}^{R-1} y[r] \cdot W_{R}^{rk} = \sum_{n=0}^{N-1} y[n \cdot M] \cdot W_{R}^{nMk} = \sum_{n=0}^{N-1} x[n] \cdot W_{R}^{nMk}$$

Next we take a look at the twiddle factor $$W_{R}^{nMk} = e^{-j\frac{2 \pi nMk}{R}} = e^{-j\frac{2 \pi nk}{N}} = W_{N}^{nk}$$ and put this back into the Fourier Transform

$$Y[k] = \sum_{n=0}^{N-1} x[n] \cdot W_{N}^{nk}$$

That's pretty much it. Comparing to the first equation we see directly that $$Y[k]=X[k]$$

We also see that $$Y[k]$$ is periodic in $$N$$ and not just in $$R$$. Since both $$x[n]$$ and $$W_{N}^{nk}$$ are periodic in $$N$$, so must be $$Y[k]$$.

You can run a thought experiment. When you sample a continuous time signal at a certain sampling frequency, the sampling creates infinite copies of the spectrum centered at multiples of sampling frequency. Now when you insert N-1 number of zeroes between samples, you have basically stretched the time axis by a factor of N. Because $$m^{th}$$ sample will now appear at $$(Nm)^{th}$$ sample. And so the frequency axis will get shrunk by the same factor N. And so, N copies of the original spectrum will get pulled inside $$[-\pi, \pi]$$. That's why you see N copies of the spectrum.

And now when you pass this upsampled sequence through an LPF to filter out only baseband copy of the original sequence, you are basically filling sinc interpolated values at those inserted zeros.