Communicates & Signal Process (CS)

Question 2: Signal Processing

August 2010

Problem 1. [50 pts]

Equation below is the formula, for reconstructing the DTFT, $X(\omega)$, from $N$ equi-spaced samples of the DTFT over $0 \leq \omega \leq 2\pi$. $X_{N}(k) = X(\frac{2\pi k}{N},k=0,1,...,N-1)$ is the N-pt DFT of x[n], which corresponds to N equi-spaced samples of the DTFT of x[n] over $0 \leq \omega \leq 2\pi$.

$X_{r}(\omega)=\sum_{k=0}^{N-1} X_{N}(k) \frac{sin[\frac{N}{2}(\omega - \frac{2 \pi k}{N})]}{N sin[\frac{1}{2} (\omega -\frac{2 \pi k}{N})]} e^{-j\frac{N-1}{2}(\omega - \frac{2 \pi k}{N}) }$(1)

(a) Let x[n] be a discrete-time rectangular pulse of length $L=12$ as defined below:

$x[n] = \{-1,-1,-1,-1,1,1,1,1,1,1,1,1 \}$

(i) $X_{N}(k)$ is computed as a 16-point DFT of x[n] and used in Eqn (1) with N=16. Write a closed-form expression for resulting reconstructed spectrum $X_{r}(\omega)$.
(ii) $X_{N}(k)$ is computed as a 12-point DFT of x[n] and used in Eqn (1) with N=12. Write a closed-form expression for the resulting reconstructed spectrum $X_{r}(\omega)$.
(iii) $X_{N}(k)$ is computed as an 8-point DFT of x[n] ans used in Eqn (1) with N=8. That is, $X_{N}(k)$ is obtained by sampling the DTFT of x[n] at 8 equi-spaced frequencies between 0 and 2$\pi$. Write a closed-form expression for the resulting reconstructed spectrum $X_{r}(\omega)$.

(b) Let x[n] be a discrete-time sinewave of length L=12 as defined below. For all sub-parts of part (b), $X_{N}(k)$ is computed as a 12-pt DFT of x[n] and used in Eqn (1) with N=12.

$x[n]=cos(\frac{\pi}{3} n) \{u[n]-u[n-12]\}$

(i) Write a closed-form expression for the resulting reconstructed spectrum $X_{r}(\omega)$.
(ii) What is the numerical value of $X_{r}(\frac{\pi}{3})$? The answer is a number and you do not need a calculator to determine the value; this also applies to the next 2 parts.
(iii) What is the numerical value of $X_{r}(\frac{5 \pi}{3})$?
(iv) What is the numerical value of $X_{r}(\frac{\pi}{2})$?

Solution : (a)
(i) $x[n] = (u[n]-u[n+2]) - 2(u[n]-u[n-4])$
$X(w) = e^{-j \frac{12-1}{2}w } \frac{sin(\frac{12}{2}w)}{sin(\frac{1}{2}w)} - 2e^{-j \frac{4-1}{2}w } \frac{sin(\frac{4}{2}w)}{\frac{1}{2}w}$
$X_{r}(w) = X(w)$
(ii) same, $X_{r}(w)=X(w)$
(iii) $x_{r}[n] = \{0,0,0,0,1,1,1,1 \} = (u[n] - u[n-4])* \delta[n-4]$
$X_{r}(w) = e^{-j \frac{4-1}{2}w} \frac{sin(\frac{4}{2}w)}{\frac{1}{2}w} e^{-j4w}$

(b)
(i) $X(w)=\frac{1}{2} e^{-j \frac{11}{2}(w- \frac{\pi}{3})} \frac{sin(6(w-\frac{\pi}{3}))}{sin(\frac{1}{2}(w-\frac{\pi}{3}))} + \frac{1}{2} e^{-j \frac{11}{2} (w+\frac{\pi}{3}) } \frac{sin(6(w+\frac{\pi}{3}))}{sin(\frac{1}{2}(w-\frac{\pi}{3}))}$
(ii) $X_{r}(\frac{\pi}{3})=\frac{1}{2} \times 12 = 6$
(iii) $X_{r}(\frac{5}{3} \pi) = \frac{1}{2} \times 12 = 6$
(iv) $X_{r}(\frac{\pi}{2}) = \frac{1}{2} \times 0 = 0$

Problem 2. [50 pts]
Consider a finite-length sinewave of the form below where $k_{o}$ is an interger in the range $0 \leq k_{o} \leq N-1$.

$x[n] = e^{j 2 \pi \frac{k_{o}}{N} n} \{ u[n] - u[n-N] \}$ (2)

In addition, h[n] is a causal FIR filter of length L, where L < N. In this problem $y[n]=x[n] \star h[n]$ is the linear convolution of the causal sinewave of length N in Equation (1) with a causal FIR filter of length L, where L < N.

