0
$\begingroup$

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) $

$\endgroup$
4
  • $\begingroup$ some of your notation is strange. $[n/M]$ is not an integer so you shouldn't be using this as a subscript $\endgroup$
    – Hilmar
    Aug 23, 2019 at 19:58
  • $\begingroup$ @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 $\endgroup$
    – user33321
    Aug 23, 2019 at 20:30
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 23, 2019 at 21:53
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 23, 2019 at 22:17

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.