Line 19: Line 19:
 
</math>  
 
</math>  
  
 +
 +
<span style="color:red"> This is the long way. Do not do this!!! </span>
 
The period of the input is N, so we will calculate the N-point DFT:
 
The period of the input is N, so we will calculate the N-point DFT:
  
Line 29: Line 31:
 
</math>
 
</math>
  
 +
<span style="color:red"> This is the short way: write your signal as a sum of complex exponentials, and then compare with IDFT formula to extract the DFT coefficients.</span>
 +
 +
 +
<math>
 +
\begin{align}
 +
x[n] &=s_N[n] \text{remember, the one we defined when looking at up sampling in the frequency domain? } \\
 +
&=  \\
 +
&=
 +
\end{align}
 +
</math>
  
 
b) <math>x[n]= e^{j \frac{2}{5} \pi n}</math>
 
b) <math>x[n]= e^{j \frac{2}{5} \pi n}</math>

Revision as of 11:39, 14 October 2015


Homework 6 Solution, ECE438, Fall 2015, Prof. Boutin

Questions 1

Compute the DFT of the following signals x[n] (if possible). How does your answer relate to the Fourier series coefficients of x[n]?

a) $ x[n] = \left\{ \begin{array}{ll} 1, & n \text{ multiple of } N\\ 0, & \text{ else}. \end{array} \right. $


This is the long way. Do not do this!!! The period of the input is N, so we will calculate the N-point DFT:

$ \begin{align} X_n[k]&=\sum_{n=0}^{N-1} x[n] e^{-j2\pi kn /N} \\ &= 1e^{-j2\pi k 0 /N} + 0e^{-j2\pi k1 /N} + \ldots + 0e^{-j2\pi k(N-1) /N} \\ &= 1 \text{ for all } k \end{align} $

This is the short way: write your signal as a sum of complex exponentials, and then compare with IDFT formula to extract the DFT coefficients.


$ \begin{align} x[n] &=s_N[n] \text{remember, the one we defined when looking at up sampling in the frequency domain? } \\ &= \\ &= \end{align} $

b) $ x[n]= e^{j \frac{2}{5} \pi n} $

Notice that the period is 5, so we will calculate the 5-point DFT. Beginning with the inverse-DFT:

$ \begin{align} x[n]&=\frac{1}{5} \sum_{k=0}^{4} X_5[k] e^{j2\pi kn/5} \\ &= \frac{1}{5} \left ( X_5[0]e^{j2\pi n0/5} + X_5[1]e^{j2\pi n1/5} + X_5[2]e^{j2\pi n2/5} + X_5[3]e^{j2\pi n3/5} + X_5[4]e^{j2\pi n4/5} \right ) \\ &= e^{j2\pi n/5} \end{align} $

From this we can see that

$ X_5[1]=5 \mbox{, and } X_5[0]=X_5[2]=X_5[3]=X_5[4]=0 $

or

$ X_5[k]=\begin{cases} 5\mbox{, }k=1\\ 0\mbox{, } k=0, 2, 3, 4 \end{cases} \mbox{ , periodic with } = 5 $


c) $ x[n]= e^{-j \frac{2}{5} \pi n} $

Notice that the period is 5, so we will calculate the 5-point DFT. Beginning with the inverse-DFT:

$ x[n]= e^{-j \frac{2}{5} \pi n} = e^{-j \frac{2}{5} \pi n} e^{2\pi n} = e^{j2\pi n \frac{4}{5}} $

$ \begin{align} x[n]&=\frac{1}{5} \sum_{k=0}^{4} X_5[k] e^{j2\pi kn/5} \\ &= \frac{1}{5} \left ( X_5[0]e^{j2\pi n0/5} + X_5[1]e^{j2\pi n1/5} + X_5[2]e^{j2\pi n2/5 } + X_5[3]e^{j2\pi n3/5} + X_5[4]e^{j2\pi n4/5} \right ) \\ &= e^{j2\pi n \frac{4}{5}} \end{align} $

From this we can see that

$ X_5[4]=5 \mbox{, and } X_5[0]=X_5[1]=X_5[2]=X_5[3]=0 $

or

$ X_5[k]=\begin{cases} 5\mbox{, }k=4\\ 0\mbox{, } k=0, 1, 2, 3 \end{cases} \mbox{ , periodic with } = 5 $


d) $ x[n]= e^{j \frac{2}{\sqrt{3}} \pi n} $

The period of the input is $ \sqrt{3} $. We cannot take a $ \sqrt{3} $-point DFT (only integer values).


e) $ x[n]= e^{j \frac{\pi}{3} n } \cos ( \frac{\pi}{6} n ) $

Using Euler's formula

$ \begin{align} x[n] &= e^{j\frac{\pi}{3}n} \left ( \frac{1}{2} e^{j\frac{\pi}{6}} + \frac{1}{2}e^{-j\frac{\pi}{6}}\right ) \\ &= \frac{1}{2}e^{\frac{\pi}{2}n} + \frac{1}{2}e^{j\frac{\pi}{6}n} \\ &= \frac{1}{2}e^{\frac{2\pi}{12}3n} + \frac{1}{2}e^{j\frac{2\pi}{12}n} \mbox{, this will make comparing with the IDFT easier} \end{align} $

The period for the signal is 12. Looking at the 12-point IDFT:

$ \begin{align} x[n]&=\frac{1}{12}\sum_{k=0}^{11} X_{12}[k] e^{j2\pi kn /12} \\ &= \frac{1}{2}e^{j2\pi 3n/12} + \frac{1}{2}e^{j2\pi n/12} \end{align} $

