(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{, | + | 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{, | + | <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{, | + | 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 | + | 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> | ||
− | + | '''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>. | ||
− | + | '''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
Contents
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