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

\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\F}{{\mathbb F}}
\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]
Due:  Wednesday, October 30, 2002\hfill \mbox{}\\[.4in]}
{\LARGE \centering Problem Set 3 \\[.4in] \par}

\noindent {\bf Instructions:} See PS1.

\begin{enumerate}
\item {\sf Asymptotics of codes:} Given $\epsilon > 0$ express
the rate of the best family of binary codes of relative distance 
$\frac12 - \epsilon$,
you can (a) construct, and (b) show the existence of. Express
the rate in big-Oh notation (i.e., $O(\epsilon^d)$ implies there
exist constants $c$ and $\epsilon_0$ such that for all $\epsilon
< \epsilon_0$, the rate of the code of relative distance 
$\frac12-\epsilon$ is at least $c \epsilon^d$.)
How constructive are your codes in Part (a)?

\item {\sf Variants of RS codes:} 
The two parts of this question consider variants
of Reed-Solomon codes over $\F_q$, obtained by evaluations of
polynomials at $n$ distinct points $\alpha_1,\ldots,\alpha_n \in \F_q$.
The message will be speified by a sequence of coefficients 
$c_0,\ldots,c_{k-1} \in \F_q$ and its encoding will be the
evaluation of a polynomial $p(x)$ at $\alpha_1,\ldots,\alpha_n$.
What will be different is the definition of $p(x)$ given 
$c_0,\ldots,c_{k-1}$. Give exact bounds on the distance of the
resulting code. (Note, the distance may be a function of the
set $\{\alpha_1,\ldots.\alpha_n\}$.)
\begin{enumerate}
\item $p(x) = \sum_{i=0}^{k-1} c_i x^{i + \ell}$, where
$\ell$ is some non-negative integer.
\item $p(x) = \sum_{i=0}^{k-1} c_i x^{2i}$.
\end{enumerate}

\item {\sf Hadamard matrices:} Recall that an $n \times n$
matrix $H$ all
of whose entries are from $\{+1,-1\}$ is a Hadamard matrix if
$H \cdot H^T = n \cdot I$ where the matrix product is over the reals
and $I$ is the $n \times n$ identity matrix.
\begin{enumerate}
\item Show that if there is an $n x n$  Hadamard matrix 
	then $n$ is either $1$ or $2$ or a multiple of $4$.
\item Given an $n \times n$ Hadamard matrix $H_n$ and an 
	$m \times m$ Hadamard matrix $H_m$, construct an
	$(nm) \times (nm)$ Hadamard matrix.
\item (Not to be turned in) Let $q$ be a prime power equivalent
to $3$ modulo $4$. Let $H = \{h_{ij}\}$ be the $(q+1) \times (q+1)$ 
matrix with $h_{ij} = 1$ if $i = 1$ or $j = 1$ or $i = j$,
and $h_{ij} = (j-i)^{(q-1)/2}$ otherwise. Verify that $H$ is 
a Hadamard matrix. (The purpose of this exercise is point out that
Hadamard matrices of many size, and not just powers of $2$, exist.)
\end{enumerate}

\item Let $C$ be an infinite family of binary codes obtained
by concatenation of two infinite families of codes $C_1$ and $C_2$. 
(The $i$th code of $C$ is obtained by concatenating the $i$th
code of $C_1$ with the $i$th code in $C_2$. The block lengths of
the codes in $C_1$ and $C_2$ tend to infinity as $i \to \infty$.)
Give an upper bound on the rate of $C$ as a function of its
minimum distance.

\item Consider the following simple 
edit distance between strings: $x \in \Sigma^n$ is at distance
$d$ from $y \in \Sigma^m$ if $y$ can be obtained from $x$ by 
first deleting upto $d$ coordinates of $x$ and getting an
intermediate string $z \in \Sigma^{\ell}$ where $\ell \geq n-d$,
and then inserting up to $d$ characters into $z$ (at arbitrary 
locations) to get $y$. What are the analogs of the 
Singleton bound, the Hamming (packing) bound on codes, and the
Gilbert-Varshamov bounds for this measure of distance?
\end{enumerate}
\end{document}