\documentclass[a4paper,11pt]{article}

\usepackage{amsmath}
\usepackage{amstext}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{braket}
\usepackage{graphicx,subcaption}
\usepackage[percent]{overpic}
\usepackage{bbm}
\usepackage{bm}
\usepackage{threeparttable}
\usepackage{tabularx}
\usepackage{multirow}
\usepackage{booktabs}
\usepackage[nohyperlinks]{acronym}
\usepackage{microtype}
\usepackage{pifont}
\usepackage{pdfpages,diagbox}
\usepackage[utf8]{inputenc}
\usepackage[labelformat=empty,labelsep=none]{caption}
\usepackage{enumerate}
\usepackage{hyperref}
\definecolor{ulbblue}{cmyk}{1,0.75,0.2,0.18}
\hypersetup{colorlinks,
  citecolor=ulbblue,
  linkcolor=ulbblue,
  urlcolor=ulbblue
}

\makeatletter
\renewcommand\@pnumwidth{1.8em}
\makeatother

\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage{fix-cm}
\usepackage[charter,cal=cmcal,sfscaled=false]{mathdesign}

\usepackage[paper=a4paper,innermargin=4cm,outermargin=3cm,top=3.5cm,bottom=3.5cm]{geometry}
\setlength{\headheight}{13.6pt}
\usepackage{setspace}
\usepackage[PetersLenny]{fncychap}
\usepackage{fancyhdr}



\theoremstyle{definition}
\newtheorem{exercise}{Exercise}


\setlength {\textheight}{26 cm} \setlength {\textwidth}{16.5 cm}
\setlength {\topmargin}{-2 cm} \setlength {\oddsidemargin}{-0.4 cm}

\begin{document}
\noindent
\fbox{\parbox{\textwidth}{
INFO-H-422\hfill 2016-2017\\ 
\centering{
\textsc{\Large Information and Coding Theory}\\
Exercise Sheet 3}
}}

\section*{}
\begin{exercise}~\textbf{Data compression}. 
Determine whether the following codes are nonsingular, uniquely decodable or instantaneous:
\begin{enumerate}[(a)]
\item The code $\{0,0\}$.
\item The code $\{0,010,01,10\}$.
\item The code $\{10,00,11,110\}$.
\item The code $\{0,10,110,111\}$.
\end{enumerate}
\end{exercise}

\begin{exercise}~We consider a source $\{ x_i, p_i \}$ with $i=1,\cdots,m$. The symbols $x_i$
(emitted with probabilities~$p_i$) are encoded in sequences using an alphabet of
cardinality $D$, such that the decoding is instantaneous. For $m=6$ and lengths
of the codewords $\{l_i\}=\{1,1,1,2,2,3\}$, find a lower bound for $D$. Is this
code optimal?
\end{exercise}

\begin{exercise}~\textbf{Huffman code}. A source emits a random variable $X$ which can take four values with probabilities $\left\{{1\over 10},{2\over 10},{3\over 10},{4\over 10}\right\}$.
\begin{enumerate}[(a)]
\item Construct a binary Huffman code for $X$.
\item Construct a ternary Huffman code for $X$.
\item Construct a binary Shannon code for $X$ and compare its expected length with the code of~(a).
\end{enumerate}
\end{exercise}

\begin{exercise}~\textbf{Huffman code}. A source emits a random variable $X$ which can take four values with probabilities $\left\{{1\over 3},{1\over 3},{1\over 4},{1\over 12}\right\}$.
\begin{enumerate}[(a)]
\item Construct a binary Huffman code for $X$.
\item Construct a binary Shannon code for $X$ and compare it with the code of (a).
\end{enumerate}
\end{exercise}

\begin{exercise}~We have a non-balanced coin with probability $p$ to obtain ``head'' (``1'') 
and probability $1-p$ to obtain ``tail'' (``0''). Alice flips this coin as many times as needed to obtain ``head'' for the first time, and would like to communicate to Bob the number of flips $k$ that were needed. A naive method is to send to Bob the sequence of the outcomes of the coin flips encoded in a chain of bits of length $k$, like $000\cdots01$ (where 0 stands for ``tail'' and 1 for ``head'').
\begin{enumerate}[(a)]
\item What is the expected length of this naive code? Compare it with
the entropy of the random variable $k$. In which case the naive code is optimal? 
Use
\begin{align*}
\sum_{i=0}^\infty a^i&={1\over 1-a}\\
\sum_{i=0}^\infty i\, a^i&={a\over (1-a)^2 }
\end{align*}
\item Alice decides now to encode her random variable $k$ with a Shannon
code, with the aim to approach $H(k)$. Compare the
expected lengths of the naive code and the Shannon code in the limit $p\to 0$.
\end{enumerate}
\end{exercise}

\section*{}
\centering \textbf{\color{ulbblue}{The exercises and solutions are available at} \url{http://quic.ulb.ac.be/teaching}}
\end{document}