%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TPs Ann� 2002-2003 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \voffset -2.8 cm \textwidth 17 cm \textheight 24.7 cm \oddsidemargin -.54 cm \evensidemargin -1.54 cm \pagestyle{plain} \begin{document} \centerline {\Large \sc Information and coding theory} \bigskip \bigskip \hrule \bigskip \bigskip \centerline {\underline{\Large Exercise sheet n$^\circ$ 1}:} \bigskip \bigskip \noindent {\bf 1-1.} A discrete random variable $X$ has a uniform probability distribution $p(x)$ over the set ${\mathcal{X}}$ of cardinality $|{\mathcal{X}}|=m$. \par \medskip \noindent (a) Give an example for ${\mathcal{X}}$ and calculate $p(x)$ for $x \in {\mathcal{X}}$. \par \medskip \noindent (b) Determine the entropy $H(X)$. If $m=64$, what is $H(X)$? \par \medskip \noindent (c) How many bits are needed to enumerate the alphabet ${\mathcal{X}}$ without encoding, where $m=64$? \par \medskip \noindent (d) How many symbols taken from a quaternary alphabet are necessary to enumerate the alphabet ${\mathcal{X}}$ without encoding, where $m=64$? \par \medskip \noindent (e) Show that $H(X)$ is greater than the entropy of any other random variable $Y$, where $Y$ has values on the same set $\mathcal{X}$. {\it (Read the recall on Lagrange multipliers.)} \bigskip \noindent {\bf 1-2.} A random variable $X$ has an alphabet ${\mathcal{X}}=\{A,B,C,D\}$. \par \medskip \noindent (a) Calculate $H(X_P)$ associated to probabilities \newline $P(X)=\{1/2,1/4,1/8,1/8\}$. \par \medskip \noindent (b) Calculate $H(X_Q)$ associated to probabilities $Q(X)=\{1/4,1/4,1/4,1/4\}$. \par \medskip \noindent (c) We define a binary code: \newline \{C($X=A$)=0, C($X=B$)=10, C($X=C$)=110, C($X=D$)=111\}. \newline Calculate the expected length (in bits) of the codewords of $X$ are distributed according to $P(X)$ and $Q(X)$ \par \medskip \noindent (d) Compare the four obtained results. \bigskip \noindent {\bf 1-3.} A coin (with same probability for ``head'' or ``tail'') is flipped repeatedly until one obtains ``head''. Let the random variable $X$ be given by the number of flips until one obtains ``head'' for the first time. \par \medskip \noindent (a) Calculate $H(X)$. \par \medskip \noindent (b) One repeatedly flips the coin until ``head'' is obtained for the first time. Find a sequence of questions of type ``yes/no'' to determine the value of $X$. Compare the entropy of $X$ with the expected length of the sequence of questions necessary to fully determine $X$. \par \medskip \noindent {\it Note:} \begin{eqnarray*} \sum_{n=1}^\infty r^n={r\over 1-r}, \qquad \sum_{n=1}^\infty n r^n={r\over (1-r)^2}, \qquad r < 1. \end{eqnarray*} \newpage \noindent {\bf 1-4.} Assume $X$ and $Y$ to be random variables. What is the inequality relating $H(X)$ and $H(Y)$ if, \par \medskip \noindent (a) $Y=2^X$, with ${\mathcal{X}}=\{0,1,2,3,4\}$ associated to probabilities $\{1/2,1/4,1/8,1/16,1/16\}$. \par \medskip \noindent (b) $Y=\cos(X)$, with ${\mathcal{X}}=\{0,\pi/2,\pi,3 \pi/2,2 \pi \}$ associated to probabilities $\{1/3,1/3,1/12,1/12,1/6\}$. \par \medskip \noindent (c) Show that the entropy of any function $f(X)$ of the random variable $X$ is less or equal than the entropy of $X$. In order to prove this, it is useful to calculate the join entropy $H(X,f(X))$. In which case the inequality $H(f(X)) \le H(X)$ is saturated? \par \bigskip \noindent {\bf 1-5.} Let $X$ and $Y$ be two random variables, taking values $x_1,x_2,\cdots, x_r$ and $y_1,y_2,\cdots, y_s$. Furthermore, we define a random variable $Z=X+Y$. \par \medskip \noindent (a) Show that $H(Z|Y)=H(X|Y)$ and $H(Z|X)=H(Y|X)$. Deduce that if $X$ and $Y$ are independently distributed, then $H(X)\le H(Z)$ and $H(Y)\le H(Z)$. Thus, summing two random variables can only increase the uncertainty. \par \medskip \noindent (b) Give an example for $X$ and $Y$ (necessarily correlated) such that $H(X)>H(Z)$ and $H(Y)>H(Z)$. \par \medskip \noindent (c) In which case the equality $H(Z)=H(X)+H(Y)$ is satisfied? \par \bigskip \noindent {\bf Optional:} Give an example of a distribution of two random variables $X$ and $Y$ whose correlation coefficient is zero, although they are not independent. Show that in this case $H(X{\rm:}Y) \ne 0$, showing that the mutual entropy is a better measure of the dependence of $X$ and $Y$. \medskip Correlation coefficient: $r=\frac{-}{\sqrt{-^{2}}\sqrt{-^{2}}}$ \medskip \par \bigskip \bigskip \bigskip \centerline {\underline{\Large Recall}:} \bigskip \begin{enumerate} \item Change of the base of logarithms \medskip \newline $\log_{a}N=\log_{b}N/\log_{b}a$ \item Lagrange theorem: \begin{itemize} \item We want to maximize \newline $u(x_{1},x_{2},...,x_{n})$ with $k$ constraints $g_{j}(x_{1},x_{2},...,x_{n})=a_{j}$, $j=1,\cdots,k$. \item We introduce the Lagrangian: \newline $ L(x_{1},...,x_{n},\lambda_{1},...,\lambda_{k})=u(x_{1},x_{2},...,x_{n})+\sum_{j=1}^{k}\lambda_{j}[a_{j}-g_{j}(x_{1},x_{2},...,x_{n})]. $ \item Condition on an extremum: \newline $\forall i, \frac{\partial L}{\partial x_{i}}=0.$ \item If $u$ is concave, the solution is a maximum. \end{itemize} \end{enumerate} \bigskip \centerline {\underline{\Large Web site}:} \bigskip http://quic.ulb.ac.be/teaching/ \end{document} % \noindent {\bf 1-7.} On dispose de $n$ pi\`eces de monnaie dont l'une d'entre % elles peut \'eventuellement \^etre contrefaite. % Une pi\`ece contrefaite se reconna\^\i t par le fait qu'elle est soit % l\'eg\`erement plus lourde, soit l\'eg\`erement plus l\'eg\`ere qu'une % pi\`ece authentique. Afin de d\'eterminer s'il y a contrefa\c con, % les pi\`eces sont pes\'ees. % \par % \medskip % \noindent (a) Quelle est la distribution de probabilit\'e de la pi\`ece contrefaite qui maximise l'entropie se Shannon. % Traiter l'existance ou non de pi\`ece contrefaite comme un \'el\'ement de plus de la distribution de probabilit\'e. % \par % \medskip % \noindent (b) \'Etablir l'\'equation qui borne inf\'erieure et sup\'erieurement le nombre de pes\'ees en moyenne. % \par % \medskip % \noindent (c) Sachant que la distribution de probabilit\'e est 2-adique. % Obtenir une borne sup\'erieure du nombre de pi\`eces $n$ % tel que $k$ pes\'ees en moyenne suffisent pour trouver la pi\`ece contrefaite, s'il y en a. % \par %