\begin{center}
{\large\bf Exercise sheet 11 -- 14.06.2023}
\end{center}
\hrule
\bigskip

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

\begin{bsp}
    Consider a binary symmetric channel $\Ccal$ with input and output $\{0,1\}$ and crossover probability $p(1 \mid 0)=p(0 \mid 1)=0.1$. To reduce the error probability, we encode 0 as 000 and 1 as 111, send these three bit words through the channel and then decode the received three bit words by majority (for example, 010 will be decoded as 0). With this coding scheme we can consider the combination of encoder, channel and decoder as a new binary symmetric channel $\Ccal'$.
    \begin{enumerate}
        \item Calculate the crossover probability of $\Ccal'$
        \item Compare the capacity of $\Ccal'$ to the capacity of $\Ccal$.
        \item Show that for any channel $\Ccal$, considering the encoder, channel and decoder as a new channel $\Ccal'$ will not increase the capacity in bits per transmission of the original channel.
    \end{enumerate}
\end{bsp}

\begin{bsp}
Given a channel $\mathcal{C}=(\mathcal{X},P,\mathcal{Y})$ suppose we form a new channel $\mathcal{C}'$ by transmitting the same message $X$ across the channel twice, resulting in an output $(Y_1,Y_2)$ where $Y_1$ and $Y_2$ are conditionally independent and conditionally identically distributed given $X$.
\begin{enumerate}
    \item Show that
    \[
    I(X;Y_1,Y_2) = 2I(X;Y_1) - I(Y_1;Y_2).
    \]
    \item Conclude that $\text{cap}(\mathcal{C}') \leq 2\text{cap}(\mathcal{C})$.
\end{enumerate}
\end{bsp}

\begin{bsp}
\label{ex:sumchannel}
Consider the channel $\Ccal=(\Xcal,P,\Ycal)$ with input and output $\mathcal{X}=\mathcal{Y}=\{0,1,2,3\}$ and with probability transition matrix
\[ P=
    \left[
    \begin{array}{cccc}
     1-q_1 & q_1 & 0 & 0  \\
     q_1 & 1-q_1 & 0 & 0 \\
    0 & 0 & 1-q_2 & q_2 \\
    0 & 0 & q_2 & 1-q_2     
    \end{array}
    \right]\, .
\]
\begin{enumerate}
    \item Find the capacity for this channel if $q_1=q_2=\sfrac{1}{2}$
    \item Let $p_X(x)$ be the input distribution and suppose that $p_X(0)+p_X(1)=p$. Show that the mutual information between the input $X$ and the output $Y$ is 
    \[
    I(X;Y)=H(p,1-p)+ p I(X;Y \mid X \in \{0,1\})+(1-p) I(X;Y \mid X \in \{2,3\}).
    \]
\end{enumerate}
\end{bsp}

\begin{bsp}
    Consider again the channel $\Ccal=(\Xcal,P,\Ycal)$ from Exercise \ref{ex:sumchannel} and let $C_1$ and $C_2$ be the capacities of the two binary symmetric channels with error probabilities $q_1$ and $q_2$, respectively.
    \begin{enumerate}
        \item Show that 
        \[
        \max_{p_X( \,\cdot\,)} I(X;Y)= \max_{p \in [0,1]}(H(p,1-p) + p C_1 + (1-p) C_2).
        \]
        \item Find the capacity $C$ of the channel $\Ccal$ in terms of the capacities $C_1$ and $C_2$ and no other parameters. 
    \end{enumerate}
\end{bsp}



\begin{bsp}
Consider a channel with binary inputs that has both errors (with probability $\epsilon$) and erasures (with probability $\alpha$), and so has transition matrix
\[
P = \begin{pmatrix}
    1-\alpha-\epsilon &\epsilon &\alpha\\
    \epsilon & 1-\alpha-\epsilon& \alpha
\end{pmatrix}.
\]
Find the capacity of this channel.
\end{bsp}

