\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}