## 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

## Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood