Practice Problem
(This problem clarifies how zero-padding a signal changes its DFT.)
let x[n] be a signal with duration N. More precisely, assume that $ x[n]=0 $ for $ n> N-1 $ and for $ n<0 $.
Let y[n] be the zero-padding of x[n] to length M>N:
$ y[n]= \left\{ \begin{array}{ll} x[n], & 0\leq n < N,\\ 0, & N \leq n <M. \end{array} \right. $
Show that the M point DFT of y[n] satisfies
$ Y_M [k] = {\mathcal X} \left( \frac{2 \pi k }{M}\right), \text{ for } k=0,1,\ldots, M-1, $
where $ {\mathcal X} (\omega) $ is the DTFT of x[n].
You will receive feedback from your instructor and TA directly on this page. Other students are welcome to comment/discuss/point out mistakes/ask questions too!
Answer 1
$ {\mathcal X}(\omega)= \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n} $
---------------------------------------------
set $ \omega = \frac{2\pi k}{N} $ and use the fact that $ x[n]=0 $ for $ n> N-1 $ and for $ n<0 $
$ {\mathcal X}(\frac{2\pi k}{N})= \sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{N} n} = X_{N}[k] $ formula(1)
---------------------------------------------
- Why do you need this part? Shouldn't you get an expression for the M point DFT of x[n] instead?
Now we can manipulate the DFT of y[n]
$ \begin{align} Y_{M}[k]&= \sum_{n=0}^{M-1}y[n]e^{-j\frac{2\pi k}{M} n} \\ &= \sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi k}{M} n} \ \ since \ y[n]=0 \ above \ N-1 \\ &= {\mathcal X}(\frac{2\pi k}{M}) \ \ by \ comparing \ to \ formula (1) \end{align} $
Answer 2
By definition of DFT and DTFT:
$ Y_{M}[k] = \sum_{n=0}^{M-1}x[n]e^{-j2\pi\frac{kn}{M}} $
$ {\mathcal X}(\omega)= \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n} $
since x is none zero in [0,N-1],N<M, so x is zero wherever x<0 or x>M-1,
(Note:x[n]=0 when n in[N,M-1], but we still keep it in there for notation)
$ {\mathcal X}(\omega)= \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}= \sum_{n=0}^{M-1}x[n]e^{-j\omega n} $
Plug in $ \omega = \frac{2\pi k}{M} $
$ {\mathcal X}(\frac{2\pi k}{M})= \sum_{n=0}^{M-1}x[n]e^{-j\frac{2\pi k}{M}n} $
Compare to $ Y_{M}[k] = \sum_{n=0}^{M-1}x[n]e^{-j2\pi\frac{kn}{M}} $
one can conclude that
$ Y_{M}[k] = \sum_{n=0}^{M-1}x[n]e^{-j2\pi\frac{kn}{M}} = {\mathcal X}(\frac{2\pi k}{M}) $
Q.E.D.
Yimin.
- Instructor's comment: This proof is very clear. But on the exam, you would not have to write that many details. Perhaps somebody can try to write a shorter proof below? -pm
Answer 3
write it here.
