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

Question

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,0,\dots,0,\\&X[1],0,0,\dots,0,\\&X[2],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) $

Answer 1

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.

Answer 2

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]$.