Homec4science
Diffusion epfl (master) Browse

R2653/teaching/COM303/2014/exams/finalSolution.tex
e6c78c7fade2master

Last Change
Raw File

finalSolution.tex
View Options

\documentclass[a4paper,13pt]{article}
\usepackage{defsDSPcourse}
\usepackage{dspTricks}
\usepackage{dspFunctions}
\usepackage{dspBlocks}
\begin{document}
\newcounter{tmpc}
\framebox[12cm][l]{Name:\rule{0cm}{1cm}}\hfill\framebox[3cm][l]{\#\rule{0cm}{1cm}}
\vspace{1em}
\begin{center}%
\sffamily
{\LARGE \bfseries COM-303 - Signal Processing for Communications \\ Final Exam} \\
\vspace{1em}
{\large Saturday, June 21 2014, 09:15 to 12:15}
\vspace{1em}
\end{center}
\centerline{\rule{\textwidth}{.5pt}}
\begin{itemize}
\item {\bf Write your name} on the top left corner of {\bf ALL sheets you turn in}, including this one. When you are done, \textbf{staple} all your sheets together \textbf{with this sheet on top}!
\item You can have two A4 sheet of \emph{handwritten} notes (front and back). Please \textbf{no photocopies, no books and no electronic devices}. Turn off your phone if you have it with you.
\item There are 5 problems for a total of 100 points; the number of points for each problem is indicated next to it.
\item Please write your derivations clearly, as there is partial credit.
\end{itemize}
\centerline{\rule{\textwidth}{.5pt}}
\vspace{1em}
\begin{exercise}{(10 points)}
Consider the discrete-time signal $x[n] = \sinc(an)$ with $0 < a < 1$; compute the following sums:
\begin{enumerate}
\item $\displaystyle \sum_{n = -\infty}^{\infty} x[n]$
\item $\displaystyle \sum_{n = -\infty}^{\infty} x^2[n]$
\end{enumerate}
\vspace{2em}
{\em the impulse response of an ideal lowpass filter with cutoff frequency $\omega_c$ is }
\[
h[n] = (\omega_c/\pi)\sinc((\omega_c/\pi)n)
\]
{\em therefore $x[n]$ is the impulse response of an ideal lowpass filter with cutoff frequency $a\pi$, scaled by $1/a$ so that} $X(e^{j\omega}) = (1/a)\rect(\omega/(2a\pi))$. {\em From this:}
\begin{enumerate}
\item $\displaystyle \sum_{n = -\infty}^{\infty} x[n] = X(e^{j\omega})|_{\omega = 0} = 1/a$
\item$\displaystyle \sum_{n = -\infty}^{\infty} x^2[n] = \frac{1}{2\pi}\int_{-\pi}^{\pi}|X(e^{j\omega})|^2 = \frac{1}{2\pi}\int_{-a\pi}^{a\pi}a^{-2} = 1/a$ {\em (by using Parseval's theorem)}
\end{enumerate}
\end{exercise}
\begin{exercise}{(10 points)}
Compute the DFT of the $\mathbb{C}^4$ vector $\mathbf{x} = [ 1 \ \ 1 \ -1 \ -1]^T$ \\ \\
{\em the DFT matrix for $\mathbb{C}^4$ is }
\[
\mathbf{W} = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -j & -1 & j \\
1 & -1 & 1 & -1 \\
1 & j & -1 & -j
\end{bmatrix}
\]
{\em By computing the matrix-vector product $\mathbf{X} = \mathbf{Wx}$ it is easy to obtain $\mathbf{X} = [0 \ \ (2-2j) \ \ 0 \ \ (2+2j)]^T$}
\end{exercise}
\begin{exercise}{(20 points)}
Compute the impulse response of the causal filter with the following pole-zero plot:
\begin{center}
\begin{dspPZPlot}[width=5cm,xticks=none,yticks=none]{1.3}
\dspPZ[label={$\alpha$}]{0.6,0}
\dspPZ[type=zero,label=none]{1,0}
\end{dspPZPlot}
\end{center}
{\em The system has a pole in $z = \alpha$ and a zero in $z = 1$. We can write the transfer function of the system as}
\[
H(z) = \frac{1 - z^{-1}}{1 - \alpha z^{-1}} = \frac{1}{1 - \alpha z^{-1}} - z^{-1}\frac{1}{1 - \alpha z^{-1}}
\]
{\em A first order section with a pole in $z = \alpha$ has a transfer function $G(z) = 1/(1 - \alpha z^{-1})$ and impulse response $g[n] = \alpha^n u[n]$. Therefore the impulse response of the above system is}
\[
h[n] = g[n] - g[n-1] = \alpha^n u[n] - \alpha^{n-1} u[n-1] = \begin{cases}
0 & n < 0 \\
1 & n = 0 \\
\alpha^{n-1}(\alpha - 1) & n > 0
\end{cases}
\]
\end{exercise}
\begin{exercise}{(15 points)}
Sketch the magnitude response of the following causal system:
\begin{center}
\begin{dspBlocks}{1.1}{0.5}
$x[n]~~$ & \BDadd & & \BDsplit & \BDadd & & \BDsplit & $~~y[n]$ \\
& & \BDdelay & & & \BDdelay &
\end{dspBlocks}
\ncline{1,4}{2,4}\ncline{1,7}{2,7}
\ncline{2,2}{2,3}\ncline{2,6}{2,5}
\psset{arrows=->}
\ncline{1,1}{1,2}\ncline{1,2}{1,5}\ncline{1,5}{1,8}
\ncline{4,2}{4,3}\ncline{4,3}{4,4}\ncline{4,4}{4,5}
\ncline{2,2}{1,2}\ncline{2,4}{2,3}\tbput{$\qquad\qquad (1+j)$}
\ncline{2,5}{1,5}\ncline{2,7}{2,6}\tbput{$\qquad\qquad (1-j)$}
\end{center}
{\em The transfer function of the system is} $H(z) = H_1(z)H_2(z)$ {\em where}
\[
H_{1,2}(z) = \frac{1}{1 - (1\pm j)z^{-1}}.
\]
{\em The system has therefore no zeros and two poles at $z = (1\pm j)$ or, in polar coordinates, at $z = e^{\pm j\frac{\pi}{4}}$ (note that the filter is not stable); its frequency response in magnitude follows the classic resonator pattern:}
\begin{center}
\begin{dspPlot}[xtype=freq,yticks=none,xticks=4]{-1,1}{0,3}
\dspFunc{x \dspTFM{1}{1 -2 2}}
\end{dspPlot}
\end{center}
\end{exercise}
\begin{exercise}{(45 points)}
Bellanger's Approximation is an empirical formula used to estimate the order of an equiripple lowpass filter based on its design specifications. For a lowpass filter with transition band $[\omega_p,\ \omega_s]$ and error tolerances of $\delta_p$ and $\delta_s$ in passband and stopband respectively, the filter order is going to be approximately
\[
N \approx \frac{-2\log_{10}(10\delta_p\delta_s)}{3(\omega_s - \omega_p)/2\pi} - 1
\]
Since the order is inversely proportional to the width of the transition band, ``sharp'' filters (i.e., filters with a narrow transition band) will require a lot of multiplications per output sample. The following questions will ask you to analyze an alternative design strategy called IFIR (Interpolated FIR), used to obtain sharp filters at a lower computational cost.
\vspace{1em}
To begin with, assume you have designed an $N$-tap FIR lowpass $H(z)$ with the following magnitude response (we're showing just the positive frequencies and neglecting the ripples):
\begin{center}
\begin{dspPlot}[height=2.5cm,xtype=freq,yticks=none,xticks=1,ylabel={$|H(e^{j\omega})|$}]{0,1}{0,1.2}
\psline(0,1)(0.3,1)(0.5,0)(1,0)
\psline[linewidth=0.5pt,linestyle=dashed](0.3,1)(0.3,0)
\dspCustomTicks[axis=x]{0.3 $\phi_p$ 0.5 $\phi_s$}
\end{dspPlot}
\end{center}
The transition band of $H(z)$ has width $\Delta_H = \phi_s - \phi_p$. Build now a derived FIR filter $G(z)$ with impulse response
\[
g[n] = \begin{cases}
h[n/2] & \mbox{for $n$ even} \\
0 & \mbox{for $n$ odd} \\
\end{cases}
\]
\begin{enumerate}
\item express $G(z)$ in terms of $H(z)$ \\ \\
{\em $G(z)$ is obtained by upsampling the impulse response by a factor of 2; therefore $G(z) = H(z^2)$}
\item sketch the magnitude response |$G(e^{j\omega})|$; you don't need to draw the ripples but clearly show the band edges and their values\\
\begin{center}
\begin{dspPlot}[height=2.5cm,xtype=freq,yticks=none,xticks=1,ylabel={$|G(e^{j\omega})|$}]{0,1}{0,1.2}
\psline(0,1)(0.15,1)(0.25,0)(0.75,0)(0.85,1)(1,1)
\dspCustomTicks[axis=x]{0.15 $\phi_p/2$ 0.25 $\phi_s/2$ 0.75 $\pi-\phi_s/2$}
\end{dspPlot}
\end{center}
\item assuming that multiplications by zero can be ignored, what is the number of multiplications per output sample required by $G(z)$?\\ \\
{\em $N$ multiplications per output sample}
\setcounter{tmpc}{\theenumi}
\end{enumerate}
Consider now the following cascade, used to implement a complete IFIR filter:
\begin{center}
\begin{dspBlocks}{1.1}{0.5}
$x[n]~~$ & \BDfilter{$G(z)$} & \BDfilter{$I(z)$} & $~~y[n]$
\end{dspBlocks}
\psset{arrows=->}
\ncline{1,1}{1,2} \ncline{1,2}{1,3} \ncline{1,3}{1,4}
\end{center}
\begin{enumerate}
\setcounter{enumi}{\thetmpc}
\item describe filter $I(z)$ so that the cascade $G(z)I(z)$ is equivalent to a simple lowpass filter \\ \\
{\em $I(z)$ should be a lowpass filter that removes the high frequency image introduced by the upsampling. }
\item specify the passband and stopband frequencies of the global filter implemented by the cascade \\ \\
{\em the global filter is a lowpass with band edges:}
\begin{align*}
\omega_p &= \phi_p/2 \\
\omega_s &= \phi_s/2
\end{align*}
\item find the passband and stopband frequencies of $I(z)$ so as to maximize its transition band \\ \\
{\em to minimize the computational cost of the cascade we can keep the transition band as wide as possible. We could use the following values, for instance:
\begin{align*}
\theta_p &= \phi_p/2 \\
\theta_s &= \pi - \phi_s/2 \\
\end{align*}
for a transition band of $\Delta_I = \pi - (\phi_s + \phi_p)/2$.}
\begin{center}
\begin{dspPlot}[height=2.5cm,xtype=freq,yticks=none,xticks=1,ylabel={$|G(e^{j\omega})|$}]{0,1}{0,1.2}
\psline(0,1)(0.15,1)(0.25,0)
\psline[linecolor=lightgray](0.75,0)(0.85,1)(1,1)
\psline[linestyle=dashed,linewidth=1pt](0,1.1)(0.15,1.1)(0.75,0)
\dspCustomTicks[axis=x]{0.15 $\phi_p/2$ 0.25 $\phi_s/2$ 0.75 $\pi-\phi_s/2$}
\end{dspPlot}
\end{center}
\setcounter{tmpc}{\theenumi}
\end{enumerate}
Consider now the following specifications for a lowpass filter:
\begin{align*}
\omega_p &= 0.3\pi \\
\omega_s &= 0.31\pi \\
\delta_p &= \delta_s = 0.01
\end{align*}
and compare a direct FIR with an IFIR implementation.
\begin{enumerate}
\setcounter{enumi}{\thetmpc}
\item estimate the order of a direct equiripple implementation of the filter using Bellanger's formula \\
{\em
\begin{align*}
N &\approx \frac{-2\log_{10}(10\cdot 10^{-2}\cdot 10^{-2})}{3(0.31-0.3)\pi/2\pi} - 1 \\
&= \frac{6}{0.015} - 1 = 399
\end{align*}
}
\item now consider an IFIR implementation: give the specifications for the initial IFIR filter $H(z)$ (i.e. the values of $\phi_p$ and $\phi_s$ to use in the design of $H(z)$) \\ \\
{\em the initial filter has double the passband and stopband frequencies, i.e.
\begin{align*}
\phi_p &= 0.6\pi \\
\phi_s &= 0.62\pi \\
\end{align*}
}
\item estimate the order of an equiripple implementation of $H(z)$ \\
\[
N_H \approx \frac{6}{0.03} - 1 = 199
\]
\item assume an optimal equiripple design for $I(z)$ using the maximum transition band $\Delta_I$ you found before and using $\delta_p = \delta_s = 0.01$; estimate the order of $I(z)$ \\ \\
$\Delta_I = \pi - (\phi_p + \phi_s)/2 = 0.39\pi$
\[
N_I \approx \frac{6}{3\cdot 0.39\pi/2\pi} - 1 = \frac{6}{3\cdot 0.39\pi/2\pi} - 1 \approx 9
\]
\item using the above estimations, determine the number of operations per output sample of the IFIR cascade \\ \\
{\em we will need 199 multiplications for $H(z)$ and 9 for $I(z)$ for a total of 208 multiplications}
\end{enumerate}
\end{exercise}
\end{document}
c4science · Help