We can see that

$ X_{12}[k]=\begin{cases} 6 &\mbox{, if } k=1 \mbox{ or } k=3 \\ 0 &\mbox{, if} k=0 \mbox{, } k=2 \mbox{, or} k=4,\ldots,11 \end{cases}\mbox{, periodic with period } 12 $


f) $ x[n]= (-j)^n . $

First, rewrite the signal as

$ \begin{align} x[n] &= (-j)^n \\ &= e^{j3\pi n/2} \\ &= e^{j2\pi 3n /4} \mbox{, again, this makes comparison with the IDFT easier} \end{align} $

The period of the signal is 4. You can see this by observing that the sequence is {-j, -1, j, 1, -j, ...}. Or you can find it using the general form $ e^{j\omega_0n} $. Then you can solve for the period M by solving $ \omega_0M=2\pi m $ for some integer m. This signal, for example, would be

$ \frac{3\pi}{2} M = 2\pi n \Rightarrow M=\frac{4}{3}m \mbox{, where M and m are both integers} $

When m=3, M is the integer 4.

So, looking at the 4-point IDFT

$ \begin{align} x[n]&= \sum_{k=0}^{3} X_4[k] e^{j2\pi kn/4} \\ &= e^{j2\pi 3n/4} \end{align} $

From this, we can see that

$ X_4[k]=\begin{cases} 4 &\mbox{, if }k=3 \\ 0 &\mbox{, if } k=0,1,2 \end{cases} \mbox{, periodic with period } 4 $


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

First, rewrite the signal

$ \begin{align} x[n] &=(\frac{1}{\sqrt{2}}+j \frac{1}{\sqrt{2}})^n \\ &=(e^{j\pi/4})^n \\ &=e^{j2\pi n/8} \end{align} $

Now, looking at the 8-point IDFT

$ \begin{align} x[n] &= \sum_{k=0}^{7} X_8[k] e^{j2\pi kn /8} \\ &=e^{j2\pi n/8} \end{align} $

We can see that

$ X_8[k] = \begin{cases} 8 &\mbox{, if } k=1 \\ 0 &\mbox{, if} k=0 \mbox{ or } k=2,\ldots,7 \end{cases}\mbox{, periodic with period } 8 $


Question 2

Compute the inverse DFT of $ X[k]= e^{j \pi k }+e^{-j \frac{\pi}{2} k} $.

Solution

Rewrite so that the exponents are negative:

$ \begin{align} x[n] &= e^{j\pi k}e^{-j2\pi k} + e^{-j\pi k/2} \\ &= e^{-j\pi k} + e^{-j\pi k/2} \end{align} $

The period of the signal is 4. We can again rewrite the signal so that the period is in the denominator of the exponent (this makes the next steps easier):

$ x[n] = e^{-j2\pi 2 k/4} + e^{-j2\pi k/4} $

Looking at the 4-point DFT

$ \begin{align} X_4[k] &= \sum_{k=0}^{3} x[n] e^{-j2\pi kn /4} \\ &= e^{-j2\pi 2 k/4} + e^{-j2\pi k/4} \end{align} $

As in question 1, we can see that

$ \begin{align} x[n]&=\begin{cases} 1 &\mbox{, if }n=1 \mbox{ or } n=2 \\ 0 &\mbox{, if } n=0 \mbox{ or } n=3 \end{cases} \mbox{, periodic with period } 4 \\ &=\delta(n-1) + \delta(n-2) \mbox{, periodic with 4} \end{align} $


Question 3

Prove the time shifting property of the DFT.

Method 1

Given that

$ X_n[k] = \text{DFT} \left \{ x[n] \right \} $

Then the shifted form can be written as

$ x[n-n_0] = x[n]\ast \delta[n-n_0] $

Then it follows that

$ \begin{align} \text{DFT}\left \{ x[n-n_0] \right \} &= \text{DFT} \left \{ x[n] \right \} \text{DFT} \left \{\delta[n-n_0] \right \} \\ &= X_n[k] e^{-j2\pi kn_0/N} \end{align} $

Method 2

Or, you can use a change of variables. Let $ X_N[k] = \text{DFT} \left \{x[n] \right \} $, then

$ \begin{align} \text{DFT}\left \{ x[n-n_0] \right \} &= \sum_{k=0}^{N-1} x[n-n_0] e^{-j2\pi kn /N} \\ &= \sum_{n'=-n_0}^{N-n_0-1} x[n']e^{-j2\pi k(n' + n_0)/N} \mbox{ using the variable substitution } n'=n-n_0 \\ &=e^{-j2\pi k n_0/N} \sum_{n'=-n_0}^{N-n_0-1}x[n'] e^{-j2\pi k n'/N} \\ &=e^{-j2\pi k n_0/N} \sum_{n'=-0}^{N-1}x[n'] e^{-j2\pi k n'/N} \mbox{ (details below)}\\ &=e^{-j2\pi k n_0/N} X_N[k] \end{align} $

The change in the limits follows because $ x[n'] e^{j2\pi k n'/N} $ has a period of N. If we're summing over one full period, it doesn't matter where we start the summation.



Question 4

Under which circumstances can one recover the DTFT of a finite duration signal from the DFT of its periodic repetition? Justify your answer mathematically.

Solution

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.


Discussion

You may discuss the homework below.

  • write comment/question here
    • answer will go here

Back to Homework6

Back to ECE438, Fall 2015, Prof. Boutin

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang