%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TPs Année 2000-2001
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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 Exercise sheet n$^\circ$ 4}:}
\bigskip
\bigskip



\noindent {\bf 4-1.} {\em Lempel-Ziv code.}
\par
\noindent (a) Consider a source with alphabet $\{\mathtt{A}, \mathtt{B}, \mathtt{C}, \mathtt{\_} \}$. Encode the sequence $\mathtt{AA\_ABABBABC\_ABABC}$ with the Lempel-Ziv code. Establish a method to encode the position, and calculate the number of bits that are necessary to transmit this sequence compressed by Lempel-Ziv. What do you encounter at the last $ABC$? What would you encounter if the sequence was $\mathtt{AA\_ABABBABC\_ACABC}$?
\par
\noindent (b) Consider a source with alphabet $\{\mathtt{A},\mathtt{B} \}$. Encode the sequence $\mathtt{ABAAAAAAAAAAAAAABB}$ with the Lempel-Ziv code. Calculate the number of bits necessary to transmit the sequence compressed by Lempel-Ziv and compare it with a naive encoding.
\par
\noindent (c) Consider a source with alphabet $\{\mathtt{A},\mathtt{B}\}$. Encode the sequence $\mathtt{ABAAAAAAAAAAAAAAAAAAAA}$ with the Lempel-Ziv code. Calculate the number of bits necessary to transmit the sequence compressed by Lempel Ziv and compare it with a naive encoding.
\par
\medskip
\noindent (d) The following is the encoded sequence that is obtained by using the Lempel-Ziv code. Reconstruct the original sequence.
\begin{center}
$0, \mathtt{A}$ \\
$1, \mathtt{B}$ \\
$2, \mathtt{C}$ \\
$0, \mathtt{\_}$ \\
$2, \mathtt{B}$ \\
$0, \mathtt{B}$ \\
$6, \mathtt{B}$ \\
$7, \mathtt{B}$ \\
$0, \mathtt{.}$
\end{center}

\par
\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\noindent {\bf 4-2.} Each object of an ensemble of $n$ objects can either be faulty or not. The random variable $X_i$ is either 1 or 0, respectively, if the $i$-th object is faulty or not. We assume that the variables $X_1$, $X_2, \cdots ,X_n$ are independent, with ${\rm Prob}\{X_i=1\}=p_i$ and $p_1>p_2>\cdots >p_n>1/2$.
The problem is to determine the ensemble of all faulty objects with a method that is optimal.
\par
\medskip
\noindent (a)
How can one find the optimal sequence of yes/no-questions that determines all objects that are faulty?
\par
\medskip
\noindent (b)
What is the last question that has to be asked? Which two ensembles can one distinguish with this question?
\par

\newpage
\bigskip
\noindent {\bf 4-3.} A player $A$ choses an object from an ensemble and a player $B$ tries to identify this object with a series of yes/no-questions. We assume that player $B$ uses an optimal code (which gives the minimal expected length) with respect to the distribution of objects of player $A$. One observes that, on average, player $B$ needs to ask 35 questions to determine the object chosen by $A$. Find a lower bound on the number of objects of the ensemble.
\bigskip
\bigskip

\noindent {\bf 4-4.} One is given $n$ coins, where one of them can be counterfeited. A counterfeited coin is either heavier or lighter then an authentic one. In order to find the counterfeited coin, all coins are weighed.
\bigskip
\par
\medskip
\noindent (a) What is the probability distribution of the counterfeited coin that maximizes the Shannon entropy? Treat the existence or non-existence of a counterfeited coin as an extra element in the probability distribution.
\par
\medskip
\noindent (b) Establish the equation that bounds from below and above the expected number of weighs, if one uses an optimal method.
\par
\medskip
\noindent (c) Deduce the maximal number of coins $n$, given an average number of weighs $k$.
\par
\medskip
\noindent (d) Show that this maximum can be attained.
\par
\bigskip
\bigskip

\noindent {\bf 4-5.} A random variable $X$ can take $m$ possible values and has an entropy $H(X)$. Suppose one is given an instantaneous code $C$ for the source $X$, which has an expected length $L(C)=H(X)/\log_2 5=H_5(X)$.
\par
\medskip

\noindent (a) Show that each symbol of $X$ has a probability of the form $5^{-n}$, where $n$ is a whole number.
\par
\medskip
\noindent (b) Show that $m$ has to satisfy $m=4k+1$ where $k$ is a whole number.
\par

\bigskip
\centerline {\underline{\Large Web site}:}
\bigskip
http://quic.ulb.ac.be/teaching/

\bigskip
\end{document}