# Prove that, in DFT ,interpolation 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]$$.