(14 intermediate revisions by 3 users not shown)
Line 19: Line 19:
 
</math>  
 
</math>  
  
'''Solution'''
 
  
 +
<span style="color:red"> This is the long way. Do not do this if you can help it!!! </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 31: 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>
  
b) <math>x[n]= e^{j \frac{2}{5} \pi n}</math>
 
  
'''Solution'''
+
<math>
 +
\begin{align}
 +
x[n] &=s_N[n] \text{ (Remember, that function we defined when looking at downsampling in the frequency domain?) } \\
 +
&=\frac{1}{N} \sum_{k=0}^{N-1} e^{jk \frac{2\pi}{N} n} \text{ (Writing }s_N[n] \text{ as its Fourier series.)} \\
 +
\end{align}
 +
</math>
 +
 
 +
By comparison with the inverse-DFT expression for x[n], namely
 +
 
 +
<math> x[n]=\frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{j \frac{2\pi}{N} kn }</math>
 +
 
 +
we find that <math> X[k]=1</math>, for k=1,…,N-1. Using the periodicity of X[k] (period N), we conclude that X[k]=1, for all k.
 +
 
 +
b) <math>x[n]= e^{j \frac{2}{5} \pi n}</math>
  
 
Notice that the period is 5, so we will calculate the 5-point DFT. Beginning with the inverse-DFT:
 
Notice that the period is 5, so we will calculate the 5-point DFT. Beginning with the inverse-DFT:
Line 41: Line 54:
 
\begin{align}
 
\begin{align}
 
x[n]&=\frac{1}{5} \sum_{k=0}^{4} X_5[k] e^{j2\pi kn/5} \\
 
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 k0/5}  + X_5[1]e^{j2\pi k1/5} + X_5[2]e^{j2\pi k2/5} + X_5[3]e^{j2\pi k3/5} + X_5[4]e^{j2\pi k4/5}  \right ) \\
+
&= \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}  
 
&= e^{j2\pi n/5}  
 
\end{align}
 
\end{align}
Line 60: Line 73:
  
 
c) <math>x[n]= e^{-j \frac{2}{5} \pi n}</math>
 
c) <math>x[n]= e^{-j \frac{2}{5} \pi n}</math>
 
'''Solution'''
 
  
 
Notice that the period is 5, so we will calculate the 5-point DFT. Beginning with the inverse-DFT:
 
Notice that the period is 5, so we will calculate the 5-point DFT. Beginning with the inverse-DFT:
 +
 +
<math>x[n]= e^{-j \frac{2}{5} \pi n} = e^{-j \frac{2}{5} \pi n} e^{j 2\pi n} = e^{j2\pi n \frac{4}{5}} </math>
  
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
x[n]&=\frac{1}{5} \sum_{k=0}^{4} X_5[k] e^{-j2\pi kn/5} \\
+
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 k0/5}  + X_5[1]e^{-j2\pi k1/5} + X_5[2]e^{-j2\pi k2/5} + X_5[3]e^{-j2\pi k3/5} + X_5[4]e^{-j2\pi k4/5}  \right ) \\
+
&= \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}  
+
&= e^{j2\pi n \frac{4}{5}}
 
\end{align}
 
\end{align}
 
</math>
 
</math>
Line 76: Line 89:
  
 
<math>
 
<math>
X_5[1]=5 \mbox{, and } X_5[0]=X_5[2]=X_5[3]=X_5[4]=0  
+
X_5[4]=5 \mbox{, and } X_5[0]=X_5[1]=X_5[2]=X_5[3]=0  
 
</math>
 
</math>
  
Line 82: Line 95:
  
 
<math>
 
<math>
X_5[k]=\begin{cases} 5\mbox{, }k=1\\ 0\mbox{, } k=0, 2, 3, 4 \end{cases} \mbox{ , periodic with } = 5
+
X_5[k]=\begin{cases} 5\mbox{, }k=4\\ 0\mbox{, } k=0, 1, 2, 3 \end{cases} \mbox{ , periodic with } = 5
 
