\documentclass[12pt]{article} \usepackage[french]{babel} \voffset -2.8 cm \textwidth 17 cm \textheight 24.7 cm \oddsidemargin -.54 cm \evensidemargin -1.54 cm \usepackage[latin1]{inputenc} \pagestyle{plain} \begin{document} \centerline {\Large \sc Information and coding theory} \bigskip \bigskip \hrule \bigskip \bigskip \centerline {\underline{\Large Solution to exercise sheet n$^\circ$ 1}:} \bigskip \noindent {\bf 1-1.} \par \medskip \noindent (a) Example ${\mathcal{X}} = \{0,1, \dots m-1 \}$. With $p(x)=\frac{1}{m}$ for $x \in {\mathcal{X}}$. \par \medskip \noindent (b) $H(X)=-\sum_{i=0}^{m-1}p_{i}\log_{2}p_{i}=\log_{2}m=6$ bits. \par \medskip \noindent (c) One needs 6 bits, since $2^6=64$. \par \medskip \noindent (d) One needs 3 symbols, since $4^3=64$. \par \medskip \noindent (e) One defines the Lagrangian $\qquad L(\{p_{i}\})=H(X)-\lambda[\sum_{i=0}^{m-1}p_{i}-1].$ \newline Condition for an extremum: $$\forall i, \frac{\partial L}{\partial p_{i}}=0.$$ The distribution that maximizes $H(X)$ (note that $H(X)$ is concave) satisfies: \[ -\log_{2}p_{i}-\frac{1}{\ln 2}+\lambda=0 \qquad \forall i. \] One finds $p_{i}=2^{\lambda-\frac{1}{\ln 2}}$, \emph{i.e.} $p_i$ is a constant. With the constraint one finds $p_{i}=\frac{1}{m}$. \bigskip \noindent {\bf 1-2.} \par \medskip \noindent (a) $H(X_P)=1.75$ bits. \par \medskip \noindent (b) $H(X_Q)=2$ bits. \par \medskip \noindent (c) The expected length of the codewords is $1.75$ bits for the distribution $P$ and $2.25$~bits for the distribution $Q$. \par \medskip \noindent (d) The entropy gives the minimal expected length of codewords one can obtain. The binary code $C$ is optimal for the distribution $P$, since its expected length $L_P=H(X_P)$. For the distribution $Q$ we find $L_Q > H(X_Q)$ and $L_Q>L_P$, which implies that the code is not optimal. The optimal code for $Q$ is given by a simple enumeration of the elements of $X$; it is thus, impossible to compress that source. \bigskip \noindent {\bf 1-3.} \par \medskip \noindent (a) $H(X)=2$ bits. \par \medskip \noindent (b) Sequence of questions: \newline Did one obtain ``head'' with the first flip? \newline Did one obtain ``head'' with the second flip? \newline ... \newline Did one obtain ``head'' with the $n$th flip? \newline One can associate the answer to each question with a separate bit, and thus the answers to $n$ questions are encoded in $n$ bits. We obtain the expected number of ``yes/no'' questions: $\sum_{n=1}^{\infty}p(n)n=H(X)=2$. It is equal to the entropy, which shows that the sequence of questions is optimal. \newpage \bigskip \noindent {\bf 1-4.} \par \medskip \noindent (a) $H(Y)=H(X)=1.875$ bits, because the function is bijective (i.e. if one fixes $Y$, one knows $X$). \par \medskip \noindent (b) The function is not bijective. One obtains $H(Y)< H(X)$ with $H(X)=2.085$ bits and $H(Y)=1,325$ bits. \par \medskip \noindent (c) $H(X,f(X))=H(X)+H(f(X)|X)$ but $H(f(X)|X)=0$, because knowing $X$ fixes $f(X)$. \newline $H(f(X),X)=H(f(X))+H(X|f(X))$ but $H(X|f(X))\geq 0$. \newline Finally: $H(f(X),X)=H(X,f(X))$ implies $H(f(X))\leq H(X)$. \newline It is saturated if $H(X|f(X))=0$, i.e. if the function $Y=f(X)$ is bijective. \bigskip \noindent {\bf 1-5.} \par \medskip \noindent (a) Definition of the conditional entropy: $H(Y|X)=\sum_{x\in {{\mathcal{X}}}}p(x)H(Y|X=x)$. \[ H(Z|Y)=\sum_{y\in {{\mathcal{Y}}}}p(y)H(Z|Y=y)=\sum_{y\in {{\mathcal{Y}}}}p(y)H(X+Y|Y=y)=\sum_{y\in {{\mathcal{Y}}}}p(y)H(X|Y=y)=H(X|Y). \] If $X$ and $Y$ are independent, then $H(X|Y)=H(X)$. \newline As conditioning can only reduce the entropy: $H(Z|Y)\leq H(Z)$. \newline We finally obtain $H(X)\leq H(Z)$, and similarly $H(Y)\leq H(Z)$. \par \medskip \noindent (b) Example \newline \par \medskip \begin{tabular}{|cc|cccc|c|} \hline \multicolumn{2}{|c|}{P($X=x,Y=y$)} &\multicolumn{1}{c}{$Y=$$-1$} &\multicolumn{1}{c}{$-2$} &\multicolumn{1}{c}{$-3$} &\multicolumn{1}{c}{$-4$} &\multicolumn{1}{|c|}{P($X=x$)} \\ \hline $X=$ & $1$ & $1/4$ & $0$ & $0$ & $0$ & $1/4$ \\ & $2$ & $0$ & $1/4$ & $0$ & $0$ & $1/4$ \\ & $3$ & $0$ & $0$ & $1/8$ & $1/8$ & $1/4$ \\ & $4$ & $0$ & $0$ & $1/8$ & $1/8$ & $1/4$ \\ \hline & P($Y=y$) & $1/4$ & $1/4$ & $1/4$ & $1/4$ & $1$ \\ \hline \end{tabular} \medskip \newline Calculation of $H(X)$ and $H(Y)$: $\qquad H(Y)=H(X)=H(1/4,1/4,1/4,1/4)=\log_{2}4=2\,\mathrm{bits.}$ \newline One obtains ${{\mathcal{Z}}}=$\{$3,2,1,0,-1,-2,-3$\} with $P(Z=0)=3/4$, $P(Z=1)=1/8$ et $P(Z=-1)=1/8$ and the other probabilities are zero.\\ Calculation of $H(Z)$: $ \qquad H(Z)=-\frac{3}{4}\log_{2}\frac{3}{4}-\frac{1}{4}\log_{2}\frac{1}{8}=1.061\,\mathrm{bits.}$ \newline One verifies that $H(X)> H(Z)$ and $H(Y)> H(Z)$. \par \medskip \noindent (c) We require that $X$ and $Y$ are independent and that all $z_{i,j}=x_{i}+y_{j}$ are distinct for any couple $(i,j)$. If these conditions are satisfied one obtains $p_{z}(i,j)=p_{x}(i)p_{y}(j)$, which gives us the solution (after insertion in the defintion of $H(Z)$). \newline Example: ${\mathcal{X}}=\{1,2,3\}$ and ${\mathcal{Y}}=\{10,20,30,40\}$ for any probability distribution of $X$ and $Y$, where $X$ and $Y$ are independently distributed. \bigskip \noindent {\bf Optional.} \par \bigskip \begin{tabular}{|cc|ccc|c|} \hline \multicolumn{2}{|c|}{P($X,Y$)} &\multicolumn{1}{c}{$X=$ $-1$} &\multicolumn{1}{c}{$0$} &\multicolumn{1}{c}{$1$} &\multicolumn{1}{|c|}{P(Y)} \\ \hline $Y=$ & $-2$ & $0$ & $1/3$ & $0$ & $1/3$ \\ & $1$ & $1/3$ & $0$ & $1/3$ & $2/3$ \\ \hline P(X) & & $1/3$ & $1/3$ & $1/3$ & $1$ \\ \hline \end{tabular} \medskip \newline In this example, one verifies $\left\langle X\right\rangle=\left\langle Y\right\rangle=\left\langle XY\right\rangle=0$, thus $r=0$. \newline $H(X:Y)=H(X)+H(Y)-H(X,Y)=0.918$ bit. \end{document} Si on fait $k$ pes\'ees, pour quel nombre maximum de pi\`eces $n$ on peut d\'etecter une pi\`ece contrefaite? \newline le param\`etre $k=$ nombre de questions oui/non \`a poser, est born\'e par l'\'equation suivante: \[ H(X)\leq k \leq H(X)+1 \] o\`u $H(X)=\log_{2}n$. Cette entropie est celle qui va nous donner un nombre maximum de questions \`a poser pour $n$ donn\'e. \newline On souhaite une borne sup\'erieure pour $n \Longrightarrow k\leq H(X)+1$. \newline On obtient comme r\'esultat $n\leq 2^{k-1}$. \newline Exemple: avec $3$ questions on sait d\'eterminer la pi\`ece contrefaite dans un groupe de maximum 4 pi\`eces. \bigskip \noindent {\bf 1-7.} \par \medskip Cet exercice sera repris \`a la s\'eance $n^{o} 3$.