(6 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
[[Category:homework]]
 
[[Category:homework]]
  
=Homework 5 Solution, [[ECE438]], Fall 2014=
+
=[[HW5ECE438F14|Homework 5]] Solution, [[ECE438]], Fall 2014=
  
 
==Questions 1==
 
==Questions 1==
Line 54: Line 54:
  
 
<math>
 
<math>
X_3[k]=\begin{cases} 3\mbox{, }k=1\\ 0\mbox{, else} \end{cases} \mbox{ , periodic with period} = 3
+
X_3[k]=\begin{cases} 3\mbox{, }k=1\\ 0\mbox{, } k=0 \mbox{ or } k=2 \end{cases} \mbox{ , periodic with } = 3
 
</math>
 
</math>
  
Line 83: Line 83:
 
By matching terms, we can see that
 
By matching terms, we can see that
  
<math>X_{1000}[k]=\begin{cases} 1000&\mbox{, if }k=999 \\ 0 &\mbox{, else} \end{cases}</math>
+
<math>X_{1000}[k]=\begin{cases} 1000&\mbox{, if }k=999 \\ 0 &\mbox{, }k=0,\ldots,998 \end{cases} \mbox{, periodic with period } 1000</math>
  
 
d) <math>x_2[n]= e^{j \frac{2}{\sqrt{3}} \pi n}</math>
 
d) <math>x_2[n]= e^{j \frac{2}{\sqrt{3}} \pi n}</math>
Line 116: Line 116:
  
 
<math>
 
<math>
X_{1000}[k] = \begin{cases} 500&\mbox{, if } k=1 \mbox{ or }k=999 \\ 0 &\mbox{, else} \end{cases}
+
X_{1000}[k] = \begin{cases} 500&\mbox{, if } k=1 \mbox{ or }k=999 \\ 0 &\mbox{, if } k=0 \mbox { or } k=2,\ldots,998 \end{cases} \mbox{, periodic with period } 1000
 
</math>
 
</math>
  
Line 123: Line 123:
 
'''Solution'''
 
'''Solution'''
  
Using Euler's fomula
+
Using Euler's formula
  
 
<math>\begin{align}
 
<math>\begin{align}
 
x_2[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 ) \\
 
x_2[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{\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}</math>
 
\end{align}</math>
 +
 +
The period for the signal is 12. Looking at the 12-point IDFT:
 +
 +
<math>\begin{align}
 +
x_2[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}</math>
 +
 +
We can see that
 +
 +
<math>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</math>
  
 
g) <math>x_8[n]= (-j)^n .</math>
 
g) <math>x_8[n]= (-j)^n .</math>
 +
 +
First, rewrite the signal as
 +
 +
<math>\begin{align}
 +
x_8[n] &= (-j)^n \\
 +
&= e^{j3\pi n/2} \\
 +
&= e^{j2\pi 3n /4} \mbox{, again, this makes comparison with the IDFT easier}
 +
\end{align}</math>
 +
 +
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 <math>e^{j\omega_0n} </math>. Then you can solve for the period M by solving <math>\omega_0M=2\pi m</math> for some integer m. This signal, for example, would be
 +
 +
<math>
 +
\frac{3\pi}{2} M = 2\pi n \Rightarrow M=\frac{4}{3}m \mbox{, where M and m are both integers}
 +
</math>
 +
 +
When m=3, M is the integer 4.
 +
 +
So, looking at the 4-point IDFT
 +
 +
<math>\begin{align}
 +
x[n]&= \sum_{k=0}^{3} X_4[k] e^{j2\pi kn/4} \\
 +
&= e^{j2\pi 3n/4}
 +
\end{align}</math>
 +
 +
From this, we can see that
 +
 +
<math>X_4[k]=\begin{cases} 4 &\mbox{, if }k=3 \\ 0 &\mbox{, if } k=0,1,2 \end{cases} \mbox{, periodic with period } 4</math>
  
 
h) <math class="inline">x_3[n] =(\frac{1}{\sqrt{2}}+j \frac{1}{\sqrt{2}})^n </math>
 
h) <math class="inline">x_3[n] =(\frac{1}{\sqrt{2}}+j \frac{1}{\sqrt{2}})^n </math>
  
Note: All of these DFTs are VERY simple to compute. If your computation looks like a monster, look for a simpler approach!
+
'''Solution'''
 +
 
 +
First, rewrite the signal
 +
 
 +
<math>\begin{align}
 +
x_3 &=(\frac{1}{\sqrt{2}}+j \frac{1}{\sqrt{2}})^n  \\
 +
&=(e^{j\pi/4})^n \\
 +
&=e^{j2\pi n/8}
 +
\end{align}</math>
 +
 
 +
Now, looking at the 8-point IDFT
 +
 
 +
<math>\begin{align}
 +
x[n] &= \sum_{k=0}^{7} X_8[k] e^{j2\pi kn /8} \\
 +
&=e^{j2\pi n/8}
 +
\end{align}</math>
 +
 
 +
We can see that
 +
 
 +
<math>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</math>
 +
 
 
----
 
----
 
==Question 2 ==
 
==Question 2 ==
 
Compute the inverse DFT of  <math class="inline">X[k]= e^{j \pi k }+e^{-j \frac{\pi}{2} k} </math>.
 
Compute the inverse DFT of  <math class="inline">X[k]= e^{j \pi k }+e^{-j \frac{\pi}{2} k} </math>.
  
