Homework 4, ECE438, Fall 2011, Prof. Boutin

Question 1

a) For $ k=0,1,...,N-1 $

$ \begin{align} X_N(k) &= \sum_{k=0}^{N-1}x[n]e^{-\frac{j2\pi nk}{N}} \\ &= x[0]e^{-\frac{j2\pi 0\cdot k}{N}} \\ &= 1 \end{align} $

b) Using Euler Formula, we have

$ \begin{align} x[n] &= e^{\frac{j\pi n}{3}}(\frac{ e^{\frac{j\pi n}{6}} + e^{-\frac{j\pi n}{6}} }{2}) \\ &= \frac{1}{2}e^{\frac{j\pi n}{2}} + \frac{1}{2}e^{\frac{j\pi n}{6}} \end{align} $

Observing that $ x[n] $ has fundamental period $ N=12 $. Using IDFT, we have

$ \begin{align} x[n] &= \frac{1}{N}\sum_{n=0}^{N-1}e^{\frac{j2\pi nk}{N}} \\ \frac{1}{2}e^{\frac{j\pi n}{2}} + \frac{1}{2}e^{\frac{j\pi n}{6}} &= \frac{1}{12}\sum_{n=0}^{11}e^{\frac{j2\pi nk}{12}} \end{align} $

By comparison, we know for $ k=0,1,...,11 $

$ X_{12}[k] = \left\{ \begin{array}{ll} 6, & k=1,3 \\ 0, & otherwise. \end{array} \right. $

c)

$ x[n]=(\frac{1}{\sqrt 2} + j\frac{1}{\sqrt 2})^n = (e^{\frac{j\pi}{4}})^n $

Then $ x[n] $ has fundamental period $ N=8 $. Using IDFT, we have

$ \begin{align} x[n] &= \frac{1}{N}\sum_{n=0}^{N-1}e^{\frac{j2\pi nk}{N}} \\ e^{\frac{j\pi n}{4}} &= \frac{1}{8}\sum_{n=0}^{7}e^{\frac{j2\pi nk}{8}} \end{align} $

By comparison, we know for $ k=0,1,...,7 $

$ X_{8}[k] = \left\{ \begin{array}{ll} 8, & k=1 \\ 0, & otherwise. \end{array} \right. $

Question 2

Observing that $ X(k) $ has a fundamental period $ N=4 $

$ \begin{align} x[n] &= \frac{1}{N}\sum_{k=0}^{N-1}(e^{j \pi k }+e^{-j \frac{\pi}{2} k})e^{\frac{j2\pi nk}{N}} \\ &= \frac{1}{4}\sum_{k=0}^{3}(e^{\frac{j2\pi (n+2)k}{4}} + e^{\frac{j2\pi (n-1)k}{4}}) \\ &= \frac{1}{4}\sum_{k=0}^{3}(e^{\frac{j2\pi (n+2)k}{4}-j2\pi k} + e^{\frac{j2\pi (n-1)k}{4}}) \\ &= \frac{1}{4}\sum_{k=0}^{3}(e^{\frac{j2\pi (n-2)k}{4}} + e^{\frac{j2\pi (n-1)k}{4}}) \\ \end{align} $

when $ n\neq 1 \text{ or } 2 $, using geometric series summation formula we have

$ x[n]=\frac{1}{4}( \frac{1-e^{j2\pi (n-2)}}{1-e^{\frac{j2\pi (n-2)}{4}}} + \frac{1-e^{j2\pi (n-1)}}{1-e^{\frac{j2\pi (n-1)}{4}}} ) = 0 $

when $ n=1 \text{ or } 2 $

$ x[n]=\sum_{k=0}^{3}1=4 $

$ x[n] $ will be periodic with 4.

NOTE: In general, $ X(k) $ does not need to have a length equal to the fundamental period. Suppose N is an arbitrary number, we can still derive the IDFT using argument that is similar to the one described above.

Question 3

Suppose the length of finite duration signal $ x[n] $ is $ M $. The number of points of its DFT is $ N $.

Using IDFT we have

$ x'[n]=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{\frac{j2\pi nk}{N}} $

Noticing that $ x'[n]=x'[n+N] $, so the $ x'[n] $ obtained by IDFT is periodic with $ N $.

We can reconstruct DTFT by substituting $ x[n] $ by $ x'[n] $ as long as $ x[n]=x'[n] $ for $ n=0,1,...,M-1 $. i.e.

$ \begin{align} X(e^{j\omega}) &= \sum_{n=0}^{M-1}x[n]e^{-j\omega n} \\ &= \sum_{n=0}^{M-1}x'[n]e^{-j\omega n} \\ &= \sum_{n=0}^{M-1}\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{\frac{j2\pi nk}{N}}e^{-j\omega n} \end{align} $

Since $ x'[n] $ is periodic with $ N $, we must guarantee that $ N\ge M $ in order to fully reconstruct DTFT using DFT.

Question 4

Time Shifting property of the DFT:

Let $ X(k) $ be the N-pt DFT of $ x[n] $, $ n_0 $ be some constant.

Then $ X[k]e^{-\frac{j2\pi n_0 k}{N}} $ is the DFT of $ x[n-n_0] $.

Proof: Compute $ x[n-n_0] $ using IDFT.

$ \begin{align} x[n-n_0] &= \sum_{k=0}^{N-1}X(k)e^{\frac{j2\pi (n-n_0)k}{N}} \\ &= \sum_{k=0}^{N-1}X(k)e^{-\frac{j2\pi n_0 k}{N}}e^{\frac{j2\pi nk}{N}} \\ \end{align} $

Therefore, $ X(k)e^{-\frac{j2\pi n_0 k}{N}} $ is the DFT of $ x[n-n_0] $.

Back to Homework 4

Back to ECE 438 Fall 2011