\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-451\hfill 2014-2015\\ 
\centering{
\textsc{\Large Information and Coding Theory}\\
Exercise Sheet 5}
}}

\section*{}
\begin{exercise}~\textbf{Channel with additive noise.}
We consider a memoryless channel with additive noise, with input $X$ and output
$Y = X+Z$, where $Z$ is a random variable with $P(Z=0)=P(Z=a)=\frac{1}{2}$, $a\in \mathbb{N}$. We assume that the alphabet of the input is ${\cal X}=\{0,1\}$ and that $Z$ is independent of $X$. Calculate the capacity of this channel as a function of $a$.
\end{exercise}

\begin{exercise}~We consider a memoryless channel $S$ with input $X=\{0,1,2,3\}$ and output $Y=X+Z {\rm ~(mod~4)}$, where $Z=\{-1,0,1\}$ with probabilities $\{\frac{1}{4},\frac{1}{2},\frac{1}{4}\}$, respectively. In addition, $X$ and $Z$ are independent.

\begin{enumerate}[(a)]
\item What is the probability distribution $p^*(x)$ that maximizes the mutual information?
\item Calculate the capacity of this channel.
\item Calculate the capacity of a channel system that consists of two concatenations of the channel.
\item Calculate the capacity of a channel system that consists of two times the channel in parallel. Compare the result with the results of (b) and (c).
\end{enumerate}
\end{exercise}

\begin{exercise}~We are given a noisy channel with a binary alphabet for the input and output, with transition matrix
$$
p(y|x)=\left( \begin{tabular}{c c}
1 & 0 \\
1/2 & 1/2
\end{tabular} \right)
\qquad\qquad x,y \in \{0,1\}.
$$
\par
\begin{enumerate}[(a)]
\item Calculate the capacity and the probability distribution $p^*(x)$ that attains this maximum.
\item Find the symmetric binary channel that gives the same capacity as the previous channel.
\item Calculate the capacity of a channel with transition matrix
\begin{equation*}
	p(y|x) =
	\begin{pmatrix}
		1 & 0\\
		1-q & q
	\end{pmatrix}, \qquad x,y \in \{0,1\}, q \in [0,1]
\end{equation*}
\end{enumerate}
\end{exercise}

\begin{exercise}~\textbf{Suboptimal codes.}
We reuse the channel of exercises 5-3 and consider a sequence of random error correction codes $(2^{nR},n)$, where each codeword is a sequence of $n$ equiprobable random bits.
\par
\begin{enumerate}[(a)]
\item This sequence does not attain the capacity that we have calculated above. Why?
\item Determine the maximal transmission rate $R$ for which the average error probability $P_e^{(n)}$ of the random codes tends to zero for a block length $n$ tending to infinity.
\end{enumerate}
\end{exercise}


\begin{exercise}~\textbf{Preprocessing of the output.} We consider a channel characterized by the transition matrix $p(y|x)$ and a given capacity $C$. We want to increase $C$ by introducing a ``preprocessing'' of the output, ${\tilde Y}=f(Y)$. The resulting channel is thus $X\to Y \to {\tilde Y}$, with capacity $\tilde{C}$.
\begin{enumerate}[(a)]
\item Show that ${\tilde C} \leq C$. What does this imply?
\item When does this preprocessing not decrease the capacity of the channel?
\end{enumerate}
\end{exercise}

%\noindent {\bf 5-6.} {\em Capacit\'e \`a erreur nulle.}
%Soit un canal dont l'alphabet d'entr\'ee et de sortie
%est $\{0,1,2,3,4\}$, et qui est caract\'eris\'e par la probabilit\'e
%de transition
%$$
%p(y|x)= \left\{ \begin{tabular}{ll}
%1/2 & si $y=x \pm 1$ ~mod~5 \\
%0 & sinon
%\end{tabular} \right.
%$$
%\par
%\medskip
%\noindent (a) Calculer la capacit\'e de ce canal.
%\par
%\medskip
%\noindent (b) On appelle ``capacit\'e \`a erreur nulle'' le nombre
%de bits qui peuvent \^etre transmis par usage du canal avec une
%erreur {\em strictement} \'egale \`a 0. Il est clair que, pour le canal
%pentagonal d\'ecrit ci-dessus, cette capacit\'e est au moins \'egale
%\`a 1 bit (il suffit par exemple d'envoyer les symboles 1 ou 2 avec
%une probabilit\'e 1/2 chacun). Montrer que la capacit\'e \`a erreur nulle
%de ce canal est en fait sup\'erieure \`a 1 bit. Dans ce but, trouver
%un code utilisant des blocs de longueur 2 plus performant que le code
%trivial ci-dessus.

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