</math>
 
</math>
  
  
 
d) <math>x[n]= e^{j \frac{2}{\sqrt{3}} \pi n}</math>
 
d) <math>x[n]= e^{j \frac{2}{\sqrt{3}} \pi n}</math>
 
'''Solution'''
 
  
 
The period of the input is <math>\sqrt{3}</math>. We cannot take a <math>\sqrt{3}</math>-point DFT (only integer values).  
 
The period of the input is <math>\sqrt{3}</math>. We cannot take a <math>\sqrt{3}</math>-point DFT (only integer values).  
  
  
e) <math>x[n]= \cos\left( \frac{2}{1000} \pi n\right) ;</math>
+
e) <math class="inline">x[n]= e^{j \frac{\pi}{3} n } \cos ( \frac{\pi}{6} n )</math>
 
+
'''Solution'''
+
 
+
First, use Euler's formula
+
 
+
<math> x[n]=\frac{1}{2} e^{j2\pi n/1000} + \frac{1}{2}e^{-j2\pi n/1000} </math>
+
 
+
As in d), change the exponents so they are both positive:
+
 
+
<math>\begin{align}
+
x[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}</math>
+
 
+
Then looking at the 1000-point inverse DFT:
+
 
+
<math>\begin{align}
+
x[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}</math>
+
 
+
Again, by matching terms we can see that
+
 
+
<math>
+
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>
+
 
+
 
+
f) <math class="inline">x[n]= e^{j \frac{\pi}{3} n } \cos ( \frac{\pi}{6} n )</math>
+
 
+
'''Solution'''
+
  
 
Using Euler's formula
 
Using Euler's formula
Line 146: Line 126:
  
  
g) <math>x[n]= (-j)^n .</math>
+
f) <math>x[n]= (-j)^n .</math>
  
 
First, rewrite the signal as
 
First, rewrite the signal as
Line 175: Line 155:
 
<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>
 
<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[n] =(\frac{1}{\sqrt{2}}+j \frac{1}{\sqrt{2}})^n </math>
 
  
'''Solution'''
+
g) <math class="inline">x[n] =(\frac{1}{\sqrt{2}}+j \frac{1}{\sqrt{2}})^n </math>
  
 
First, rewrite the signal
 
First, rewrite the signal
Line 202: Line 181:
 
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'''
+
''' Solution '''
  
 
Rewrite so that the exponents are negative:
 
Rewrite so that the exponents are negative:
Line 265: Line 244:
 
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.
 
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.
  
 +
 +
----
 +
 +
==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 <math>x[n]</math> is <math>M</math>. The number of points of its DFT is <math>N</math>.
 +
 +
Using IDFT we have
 +
 +
<math>x'[n]=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{\frac{j2\pi nk}{N}}</math>
 +
 +
Noticing that <math>x'[n]=x'[n+N]</math>, so the <math>x'[n]</math> obtained by IDFT is periodic with <math>N</math>.
 +
 +
We can reconstruct DTFT by substituting <math>x[n]</math> by <math>x'[n]</math> as long as <math>x[n]=x'[n]</math> for <math>n=0,1,...,M-1</math>. i.e.
 +
 +
<math>\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}</math>
 +
 +
Since <math>x'[n]</math> is periodic with <math>N</math>, we must guarantee that <math>N\ge M</math> in order to fully reconstruct DTFT using DFT.
  
 
----
 
----

Latest revision as of 15:36, 20 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 if you can help it!!! 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, that function we defined when looking at downsampling in the frequency domain?) } \\ &=\frac{1}{N} \sum_{k=0}^{N-1} e^{jk \frac{2\pi}{N} n} \text{ (Writing }s_N[n] \text{ as its Fourier series.)} \\ \end{align} $

By comparison with the inverse-DFT expression for x[n], namely

$ x[n]=\frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{j \frac{2\pi}{N} kn } $

we find that $ X[k]=1 $, for k=1,…,N-1. Using the periodicity of X[k] (period N), we conclude that X[k]=1, for all k.

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^{j 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

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett