Solution of HW8
Question 1
According to the definition
$ \begin{align} X_2[k]&=\sum_{n=0}^{N-1}x_2[n]e^{-\frac{j2\pi nk}{N}} \\ X_1[z]&=\sum_{n=0}^{N-1}x_1[n]z^{-n} \end{align} $
Pull in $ z=\frac{1}{2}e^{-j\frac{2\pi}{N}k} $ in $ X_1(z) $
$ \begin{align} X_2[k]&=X_1(z)|_{z=\frac{1}{2}e^{-j\frac{2\pi}{N}k}} \\ &=\sum_{n=0}^{N-1}x_1 [n](\frac{1}{2}e^{-j\frac{2\pi}{N}k})^{-n} \\ &=\sum_{n=0}^{N-1}x_1 [n](\frac{1}{2})^{-n}e^{j\frac{2\pi n}{N}k} \\ &\text{Change variable m=-n } \\ &=\sum_{m=0}^{-(N-1)}x_1 [-m](\frac{1}{2})^{m}e^{-j\frac{2\pi m}{N}k} \\ &\text{Change variable l=m+N } \\ &=\sum_{l=N}^{1}x_1 [N-l](\frac{1}{2})^{l-N}e^{-j\frac{2\pi (l-N)}{N}k} \\ &=\sum_{l=1}^{N}x_1 [N-l](2)^{N-l}e^{-j\frac{2\pi l}{N}k} \end{align} $
Therefore,
$ x_2 [n]=x_1 [(-n)\text{ mod N }]2^{((-n)\text{ mod N })} $, where n=0,1,...,N-1
Question 2
a)
$ x[n]=6\delta[n]+5 \delta[n-1]+4 \delta[n-2]+3 \delta[n-3]+2 \delta[n-4]+\delta[n-5]\,\! $
Using the 6-point DFT formula,
$ \begin{align} X[k] &=\sum_{n=0}^{5}\left(6\delta[n]+5 \delta[n-1]+4 \delta[n-2]+3 \delta[n-3]+2 \delta[n-4]+\delta[n-5]\right)e^{-j\frac{2\pi}{6}kn} \\ &= 6 + 5e^{-j\frac{2\pi}{6}k} + 4e^{-j\frac{2\pi}{6}2k} + 3e^{-j\frac{2\pi}{6}3k} + 2e^{-j\frac{2\pi}{6}4k} + e^{-j\frac{2\pi}{6}5k} \\ \end{align} $
b)
We use the 6-point inverse-DFT formula to obtain $ y_6[n] $
$ y_6[n]=\frac{1}{6}\sum_{k=0}^{5} W_6^{-2k} X[k] e^{j\frac{2\pi}{6}nk} = \frac{1}{6}\sum_{k=0}^{5} X[k] e^{j\frac{2\pi}{6}(n+2)k} \quad \text{where} \;\; W_N=e^{-j\frac{2\pi}{N}} $
If you compare this with the 6-point inverse-DFT of $ X[k] $
$ x_6[n]=\frac{1}{6}\sum_{k=0}^{5}X[k] e^{j\frac{2\pi}{6}nk} $
then, you will notice that $ y_6[n]=x_6[(n+2)\text{mod}6] $. Thus, it becomes
$ y_6[n]=4\delta[n]+3 \delta[n-1]+2\delta[n-2]+\delta[n-3]+6 \delta[n-4]+5\delta[n-5]\,\! $
(Producting $ W^{-2k} $ to $ X[k] $ yields circular-shifting to the left by 2 in the periodic discrete-time signal)
c)
$ h[n]=\delta[n]+\delta[n-1]+\delta[n-2]\,\! $
computing the circular convolution with $ x[n] $ and $ h[n] $,
$ \begin{align} y[n] =& x[n]\circledast_6 h[n] \\ =& \quad \{\quad 6,\quad 5,\quad 4,\quad 3,\quad 2,\quad 1\} \\ & +\! \{\quad 1,\quad 6,\quad 5,\quad 4,\quad 3,\quad 2\} \\ & +\! \{\quad 2,\quad 1,\quad 6,\quad 5,\quad 4,\quad 3\} \\ =& \quad \{\quad 9,\;\;12,\;\;\!15,\;\;12,\quad 9,\quad 6\} \\ =& 9\delta[n]+12\delta[n-1]+15\delta[n-2]+12\delta[n-3]+9\delta[n-4]+6\delta[n-5] \\ \end{align} $
d)
In order for the periodic repetition (with period N) of the usual convolution between x[n] and h[n] to be the same with the N-point circular convolution,
$ N \geq L+M-1 $ where L is the length of x[n] and M is the length of h[n].
Therefore, $ N\geq8 $.
Question 3
a)
$ \begin{align} X(\omega)&=\sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n} \\ &=\sum_{n=-\infty}^{\infty}(2\delta [n]+6\delta [n-1]-\delta [n-2])e^{-j\omega n} \\ &=2+6e^{-j\omega}-e^{-j2\omega} \end{align} $
$ \begin{align} Y(\omega)&=\sum_{n=-\infty}^{\infty}y[n]e^{-j\omega n} \\ &=\sum_{n=-\infty}^{\infty}x[-n]e^{-j\omega n} \\ &=\sum_{n=-\infty}^{\infty}(2\delta [-n]+6\delta [-n-1]-\delta [-n-2])e^{-j\omega n} \\ &=2+6e^{j\omega}-e^{j2\omega} \end{align} $
b)
Denote v[n]=x[n]*y[n]
Then the DTFT of v[n] is given by
$ V(\omega)=X(\omega)Y(\omega) $
By using answer of part a,
$ \begin{align} V(\omega)&= (2+6e^{-j\omega}-e^{-j2\omega})(2+6e^{j\omega}-e^{j2\omega}) \\ &=41+6e^{-j\omega}+6e^{j\omega}-2e^{j2\omega}-2e^{-j2\omega} \end{align} $
Recall the definition of DTFT,
$ V(\omega)=\sum_{n=-\infty}^{\infty}v[n]e^{-j\omega n} $
Therefore,
$ \sum_{n=-\infty}^{\infty}v[n]e^{-j\omega n}=41+6e^{-j\omega}+6e^{j\omega}-2e^{j2\omega}-2e^{-j2\omega} $
By comparison the coefficients on both sides of the equation, we get
$ v[n]=-2\delta [n+2]+6\delta [n+1]+41\delta [n]+6\delta [n-1]-2\delta [n-2] $
c)
$ z[0]=x[0 \text{ mod 4}]=x[0]=2 $
$ z[1]=x[-1 \text{ mod 4}]=x[3]=0 $
$ z[2]=x[-2 \text{ mod 4}]=x[2]=-1 $
$ z[3]=x[-3 \text{ mod 4}]=x[1]=6 $
$ z[n]=2\delta [n]-\delta [n-2]+6\delta [n-3] $
In order to compute the 4-pt circular convolution of x[n] and z[n]
We first compute 4-pt DFT of x[n] and z[n].
Denote $ t[n]=x[n]\circledast_4 z[n] $
T[k] is the 4-pt DFT of t[n], where k=0,1,2,3
$ \begin{align} X(k)&=\sum_{n=0}^{3}x[n]e^{-\frac{j2\pi nk}{4}} \\ &=2+6e^{-\frac{j2\pi k}{4}}-e^{-\frac{j4\pi k}{4}} \\ &=2+6e^{-\frac{j\pi k}{2}}-e^{-j\pi k} \end{align} $
$ \begin{align} Z(k)&=\sum_{n=0}^{3}z[n]e^{-\frac{j2\pi nk}{4}} \\ &=2-e^{-\frac{j4\pi k}{4}}+6e^{-\frac{j6\pi k}{4}} \\ &=2-e^{-j\pi k}+6e^{-\frac{j3\pi k}{2}} \end{align} $
$ \begin{align} T(k)=X(k)Z(k)&=(2+6e^{-\frac{j\pi k}{2}}-e^{-j\pi k})(2-e^{-j\pi k}+6e^{-\frac{j3\pi k}{2}}) \\ &=41+12e^{-\frac{j\pi k}{2}}-4e^{-j\pi k}+6e^{-\frac{j3\pi k}{2}}-6e^{-\frac{j5\pi k}{2}} \\ &=41+6e^{-\frac{j\pi k}{2}}-4e^{-j\pi k}+6e^{-\frac{j3\pi k}{2}} \end{align} $
Then the circular convolution can be computed by doing IDFT to T(k)
$ \begin{align} T[k]&=\sum_{n=0}^{3}t[n]e^{-\frac{j2\pi nk}{4}} \\ &=41+6e^{-\frac{j\pi k}{2}}-4e^{-j\pi k}+6e^{-\frac{j3\pi k}{2}} \end{align} $
By comparing the coefficients, we can get
$ x[n]\circledast_4 z[n]=t[n]=41\delta [n]+6\delta [n-1]-4\delta [n-2]+6\delta [n-3] $
d)
In order to avoid aliasing in the circular convolution, we must guarantee that
$ N\ge length(x)+length(z)-1=3+4-1=6 $
I don't understand why n = 3 would be included when calculating z[n]. Isn't the range of n [0,3)?
Back to HW8
Back to ECE 438 Fall 2010
