\documentclass[11pt]{article}   
\usepackage{fullpage}
\usepackage{amsfonts}

\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\vol}{\mathop{\rm Vol}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\renewcommand{\vec}[1]{{\mathbf #1}}
%\input{dansmacs}

\begin{document}

\noindent {\large Essential Coding Theory \hfill 
Madhu Sudan\\[-.1in]
6.896 \hfill  \mbox{}\\[-.1in]
Extended Due Date:  Wednesday, October 2, 2002\hfill \mbox{}\\[.4in]}
{\LARGE \centering Problem Set 2 \\[.4in] \par}

\paragraph{Instructions:} See PS 1.

\section*{Problems}

\begin{enumerate}
\item Prove the noiseless coding theorem, and its converse. 
	(But don't turn in.)
\item Consider a Markovian source of bits, where the source
	consists of a 6-cycle with three successive vertices
	outputing $0$, and three successive vertices outputting
	$1$, with the probability of either going left (or right) from
	any vertex is exactly $1/2$. Compute the rate of this
	source. (I expect an ab initio argument. Hopefully this 
	will motivate you to look up Shannon's general method
	for computing the rate of a Markovian source.)
\item Consider a binary channel whose input/output alphabet
	is $\{0,1\}$, where a $0$ is transmitted faithfully as
	a $0$ (with probability $1$), but a $1$ is transmitted as
	a $0$ with probability $\frac12$ and a $1$ with probability
	$1/2$. Compute the capacity of this channel. (You should
	prove this from scratch using only simple probabilistic
	facts already stated/used in class - not by referring to
	tools gleaned from other courses in information theory.
	For partial credit, you may just prove a lower bound on
	the capacity. The higher your bound, the more the credit.)
\item If there is a constructive solution to Shannon's
	noisy coding theorem with E being a linear map,
	then show that there is a constructive solution
	to Shannon's noiseless coding theorem in the case
	where the source produces a sequence of independent 
	bits of bias $p$.

      {\em Clarifications:} 
        \begin{enumerate}
	\item The encoding and decoding functions 
        used in the noiseless theorem should be polynomial time 
	computable, if the corresponding functions are polynomial
	time computable in the noisy theorem. 
	\item The compression rate in the noiseless coding theorem 
	should be arbitrarily close to $H(p)$, assuming the rate 
	of the encoding function in the coding theorem can be 
	made arbitrarily close to $1 - H(p)$.
	\end{enumerate}

\item Given codes $C_1$ and $C_2$ with encoding functions 
	$E_1:\{0,1\}^{k_1} \to \{0,1\}^{n_1}$
	and $E_2:\{0,1\}^{k_2} \to \{0,1\}^{n_2}$ let 
	$E_1 \otimes E_2: \{0,1\}^{k_1\times k_2} \to 
	\{0,1\}^{n_1\times n_2}$ be the encoding function obtained
	as follows: View a message $\vec m$ as a $k_1 \times k_2$ 
	matrix. Encode the columns of $\vec m$ individually using the
	function $E_1$ to get an $n_1 \times k_2$ matrix $\vec m'$.
	Now encode the rows of $\vec {m'}$ individually using $E_2$ to get
	an $n_1\times n_2$ matrix that is the final encoding under 
	$E_1 \otimes E_2$ of $\vec m$. Let $C_1 \otimes C_2$ be the
	code associated with $E_1 \otimes E_2$.

	For $i \geq 3$, let 
	$H_i$ denote the $[2^i-1,2^i-i-1,3]_2$-Hamming code.
	Let $C_i = H_i \otimes C_{i-1}$ with $C_3 = H_3$ be a
	new family of codes.

	\begin{enumerate}
	\item Give a lower bound on the relative minimum distance 
		of $C_i$.  Does it go to zero as $i \to \infty$?
	\item Give a lower bound on the rate of $C_i$. Does it go 
		to zero as $i \to \infty$?
	\item Consider the following simple decoding algorithm for 
      		$C_i$: Decode the rows of the rec'd vector recursively
      		using the decoding algorithm for $C_{i-1}$. Then decode
      		each column according to the Hamming decoding algorithm.
		Let $p_i$ denote the probability of decoding error of
		this algorithm on the Binary Symmmetric Channel with
		parameter $p$. 
		Show that there exists a $p > 0$ such that $p_i \to 0$
		as $i \to \infty$.
		(Hint: First show that $p_i \leq 4^i p_{i-1}^2$.)
	\end{enumerate}
\end{enumerate}

\end{document}