Practice Question on "Digital Signal Processing"
Topic: Discrete Fourier Transform
(This problem clarifies how zero-padding a signal changes its DFT.)
Question
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.
- Instructor's comments: While it is true that the length L DFT contains enough information to fully reconstruct the original signal, and thus its DTFT, zero padding does increase the number of samples of the DTFT, and thus the resolution of the sampling of the DTFT. This extra resolution is not adding any more "information" per say (from a mathematical standpoint), but it is changing the position and distance between the samples, thus giving a different approximation (from a visual standpoint) of the DTFT. -pm
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.
