%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% TPs Année 2001-2002
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\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$ 5}:}
\bigskip
\bigskip

\noindent {\bf 5-1.} {\em 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)=1/2$. We assume that the alphabet of the input is ${\cal X}=\{0,1\}$ and that the variable $Z$ is independent of $X$. Calculate the capacity of this channel as a function of the parameter $a$ (which is a whole number and $\ge 0$.).
\par
\bigskip

\noindent {\bf 5-2.} We consider a memoryless channel with input $X$, which takes values $0,1,2$ and $3$, and output $Y=X+Z {\rm ~(mod~4)}$, where $Z$ is a random variable which takes values $-1,0$ and $1$ with probabilities $1/4, 1/2$ and $1/4$, respectively. In addition, $X$ and $Z$ are independent.
\par
\medskip
\noindent (a) What is the probability distribution $p^*(x)$ that maximizes the mutual information?
\par
\medskip
\noindent (b) Calculate the capacity of this channel.
\par
\medskip
\noindent (c) Calculate the capacity of a channel system that consists of two concatenations of the channel.
\par
\medskip
\noindent (d) 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).
\par

\bigskip

\noindent {\bf 5-3.} 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
\medskip
\noindent (a) Calculate the capacity and the probability distribution $p^*(x)$ that attains this maximum.
\par
\medskip
\noindent (b) Find the symmetric binary channel that gives the same capacity as the previous channel.
\par
\medskip
\noindent (c) 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}
\par

\bigskip

\noindent {\bf 5-4.} {\em Suboptimal codes.}
We consider again the channel of exercises 5-3. We chose a sequence of random error correction codes $(2^{nR},n)$, for which each codeword is a sequence of $n$ equiprobable random bits.
\par
\medskip
\noindent (a) This sequence does not attain the capacity (which was calculated previously). Why?
\par
\medskip
\noindent (b) 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.
\par


\bigskip
\newpage

\noindent {\bf 5-5.} {\em Pre-treatment of the output.} We consider a channel characterized by the transmition matrix $p(y|x)$ and a given capacity $C$. We decide to increase this capacity by introducing a ``pre-treatment'' of the output, ${\tilde Y}=f(Y)$. The resulting channel is thus $X\to Y \to {\tilde Y}$.
\par
\medskip
\noindent (a) Show that ${\tilde C} >C$ is impossible and that thus, this method does not work.
\par
\medskip
\noindent (b) In which case does this pre-treatment not decrease the capacity of the channel?
\par

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


%\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.


\end{document}