{\LARGE\bfseries COM-303 - Signal Processing for Communications \\ Final Exam}\\
\vspace{1em}
{\large Friday 21.06.2019, from 8h15 to 11h15}\\
% {last name $\rightarrow$ room: [A to F] $\rightarrow$ \textbf{CM1120}, [A to F] $\rightarrow$ \textbf{CM1121}, [A to F] $\rightarrow$ \textbf{CM1221}}
\vspace{1em}
\end{center}
\centerline{\rule{\textwidth}{.5pt}}
\vspace{1em}
{
\LARGE\bfseries
\begin{center}
Verify that this exam has YOUR last name on top \\
\vspace{1em}
DO NOT OPEN THE EXAM UNTIL INSTRUCTED TO DO SO
\end{center}
}
\vspace{1em}
\centerline{\rule{\textwidth}{.5pt}}
\vspace{1em}
\begin{itemize}
\item{\bf Write your name} on the top left corner of {\bf ALL the sheets you turn in}.
\item There are 5 problems for a total of 100 points; the number of points is indicated for each problem.
\item Please \textbf{write your derivations clearly!}
\item You can have two A4 sheets of \emph{handwritten} notes (front and back). Please \textbf{no photocopies, no books and no electronic devices}. Turn off your phone and store it in your bag.
\vspace{1em}
\item\textbf{When you are done, simply leave your solution at your place with this page on top and exit the classroom}. Do NOT bring the exam to the main desk.
Since we will need to determine the stability of the system later, we can already factorize $A(z)$ by simple inspection as
\[
A(z)=(1-\frac{1}{2}z^{-1})^2.
\]
We can also try to see if the root of $A(z)$ is also a root of $B(z)$: indeed $B(1/2)=0$. We can now factor $B(z)$ either by performing polynomial division or by noticing that both $+1$ and $-1$ are also roots; we have
The signal $x_N[n]$ is the periodization of $x[n]$ with period $N$, which is guaranteed to exist for all $N$ since $x[n]$ is absolutely summable. Since $x_N[n]$ is $N$-periodic, we can write
\[
x_N[n]= y[n \mod N]
\]
where $y[n]$ is the finite-length signal formed by the samples of $x_N[n]$ for $0\leq n < N-1$.
To find the $N$ values of $y[n]$ we need to compute the sum
is interpolated to a continuous-time signal $x_c(t)$ using an ideal sinc interpolator with interpolation period $T_s =1$; because the sinc interpolator has infinite support, the resulting continuous-time signal will also have infinite support, although it will decay to zero. Given a small positive constant $\delta\ll1$, we want to find an estimate for a time value $t_0$, dependent on $\delta$ and $N$, so that
\[
|x_c(t)| < \delta\quad\mbox{for $t > t_0$}.
\]
{\footnotesize [Hint: remember that $\left|\sum a_n \right| \leq\sum |a_n|$.]}
In communication systems it is often useful to be able to estimate the local ``slope'' of a discrete-time signal; for instance, in the figures below, the local slope around $n=0$ appears to be equal to 1 for the first two signals and equal to $-1/2$ for the third.
In theory, the local slope at $n$ is the value of the derivative of the sinc-interpolated signal, computed at $nT_s$; we have seen that this value can be computed directly in discrete time by using an ideal differentiator, that is, a filter with impulse response $h[n]=(-1)^n/n$. The ideal differentiator can be approximated by impulse truncation; consider for instance the 3-tap approximation
\[
\hat{h}[n]=\begin{cases}
1 & n =-1\\
-1 & n =1\\
0 & \mbox{otherwise}
\end{cases}
\]
If we compute the values $(x_k \ast\hat{h})[0]$ for the signals above, we can easily find that the result is twice the value of the slope in $n=0$; for instance $(x_2\ast\hat{h})[0]=1+1=2$. In other words, the slope in $n$ can be estimated as the value in $n$ of the convolution between the signal and the differentiation filter: the longer the impulse response, the better the approximation.
Unfortunately the ideal differentiator has a highpass frequency response and so, if the input signal is noisy, its performance is not good. We will now study an alternative approach based on \textit{linear regression}. In linear regression, given a set of data points, we want to approximate the data using a straight line; the optimal line is the one that minimizes the mean squared error of the approximation. An example of linear regression as commonly used in statistics is shown in the picture here on the right; in that case the data points are represented by arbitrary pairs of coordinates on the plane. In our case, the problem is simplified by the fact that the abscissae are given by the regularly spaced discrete time index $n$.
The goal of the exercise is to build an FIR filter that, at each index $n$, computes the slope of the optimal local linear regressor at $n$. To formalize the problem, consider the symmetric interval around the origin $-N \le n \le N$; given a signal $x[n]$, we approximate the signal around $n=0$ with a straight line described by the equation $y[n]=\alpha+\beta n$. The mean squared error is given by
and the optimal values for $\alpha$ and $\beta$ can be found my minimizing the MSE. For example, in the following figure, minimizing the MSE for $N =3$ yields the linear regression around $n=0$ shown by the dotted line.
\dspFunc[linestyle=dotted,linewidth=1pt,xmin=-5,xmax=5]{x -0.343 mul 0.014 add}
\end{dspPlot}
\end{center}
\begin{enumerate}[resume]
\item Derive the expression for $\beta$ that minimizes $J$, as a function of $x[n]$ for $-N \le n \le N$; this provides the local slope of the signal in $n=0$.
\end{enumerate}
The expression you found for $\beta$ can be rearranged to look as the convolution, computed in $n=0$, between $x[n]$ and a $(2N+1)$-tap FIR filter $r_N[n]$:
this means that the local slope of $x[n]$ for \textit{any} index $n$ can be obtained simply by filtering $x[n]$ with $r_N[n]$, which is called a \textit{slope filter}.
\begin{enumerate}[resume]
\item Compute the five values of the slope filter $r_2[n]$.
\displaystyle\frac{-3k}{N(N+1)(2N+1)} & -N \le n \le N \\[1em]
0 & \mbox{otherwise}
\end{cases}
\]
(note the sign change in the numerator because we're flipping the impulse response in the convolution). For $N=2$, therefore, we have
\[
r_2[n]=\begin{cases}
0.2 & n =-2\\
0.1 & n =-1\\
-0.1 & n=1\\
-0.2 & n=2\\
0 & \mbox{otherwise}
\end{cases}
\]
\item The filter $r_N[n]$ is an odd-length, antisymmetric FIR (Type III) for all $N$ and therefore it has linear phase.
\item The signal has a flat slope for $n < -100$ and for $n > 100$ and a linear slope with $\beta=2/200=0.01$ in between. The result of filtering the signal with $r_{10}[n]$ is shown below in black.
\item If we use a long filter ($r_{100}[n]$ has 201 taps) then the longer impulse response make the slope estimation less sharp and the estimation gets ``smeared'' in time. The result is sketched in gray below.
Let's name the intermediate signals in the system as in the picture above. To show that $y[n]=0$ we need to show that $x_{1,2}[n]= x_{2,2}[n]$. We can proceed analytically or by example.
\vspace{1em}
Analytically, let's consider the top branch; we have
\[
x_{1,1}[n]=\begin{cases}
x[n/3] & \mbox{if $(n/3)\in\mathbb{N}$} \\
0 & \mbox{otherwise}
\end{cases}
\]
and
\[
x_{1,2}[n]= x_{1,1}[2n]=\begin{cases}
x[2n/3] & \mbox{if $(2n/3)\in\mathbb{N}$} \\
0 & \mbox{otherwise}
\end{cases}
\]
For the bottom branch we have $x_{2,1}[n]= x[2n]$ and
\[
x_{2,2}[n]=\begin{cases}
x_{2,1}[n/3] & \mbox{if $(n/3)\in\mathbb{N}$} \\
0 & \mbox{otherwise}
\end{cases}
\hspace{1em} =\hspace{1em}
\begin{cases}
x[2n/3] & \mbox{if $(n/3)\in\mathbb{N}$} \\
0 & \mbox{otherwise}
\end{cases}
\]
Since $(n/3)\in\mathbb{N}$ if and only if $(2n/3)\in\mathbb{N}$, $x_{1,2}[n]$ and $x_{2,2}[n]$ are identical.
$\hat{h}[n]$ of the ideal differentiator via impulse truncation, that is, set $\hat{h}[n]= h[n]$ for $n =-1, 0, 1$ and $\hat{h}[n]=0$ everywhere else. Let $s_k[n]=(x_k \ast\hat{h})[n]$, with $k =1, 2, 3$, be the result of filtering each of the signals in the figures above with $\hat{h}[n]$. Show that $s_k[0]$ is proportional to the slope of $x_k[n]$ in zero.
\end{enumerate}
\item The 3-tap FIR approximation to the ideal differentiator obtained by impulse truncation is
\[
\hat{h}[n]=\begin{cases}
1 & n =-1\\
-1 & n =1\\
0 & \mbox{otherwise}
\end{cases}
\]
so that $s_k[0]=-x_k[-1]+ x_k[1]$.
Applying the filter to the three examples yields:
\begin{itemize}
\item$s_1[0]=0+2=2$
\item$s_2[0]=1+1=2$
\item$s_3[0]=-0.5-0.5=-1$
\end{itemize}
so that $s_k[0]$ is twice the slope of the dotted line in the figures in all cases.