Homec4science
Diffusion epfl (master) Browse

R2653/teaching/COM303/exams/sources/2016final.tex
c8aed94be65bmaster

Last Change
Raw File

2016final.tex
View Options

\documentclass[12pt,a4paper]{article}
\usepackage{styles/SPhw}
\includecomment{sol}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{exercise}{DFT}
Given a vector $\mathbf{x} = \begin{bmatrix}x_0 & x_1 & \ldots & x_{N-1}\end{bmatrix} \in \mathbb{C}^N$ and its DFT $\mathbf{X} = \begin{bmatrix}X_0 & X_1 & \ldots & X_{N-1}\end{bmatrix}$ show that
\[
\mathbf{x}^* = \mbox{IDFT}\left\{\begin{bmatrix}X_0^* & X_{N-1}^* & X_{N-2}^* & \ldots & X_{1}^*\end{bmatrix}\right\}
\]
\begin{sol}
\Solution
\begin{align*}
\mbox{IDFT}\left\{\begin{bmatrix}X_0^* & X_{N-1}^* & X_{N-2}^* & \ldots & X_{1}^*\end{bmatrix}\right\}[n]
&= \frac{1}{N}\sum_{k=0}^{N-1}X_k^*\, e^{j\frac{2\pi}{N}n(N-k)} \\
&= \frac{1}{N}\sum_{k=0}^{N-1}X_k^*\, e^{-j\frac{2\pi}{N}nk} \\
&= \frac{1}{N}\sum_{k=0}^{N-1}\left(X_k\, e^{j\frac{2\pi}{N}nk}\right)^* \\
&= \left(\frac{1}{N}\sum_{k=0}^{N-1}X_k\, e^{j\frac{2\pi}{N}nk}\right)^* \\
&= x_n^*
\end{align*}
\end{sol}
\end{exercise}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{exercise}{System analysis}
Consider the causal system implemented by the following block diagram:
\begin{center}
\vspace{2em}
\begin{dspBlocks}{0.9}{0.8}
& & & & & & & & \\
$x[n]~~$ & \BDadd & \BDdelay & \BDsplit & \BDdelay & \BDadd & \BDdelay & \BDsplit & $~~y[n]$ \\
& & & & & & & & \\
\end{dspBlocks}
\BDConnHNext{2}{1}\BDConnHNext{2}{2}\BDConnHNext{2}{5}\BDConnHNext{2}{6}
\ncline{->}{2,3}{2,5}\ncline{->}{2,7}{2,9}
\ncline{2,8}{1,8}\ncline{1,8}{1,2}\taput{$-1$}\ncline{->}{1,2}{2,2}
\ncline{2,4}{3,4}\ncline{3,4}{3,6}\taput{$2$}\ncline{->}{3,6}{2,6}
\end{center}
\begin{enumerate}
\item compute the system's transfer function $H(z)$
\item plot the system's poles and zeros on the complex plane
\item determine if the system stable
\end{enumerate}
\begin{sol}
\Solution
First consider the FIR subsystem inside the feedback loop and call its transfer function $G(z)$
\vspace{-3em}
\begin{center}
\vspace{2em}
\begin{dspBlocks}{0.9}{0.8}
& & & & & & & & \\
& & \BDdelay & \BDsplit & \BDdelay & \BDadd & \BDdelay & & \\
& & & & & & & & \\
\end{dspBlocks}
\BDConnHNext{2}{2}\BDConnHNext{2}{5}\BDConnHNext{2}{6}
\ncline{->}{2,3}{2,5}\ncline{->}{2,7}{2,9}
\ncline{2,4}{3,4}\ncline{3,4}{3,6}\taput{$2$}\ncline{->}{3,6}{2,6}
\end{center}
From simple inspection it is easy to see that
\[
G(z) = 2z^{-2} + z^{-3}
\]
Now we can redraw the system as a simple feedback loop:
\begin{center}
\vspace{2em}
\begin{dspBlocks}{0.9}{0.5}
& & & & & & & & \\
$x[n]~~$ & \BDadd & & & \BDfilter{$G(z)$} & & & \BDsplit & $~~y[n]$ \\
& & & & & & & & \\
\end{dspBlocks}
\BDConnHNext{2}{1}
\ncline{->}{2,2}{2,5}\ncline{->}{2,5}{2,9}
\ncline{2,8}{1,8}\ncline{1,8}{1,2}\taput{$-1$}\ncline{->}{1,2}{2,2}
\end{center}
so that
\[
H(z) = \frac{G(z)}{1+G(z)} = \frac{2z^{-2} + z^{-3}}{1 + 2z^{-2} + z^{-3}}
\]
As explained before, unfortunately the denominator of the transfer function does not admit a simple factorization. We can find the roots with a numerical package and we have
\begin{align*}
z_1 &= -0.4534\\
z_{2,3} &= 0.2267 \pm 1.4677j
\end{align*}
Since the magnitude of the complex roots is greater than one, the system is unstable.
\vspace{2em}
{\em This was the intended exercise:} If the feedback branch had had a gain of $+1$ as intended, the transfer function would have been
\[
H(z) = \frac{G(z)}{1-G(z)} = \frac{2z^{-2} + z^{-3}}{1 - 2z^{-2} - z^{-3}}
\]
and, using simple factorization:
\[
H(z) = 2z^{-2}\frac{1 + (1/2)z^{-1}}{1 - z^{-2} - z^{-2}(1 + z^{-1})} = 2z^{-2}\frac{1 + (1/2)z^{-1}}{(1 + z^{-1})(1 - z^{-1} - z^{-2})}
\]
so that the transfer function has a zero in $z = -1/2$ and poles in $-1$ and $(1\pm\sqrt{5})/2$:
\begin{center}
\begin{dspPZPlot}[width=5cm]{1.8}
\dspPZ[type=zero,label=none]{-.5,0}
\dspPZ[type=pole,label=none]{-1,-.04}
\dspPZ[type=pole,label=none]{-0.61,-.04}
\dspPZ[type=pole,label=none]{1.61,-.04}
\end{dspPZPlot}
\end{center}
Since one of the poles is outsite the unit circle, the system is not stable.
\end{sol}
\end{exercise}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{exercise}{Sampling}
The continuous-time signal
\[
x_c(t) = \sum_{m=1}^{4}m\cos(2\pi\,f_0 m\,t),
\]
with $f_0 = 300$Hz, is raw-sampled into the discrete time sequence $x[n] = x_c(nT_s)$ with $T_s = 5\cdot 10^{-4}$s. Plot the DTFT of $x[n]$, $X(e^{j\omega})$.
\begin{sol}
\Solution
The sampling frequency is $F_s = 1/T_s = (1/5)\cdot 10^4$Hz $= 2000$Hz. Since the continuous-time signal is just a linear combination of pure sinusoids, we can easily determine its highest frequency which is $F_{\max} = 4\cdot 300 = 1200$Hz. Since $F_{\max} > F_s/2$ we will have aliasing. With this in mind, the easiest way to solve the problem is by working in the time domain, although of course we can operate also in the frequency domain.
\vspace{1em}
\textbf{Working in the time domain:} by replacing the value for $T_s$ and we have
\[
x[n] = x(nT_s) = \sum_{m=1}^{4}m\cos(\omega_m n) \qquad \omega_m = 2\pi\frac{m f_0}{F_s} = \frac{3\pi}{10}m
\]
The frequencies $\omega_m$ are less than $\pi$ for $m = 1, 2, 3$; for $m=4$ we have aliasing and we can write
\[
\cos(\frac{12}{10}\pi\, n) = \cos(\frac{20 - 8}{10}\pi \, n) = \cos(\frac{8}{10}\pi \, n)
\]
so that, in the end
\[
x[n] = \cos(\frac{3\pi}{10} n) + 2 \cos(\frac{6\pi}{10} n) + 3 \cos(\frac{9\pi}{10} n) + 4 \cos(\frac{8\pi}{10} n)
\]
and the spectrum is:
\begin{center}
\begin{dspPlot}[xtype=freq,xticks=5,yticks=custom]{-1,1}{0,4.5}
\dspDiracs{0.3 1 0.6 2 0.8 4 0.9 3}
\dspDiracs{-0.3 1 -0.6 2 -0.8 4 -0.9 3}
\dspCustomTicks[axis=y]{0 0 1 $\pi$ 2 $2\pi$ 3 $3\pi$ 4 $4\pi$}
\end{dspPlot}
\end{center}
\textbf{Working in the frequency domain:} the spectrum of the continuous-time signal is simply a collection of 8 spectral lines:
\[
X_c(j\Omega) = \pi\sum_{\substack{m=-4\\m\neq 0}}^{4}|m|\,\delta(\Omega - 2\pi\,f_0 m)
\]
By sampling with a period $T_s$ we have the standard periodization formula:
\begin{align*}
X(e^{j\omega}) &= \frac{1}{T_s}\sum_{k=-\infty}^{\infty}X_c\left(j\frac{\omega + 2\pi k}{T_s}\right) \\
&= \frac{\pi}{T_s}\sum_{\substack{m=-4\\m\neq 0}}^{4}|m|\sum_{k=-\infty}^{\infty}\,\delta\left(\frac{\omega + 2\pi k}{T_s} - 2\pi\,f_0 m \right) \\
&= \pi\sum_{\substack{m=-4\\m\neq 0}}^{4}|m|\sum_{k=-\infty}^{\infty}\,\delta(\omega - 2\pi(f_0 T_s)m + 2\pi k) \\
&= \frac{1}{2}\sum_{\substack{m=-4\\m\neq 0}}^{4}|m|\tilde{\delta}(\omega - \frac{3\pi}{10}m)
\end{align*}
which yields the same plot as before. Note that we had to use the scaling property of the Dirac delta, $\delta(t/\alpha) \equiv \alpha\delta(t)$, which is perhaps not widely known. Hence the preference for the time-domain approach.
\end{sol}
\end{exercise}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\peQAM#1{/s 10 x 10 div exp def 2 #1 1 add neg exp -3 mul s mul .4141 mul }
\makeatletter
\def\dspLegendStyle(#1,#2)#3{%
\rput[lt](#1,#2){{%
\begin{tabular}{ll}
\@dsplegendStyle#3 \@empty
\end{tabular}}}}
\def\@dsplegendStyle#1 #2 #3{%
{\psline[#1](0,0.2)(2,0.2)\rule{2.5em}{0pt}} & #2\\ \space % fbox here to have a visual test
\ifx #3\@empty\else
\expandafter\@dsplegendStyle
\fi
#3}
\makeatother
\begin{exercise}{Communication systems}
In this exercise you will need to design a data transmission system for the analog channel sketched in this picture (positive frequencies only):
\begin{dspPlot}[width=0.9\textwidth,height=1.3cm,xtype=freq,xticks=custom,yticks=none]{0,2.2}{0,5}
\psframe[fillstyle=vlines,linecolor=gray,hatchcolor=gray,hatchangle=20](.5,-.5)(.9,0.5)
\psframe[fillstyle=vlines,linecolor=gray,hatchcolor=gray,hatchangle=20](1,-.5)(1.6,0.5)
\psframe[fillstyle=vlines,linecolor=gray,hatchcolor=gray,hatchangle=20](1.9,-.5)(2,0.5)
\dspCustomTicks{0 0 .5 500Hz 1 1KHz 1.6 1.6KHz 2 2KHz}
\dspText(.7,1.3){$W_1$}
\dspText(1.3,1.3){$W_2$}
\dspText(1.95,1.3){$W_3$}
\end{dspPlot}
The channel has three usable bands with the following characteristics:
\begin{itemize}\setlength\itemsep{0pt}
\item band $W_1$, from 500Hz to 900Hz
\item band $W_2$, from 1000Hz to 1600Hz
\item band $W_3$, from 1900Hz to 2000Hz
\end{itemize}
To transmit the data you can use one or more configurable passband data transmitters. For each transmitter you can set the following parameters:
\begin{enumerate}\setlength\itemsep{0pt}
\item[1-] the center frequency for the trasmission band (in Hz)
\item[2-] the number of symbols per second (i.e. the symbol rate or Baud rate)
\item[3-] the number of bits per symbol (4, 8, 16, or 32)
\end{enumerate}
Each transmitter can also adjust its gain so that its transmitted signal reaches the maximum power allowed by the channel's power constraint. Because of different noise levels across the spectrum the resulting SNR levels for each subband are
\begin{itemize}\setlength\itemsep{0pt}
\item band $W_1$: SNR of 16dBs
\item band $W_2$: SNR of 10dBs
\item band $W_3$: SNR of 20dBs
\end{itemize}
The operational characteristic for the data transmitters is shown in this chart, where each curve shows the attainable probability of error as a function of the SNR; each curve corresponds to a different bit-per-symbol operation mode:
\begin{center}
\begin{dspPlot}[width=0.9\textwidth,sidegap=0,yticks=custom,xticks=2,ylabel={$P_{\mbox{err}}$},xlabel={SNR (dB)}]{0,30}{-8,0}
\begin{dspClip}%
\dspFunc[linecolor=black]{\peQAM{1}}%
\dspFunc[linecolor=black,linestyle=dashed,dash=15pt\space3pt]{\peQAM{2}}%
\dspFunc[linecolor=black,linestyle=dashed,dash=5pt\space4pt]{\peQAM{3}}%
\dspFunc[linecolor=black,linestyle=dotted]{\peQAM{4}}%
\end{dspClip}
\dspCustomTicks[axis=y]{0 $10^0$ -5 $10^{-5}$}
\dspLegendStyle(22,-.4){{linecolor=black} {4 bits per symbol} {linecolor=black,linestyle=dashed,dash=15pt\space3pt} {8 bits per symbol} {linecolor=black,linestyle=dashed,dash=5pt\space4pt} {16 bits per symbol} {linecolor=black,linestyle=dashed,linestyle=dotted} {32 bits per symbol}}
\end{dspPlot}
\end{center}
We want the transmission scheme to operate at an overall probability of error of $10^{-5}$ or less. Determine the maximum achievable transmission rate (in bits per second).
\begin{sol}
\Solution
Since we have three independent subbands, we will use a separate transmitter for each one. The number of symbols per second for each transmitter will be equal to the (positive) width of each subband while the trasmission center frequency will be equal to each subband's center frequency
\begin{itemize}
\item band $W_1$: 400 symbols per second, center frequency $f_1 = 700$Hz
\item band $W_2$: 600 symbols per second, center frequency $f_1 = 1300$Hz
\item band $W_3$: 100 symbols per second, center frequency $f_1 = 1950$Hz
\end{itemize}
To compute the total throughput we need to determine how many bits per symbol can be sent over each subchannel at the given reliability figure. Since we need to operate at most at $P_e=10^{-5}$ we can find the required minimum SNR for each operation curve by looking at the intersection with the line $P_e=10^{-5}$:
\begin{center}
\begin{dspPlot}[width=0.9\textwidth,sidegap=0,yticks=custom,xticks=2,ylabel={$P_{\mbox{err}}$},xlabel={SNR (dB)}]{0,30}{-8,0}
\begin{dspClip}%
\dspFunc[linecolor=black]{\peQAM{1} }%
\dspFunc[linecolor=black,linestyle=dashed,dash=15pt\space3pt]{\peQAM{2}}%
\dspFunc[linecolor=black,linestyle=dashed,dash=5pt\space4pt]{\peQAM{3} }%
\dspFunc[linecolor=black,linestyle=dotted]{\peQAM{4} }%
\end{dspClip}
\dspCustomTicks[axis=y]{0 $10^0$ -5 $10^{-5}$}
\psline[linecolor=gray,linewidth=1pt](0,-5)(30,-5)
\psline[linecolor=gray,linewidth=1pt](12,-8)(12,0)
\psline[linecolor=gray,linewidth=1pt](15,-8)(15,0)
\psline[linecolor=gray,linewidth=1pt](18.2,-8)(18.2,0)
\psline[linecolor=gray,linewidth=1pt](21.2,-8)(21.2,0)
\end{dspPlot}
\end{center}
From the plot we can see that:
\begin{itemize}
\item to transmit at 4 bits per symbol we need at least $\approx12$dB SNR
\item to transmit at 8 bits per symbol we need at least $\approx15$dB SNR
\item to transmit at 16 bits per symbol we need at least $\approx18$dB SNR
\item to transmit at 32 bits per symbol we need at least $\approx21$dB SNR
\end{itemize}
therefore:
\begin{itemize}
\item band $W_1$: SNR of 16dBs $\Rightarrow$ we can transmit at 8 bits per symbol
\item band $W_2$: SNR of 10dBs $\Rightarrow$ we cannot transmit since all possible rates will have $P_e>10^{-5}$ at this SNR
\item band $W_3$: SNR of 20dBs $\Rightarrow$ we can transmit at 16 bits per symbol
\end{itemize}
The final capacity of the transmission scheme is therefore $R = W_1\cdot 8 + W_3\cdot 16 = 4800$bps.
\end{sol}
\end{exercise}
\begin{exercise}{Quantization}
We have seen that one of the fundamental ingredients of JPEG compression is the {\em deadzone} quantizer, i.e. a quantizer which has a quantization interval centered around zero. To see the effects of the deadzone quantizer on SNR consider the following problem.
\vspace{1ex}
Assume $x[n]$ is an i.i.d. discrete-time signal whose values are over the $[-1, 1]$ interval. Consider the following uniform 2-bit quantizers for the interval:
\begin{center}
\psset{unit=1.6cm}
\begin{tabular}{ccc}
normal quantizer & & deadzone quantizer \\
$
\mathcal{Q}_n(x) = \begin{cases}
3/4 & \mbox{if $1/2 \leq x \leq 1$} \\
1/4 & \mbox{if $0 \leq x < 1/2$} \\
-1/4 & \mbox{if $-1/2 \leq x < 0$} \\
-3/4 & \mbox{if $-1 \leq x < -1/2$} \\
\end{cases}
$
& \hspace{4em} &
$
\mathcal{Q}_n(x) = \begin{cases}
2/3 & \mbox{if $1/3 \leq x \leq 1$} \\
0 & \mbox{if $|x| < 1/3$} \\
-2/3 & \mbox{if $-1 \leq x \leq -1/3$} \\
\end{cases}
$ \\ \\ \\
\begin{pspicture}(-1.1,-1.1)(1.1,1.1)
\footnotesize
\psset{fractionLabels,fractionLabelBase=2}
\psaxes[linewidth=1pt,tickwidth=0.5pt,dx=0.5,dy=0.5,showorigin=false](0,0)(-1.1,-1.1)(1.1,1.1)
\uput[90](0,1){$\mathcal{Q}_n(x)$}
\uput[90](1.1,0){$x$}
\multido{\n=0+1}{4}{\pscircle*[linecolor=gray](!0 \n\space 2 div 0.75 sub){2pt}}
\psplot[plotpoints=800,linewidth=2pt,linecolor=gray]{-0.99}{0.99}%
{x abs 2 mul floor 2 div 0.25 add x abs x div mul}
\end{pspicture}
& &
\begin{pspicture}(-1.1,-1.1)(1.1,1.1)
\footnotesize
\psset{fractionLabels,fractionLabelBase=3}
\psaxes[linewidth=1pt,tickwidth=0.5pt,dx=0.333333,dy=0.333333,showorigin=false](0,0)(-1.1,-1.1)(1.1,1.1)
\uput[90](0,1){$\mathcal{Q}_d(x)$}
\uput[90](1.1,0){$x$}
\multido{\n=0+1}{3}{\pscircle*[linecolor=gray](!0 \n\space 1 sub 2 mul 3 div){2pt}}
\psplot[plotpoints=800,linewidth=2pt,linecolor=gray]{-0.99}{0.99}{x 3 mul 2 div round 2 mul 3 div}
\end{pspicture}
\end{tabular}
\end{center}
Both quantizers operate at two bits per sample but the deadzone quantizer "wastes" a fraction of a bit since it has only 3 quantization intervals instead of 4; for a uniformly distributed input over $[-1, 1]$, therefore, the Mean Square Error of the deadzone quantizer will be larger than the MSE of the standard quantizer.
Assume now that the probability distribution for each input sample is the following:
\[
P[x[n] = \alpha] = \begin{cases}
0 & \mbox{if $|\alpha| > 1$} \\
p & \mbox{if $|\alpha| = 0$} \\
(1-p)/2 & \mbox{otherwise}
\end{cases}
\]
In other words, each sample is either zero with probability $p$ or drawn from a uniform distribution over the $[-1, 1]$ interval; we can express this distribution as a pdf like so:
\[
f(x) = \frac{1-p}{2} + p\delta(x)
\]
where the Dirac delta encodes the higher probability of the zero value.
Determine the minimum value of $p$ for which it is better to use the deadzone quantizer, i.e. the value of $p$ for which the MSE of the deadzone quantizer is smaller that the MSE of the uniform quantizer.
\vspace{1ex}
{\footnotesize\em Hint: remember that the formula for the MSE of a scalar quantizer over the $[-1, 1]$ interval (under the hypotheses of iid samples with distribution $f(x)$) is
\[
\sigma^{2} = \int_{-1}^{1} [\mathcal{Q}(x)-x]^2\,f(x)\,dx
\]
For a uniform quantizer with $M$ quantization levels (as the ones in this exercise) if the input distribution is uniform (i.e. $f(x)=1/2$) the above simplifies to:
\[
\sigma^{2} = \int_{-1}^{1}(\mathcal{Q}(x)-x)^2\frac{1}{2}\,dx = \frac{\Delta^2}{12} = \frac{(2/M)^2}{12} = \frac{1}{3M^2}
\]
}
\begin{sol}
\Solution
The number of quantization levels in the two quantizers are $M=M_n=4$ for the normal 2-bit quantizer and $M=M_d=3$ for the deadzone quantizer. Let's compute the MSE for the normal quantizer using the composite pdf for the input
\begin{align*}
\sigma_n^{2} &= \int_{-1}^{1}(\mathcal{Q}_n(x)-x)^2\left(\frac{1-p}{2} + p\delta(x)\right)\,dx \\
&= (1-p)\int_{-1}^{1}(\mathcal{Q}_n(x)-x)^2\frac{1}{2}\,dx + p\,\int_{-1}^{1}(\mathcal{Q}_n(x)-x)^2\,\delta(x)\,dx \\
&= (1-p)\frac{1}{3M_n^2} + p[{Q}_n(0)]^2 \\
&= (1-p)\frac{1}{48} + p\frac{1}{16}
\end{align*}
where we have used the fact that the normal quantizer maps zero to $1/4$; similarly, for the deadzone quantizer (which maps zero to zero):
\begin{align*}
\sigma_d^{2} &= \int_{-1}^{1}(\mathcal{Q}_d(x)-x)^2\left(\frac{1-p}{2} + p\delta(x)\right)\,dx \\
&= (1-p)\frac{1}{3M_d^2} + p[{Q}_d(0)]^2 \\
&= (1-p)\frac{1}{27}
\end{align*}
from which we find
\[
\sigma_d^{2} < \sigma_n^{2} \quad\mbox{for}\quad p > \frac{21}{102} \approx 20\%
\]
\end{sol}
\end{exercise}
\end{document}
c4science · Help