Line 254: Line 254:
 
\text{DFT}\left \{ x[n-n_0] \right \} &= \sum_{k=0}^{N-1} x[n-n_0] e^{-j2\pi kn /N} \\
 
\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 \\
 
&= \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} \sum_{n'=-n_0}^{N-n_0-1}x[n'] e^{-j2\pi k n'} \\
+
&=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} \sum_{n'=-0}^{N-1}x[n'] e^{-j2\pi k n'}  \mbox{ (details below)}\\
+
&=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} X_N[k]
+
&=e^{-j2\pi k n_0/N} X_N[k]
 
\end{align}</math>
 
\end{align}</math>
  
The change in the limits follows because <math>x[n'] e^{j2\pi k n'} </math> has a period of N. If we're summing over one full period, it doesn't matter where we start the summation.
+
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.
  
 
----
 
----

Latest revision as of 10: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