$y[n]=x[n] \star h[n]$

(a) The region $0 \leq n \leq L-1$ corresponds to partial overlap. The covolution sum can be written as:

$y[n]=\sum_{k=??}^{??} h[k] x[n-k] \ \ partial \ \ overlap:\ 0 \leq n \leq L-1$ (3)

Determine the upper and lower limits in the convolution sum above for $0 \leq n \leq L-1$
(b) The region $L \leq n \leq N-1$ corresponds to full overlap. The convolution sum is:

$y[n]=\sum_{k=??}^{??} h[k]x[n-k] \ \ full \ \ overlap: \ L \leq n \leq N-1$ (4)

(i) Determine the upper and lower limits in the convolution sum for $L \leq n \leq N-1$.
(ii) Substituting x[n] in Eqn (1), show that for this range y[n] simplifies to:

$y[n]=H_{N}(k_{o}) e^{j 2 \pi \frac{k_{o}}{N} n} \ \ for L \leq n \leq N-1$(5)

where $H_{N}(k)$ is the N-point DFT of h[n] evaluated at $k = k_{o}$. To get the points, you must show all work and explain all details.
(c) The region $N \leq n \leq N+L-2$ corresponds to partial overlap. The convolution sum:

$y[n] = \sum_{k=??}^{??} h[k]x[n-k] \ \ partial \ \ overlap: \ N \leq n \leq N+L-2$(6)

Determine the upper and lower limits in the convolution sum for $N \leq n \leq N+L-2$.
(d) Add the two regions of partial overlap at the beginning and end to form:

$z[n] =y[n]+y[n+N]=\sum_{k=??}^{??}h[n]x[n-k] \ \ for: \ 0 \leq n \leq L-1$(7)

(i) Determine the upper and lower limits in the convolution sum above.
(ii) Substituting x[n] in Eqn (1), show that for this range z[n] simplifies to:

$z[n] = y[n]+y[n+N]=H_{N}(k_{o})e^{j2 \pi \frac{k_{o}}{N} n} \ \ for \ 0 \leq n \leq L-1$ (8)

where $H_{N}(k)$ is the N-point DFT of h[n] evaluated at $k = k_{o}$ as defined previously.
(e) $y_{N}[n]$ is formed by computing $X_{N}(k)$ as an N-pt DFT of x[n] in Enq (2), $H_{N}(k)$ as an N-pt DFT of h[n], and then $y_{N}[n]$ as the N-pt inverse DFT of $Y_{N}(k) = X_{N}(K)H_{N}(k)$. Write a simple, closed-form expression for $y_{N}(k)$. Is $z[n]=y_{N}[n] + y[n+N] \ \ for \ 0 \leq n \leq N-1$?

Solution:
(a) $y[n] = \sum_{k=0}^{n} h[k] \cdot x[n-k]$
So, the lower and upper limits are 0 ~ n.
(b) $y[n] = \sum_{k=0}^{L-1} h[k] \cdot x[n-k]$
So, the lower and upper limits are 0 ~ L-1.
$x[n] = e^{2 \pi j (\frac{K_{0}}{N}) n } (u[n] - u[n-N])$
$y[n] = \sum_{k=-\infty}^{+ \infty} h_{N}[k] \cdot x[n-k]$
$= \sum_{k=-\infty}^{+\infty} h_{N}[k] \cdot e^{2 \pi j (\frac{k_{0}}{N})(n-k)} (u[n-k]-u[n-N-k])$
$= e^{2 \pi jn \frac{k_{0}}{N}} \sum_{k=0}^{L-1} h_{N}[k] e^{-2 \pi j \frac{k_{0}}{N}} k$
$= e^{2 \pi jn \frac{k_{0}}{N}} \cdot H_{N}(k_{0})$
(c) $y[n] = \sum_{k=n-N+1}^{L-1} h[k] \cdot x[n-k]$
(d) upper and lower limits are 0 ~ L-1.
$z[n] = \sum_{k=-\infty}^{+ \infty} h_{N}[k] \cdot x[n-k]$
$= \sum_{k=-\infty}^{+\infty} h_{N}[k] \cdot e^{2 \pi j (\frac{k_{0}}{N})(n-k)} (u[n-k]-u[n-N-k])$
$= e^{2 \pi jn \frac{k_{0}}{N}} \sum_{k=0}^{L-1} h_{N}[k] e^{-2 \pi j \frac{k_{0}}{N}} k$
$= e^{2 \pi jn \frac{k_{0}}{N}} \cdot H_{N}(k_{0})$
(e) $y_{N}[n] = H_{N}(k_{0}) e^{j 2\pi \frac{k_{0}}{N}} n$
. Yes, the equation is correct.