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!
TA's comments: As for the question "What's the effect of zero padding?". I want to point out that the zero padding techniques can only make your frequency spectrum smoother. It cannot increase the resolution of frequency. That means no matter how many zero you pad, the envelop of your frequency spectrum will remain the same. There will not be any new frequency components show up. This implies that given a length L signal, the length L DFT contains enough information to fully reconstruct the original signal.
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.