Note: Again, this is a VERY simple problem. Have pity for your grader, and try to use a simple approach!
+
'''Solution'''
 +
 
 +
Rewrite so that the exponents are negative:
 +
 
 +
<math>\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}</math>
 +
 
 +
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):
 +
 
 +
<math>x[n] = e^{-j2\pi 2 k/4} + e^{-j2\pi k/4}</math>
 +
 
 +
Looking at the 4-point DFT
 +
 
 +
<math>\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}</math>
 +
 
 +
As in question 1, we can see that
 +
 
 +
<math>\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}</math>
 +
 
 
----
 
----
 +
 
== Question 3 ==
 
== Question 3 ==
 
Prove the time shifting property of the DFT.  
 
Prove the time shifting property of the DFT.  
 +
 +
'''Method 1'''
 +
 +
Given that
 +
 +
<math>X_n[k] = \text{DFT} \left \{ x[n] \right \} </math>
 +
 +
Then the shifted form can be written as
 +
 +
<math>x[n-n_0] = x[n]\ast \delta[n-n_0]</math>
 +
 +
Then it follows that
 +
 +
<math>\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}</math>
 +
 +
'''Method 2'''
 +
 +
Or, you can use a change of variables. Let <math>X_N[k] = \text{DFT} \left \{x[n]  \right \}</math>, then
 +
 +
<math>\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}</math>
 +
 +
The change in the limits follows because <math>x[n'] e^{j2\pi k n'/N} </math> has a period of N. If we're summing over one full period, it doesn't matter where we start the summation.
 +
 
----
 
----
 
== Discussion ==
 
== Discussion ==

Latest revision as of 11:21, 10 October 2014


Homework 5 Solution, ECE438, Fall 2014

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_1[n] = \left\{ \begin{array}{ll} 1, & n \text{ multiple of } N\\ 0, & \text{ else}. \end{array} \right. $

Solution

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} $

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

Solution

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

$ \begin{align} x[n]&=\frac{1}{3} \sum_{k=0}^{2} X_3[k] e^{j2\pi kn/3} \\ &= \frac{1}{3} \left ( X_3[0]e^{j2\pi k0/3} + X_3[1]e^{j2\pi k1/3} + X_3[2]e^{j2\pi k2/3} \right ) \\ &= e^{j2\pi n/3} \end{align} $

From this we can see that

$ X_3[1]=3 \mbox{, and } X_3[0]=X_3[2]=0 $

or

$ X_3[k]=\begin{cases} 3\mbox{, }k=1\\ 0\mbox{, } k=0 \mbox{ or } k=2 \end{cases} \mbox{ , periodic with } = 3 $

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

Solution

The period of this signal is 1000. To make life easier, we will multiple by a factor (noting that the factor is always 1, so it doesn't change the signal):

$ \begin{align} x_5[n]&=e^{-j \frac{2}{1000} \pi n}e^{j2\pi n} \\ &= e^{j2\pi \frac{1000-1}{1000}} \\ &=e^{j2\pi \frac{998}{1000}} \end{align} $

The positive exponent is easier to deal with.

Now we can use the inverse transform as before, using a 1000-point IDFT:

$ \begin{align} x_5[n] &= \frac{1}{1000} \sum_{k=0}^{k=999} X_{1000}[k]e^{j2\pi k n/1000} \\ &= e^{j2\pi \frac{999}{1000}} \end{align} $

By matching terms, we can see that

$ X_{1000}[k]=\begin{cases} 1000&\mbox{, if }k=999 \\ 0 &\mbox{, }k=0,\ldots,998 \end{cases} \mbox{, periodic with period } 1000 $

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

Solution

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

e) $ x_6[n]= \cos\left( \frac{2}{1000} \pi n\right) ; $

Solution

First, use Euler's formula

$ x_6[n]=\frac{1}{2} e^{j2\pi n/1000} + \frac{1}{2}e^{-j2\pi n/1000} $

As in d), change the exponents so they are both positive:

$ \begin{align} x_6[n]&=\frac{1}{2} e^{j2\pi n/1000} + \frac{1}{2}e^{-j2\pi n/1000}e^{2\pi n} \\ &=\frac{1}{2} e^{j2\pi n/1000} + \frac{1}{2}e^{j2\pi 999n/1000} \end{align} $

Then looking at the 1000-point inverse DFT:

$ \begin{align} x_6[n] &= \frac{1}{1000} \sum_{k=0}^{999} X_{1000}[k]e^{j2\pi kn/1000} \\ &= \frac{1}{2} e^{j2\pi n/1000} + \frac{1}{2}e^{j2\pi 999n/1000} \end{align} $

Again, by matching terms we can see that

$ X_{1000}[k] = \begin{cases} 500&\mbox{, if } k=1 \mbox{ or }k=999 \\ 0 &\mbox{, if } k=0 \mbox { or } k=2,\ldots,998 \end{cases} \mbox{, periodic with period } 1000 $

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

Solution

Using Euler's formula

$ \begin{align} x_2[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_2[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 $

g) $ x_8[n]= (-j)^n . $

First, rewrite the signal as

$ \begin{align} x_8[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 $

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

Solution

First, rewrite the signal

$ \begin{align} x_3 &=(\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.


Discussion

You may discuss the homework below.

  • write comment/question here
    • answer will go here

Back to ECE438, Fall 2014, Prof. Boutin

Alumni Liaison

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

Buyue Zhang