\begin{center}
{\large\bf Exercise sheet 09 -- 13.06.2024}
\end{center}
\hrule
\bigskip

\setcounter{bsp}{38}	% gleich der Nummer des letzten Beispiels des letzten Übungszettels

\begin{bsp}
  Let $\mathcal{X} = \{a, b, c, d, e, f, g, h\}$. 
  \begin{enumerate}
    \item Give an example of a prefix code $C : \mathcal{X} \to \{0,1\}^*$ with code word lengths
     \[\begin{split} 
     &\ell(C(a)) = \ell(C(b)) = \ell(C(c)) = 2, \; \ell(C(d))=3, \\  
     &\ell(C(e)) = \ell(C(f)) = \ell(C(g)) = 5, \; \ell(C(h))=6.
     \end{split}\]
    \item Show that the Kraft inequality is a strict inequality for this code, that is, 
      \[\sum_{x \in \mathcal{X}} 2^{-\ell(C(x))} < 1.\]
    \item Find a binary sequence of length 6 which cannot be decoded.
    \item Find a prefix code $C : \mathcal{X} \to \{0,1\}^*$ such
      that we have equality in the Kraft inequality.
    \item Find a probability distribution for a random variable $X: \Omega \rightarrow \mathcal{X}$ such that your code is optimal and compare the expected code length with $H(X)$.
  \end{enumerate}
\end{bsp}

\begin{bsp}\label{ex:huffman}
  Consider the random variable $X : \Omega \to \{x_1, \dots, x_{10}\}$ with probability distribution 
  \[
    p=(\, 0.25,\, 0.10,\, 0.13,\, 0.15,\, 0.03,\, 0.05,\, 0.04,\, 0.15,\, 0.08,\, 0.02\,).
  \]
 In a $D$-ary Huffman code at each step we choose $D$ nodes with the lowest probability and construct their parent with probability the sum of the probabilities of the children. Only at the first step we may merge less than $D$ children: 
	given that $ |\mathcal{X}| = N$, at the first step we build the parent of $k = 2+(N-2) \!\! \! \mod  \! (D-1)$ children. For example, for $N=19$ and $D=5$ we get $k = 2+ 17 \!\!\mod  4 = 3$.
  \begin{enumerate}
    \item Build a binary Huffman code.
    \item Compute the expected code length of your code and compare it to $H(X)$.
    \item Build a ternary Huffman code over the alphabet $\Sigma=\{0,1,2\}$.
    \item Compute the expected code length of your code and compare it to 
      \[
      H_3(X)=-\sum_{x \in \mathcal{X}} p(x) \log_3(p(x)).
      \]
  \end{enumerate}
\end{bsp}

\begin{bsp}
Let $X,Y$ be random variables with values in $\mathcal{X}=\mathcal{Y}=\{0,1\}$ and let $p_X(0)=q$, $p_X(1)=1-q$. Let $\mathcal{C}=(\mathcal{X},P,\mathcal{Y})$ be the channel with input $X$, output $Y$ and transition matrix
\[ 
P=
\left[
\begin{array}{cc}
 1-p & p      \\
 p & 1-p 
\end{array}
\right].
\]
\begin{enumerate} 
    \item Compute $I(X,Y)$ in terms of $p$ and $q$.
    \item For which values of $p$ is $I(X;Y)$ maximal?
    \item For which values of $p$ is $I(X;Y)$ minimal?
\end{enumerate}
\end{bsp}
\newpage 
\begin{bsp}
    Consider the channel with input $X$ and output $Y=XZ$ where $X$ and $Z$ are independent binary random variables taking values $0$ and $1$. Let $\alpha=\Prob[Z=1]$.
    \begin{enumerate}
        \item Find the capacity of this channel and the distribution on $X$ maximising $I(X;Y)$.
        \item Now suppose the receiver can observe $Z$ as well as $Y$. What is the capacity?
    \end{enumerate}
\end{bsp}