
\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$.




 

