\documentclass[10pt]{article}
\input{../preamble.tex}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\newcommand{\Z}{{\mathbb Z}}
\newcommand{\bit}{\set{0,1}}
\newcommand{\Ball}[2]{\mathit{Ball}(#1,#2)}
\newcommand{\Vol}[2]{\mathit{Vol}_{2}(#1,#2)}
\newcommand{\length}[1]{\left\vert #1 \right\vert}
%\newcommand{\wt}[1]{\mathit{wt}\left( #1 \right)}
\usepackage{psfig}
\usepackage{epsfig}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\lecture{5}{September 18, 2002}{Madhu Sudan}{Jonathan Herzog}
%%%% body goes in here %%%%
\section{Overview}
\label{sec:overview}
\begin{itemize}
\item Existence of asymptotically good codes
\item Gilbert codes / Random codes
\item Vashamov codes / Random linear codes
\item Bounds
\item Wozencraft ensemble of codes
\end{itemize}
\section{Random codes}
\label{sec:random-codes}
So far, we have seen a number of codes, but we would like an
asymptotically good one. To review, an asymptotically good code is a
family of codes, indexed by the block length ($n$) where:
\begin{itemize}
\item $\frac{k}{n} \geq R > 0$ and
\item $\frac{d}{n} \geq \delta > 0$
\end{itemize}
and $R$ and $\delta$ are both constants. That is, we would like a code
with a rate ($R$) and a minimum distance ($\delta$) constant relative
to the block length. Can we show that such codes exist? Yes, by
examining \emph{random} codes:
\begin{theorem}[Gilbert]
There exists a code with a constant $\delta$ and a constant rate $R
\geq 1 - H_2(\delta)$.
\end{theorem}
\begin{proof}
Consider a random code with block size $n$ and minimum distance $d$,
constructed according to the following algorithm:
\begin{enumerate}
\item Let $S \leftarrow \bit^n$.
\item Let $C \leftarrow \emptyset$.
\item While $S \not = \emptyset$, do:
\begin{itemize}
\item Pick $x$ randomly (uniformly) from $S$.
\item Let $C \leftarrow C \cup \set{x}$
\item Let $S \leftarrow S \setminus \Ball{x}{d-1}$
\end{itemize}
\end{enumerate}
(Here, $\Ball{x}{d-1} = \set{y \in S| \Delta(x,y)\leq d-1}$, and
$\Vol{n}{d-1}$ is the number of points in $\Ball{x}{d-1}$.)
Let $C$ be a code produced by the above algorithm. How large will $C$
be? Each time you add a codeword, you remove at most $\Vol{n}{d-1}$
elements from $S$:
$$\length{C} \geq \frac{2^n}{\Vol{n}{d-1}}$$
If $\delta = \frac{d}{n}$ for a family of codes, then $\Vol{n}{d-1}
\approx 2^{H_2(\delta)n}$. In which case
$$\length{C} \geq 2^{n(1-H_2(\delta))}$$
If $\length{C} = 2^k$, then $2^k \geq 2^{n(1-H_2(\delta))}$, or $k \geq
n(1-H_2(\delta))$. Hence, there exists a code $C$ so that
$$R \geq 1 - H_2(\delta).$$
\end{proof}
\section{Bounds}
\label{sec:bounds}
How does this relate to the Hamming Bound? The Hamming bound tells us
that if $C$ is a code with distance $d$, then
$$\length{C} \leq \frac{2^n}{\Vol{n}{\frac{d-1}{2}}}$$
(In the
asymptotic case, $R \leq 1 - H_2(\frac{\delta}{2})$.) In other words,
we know we can achieve a code with $\Vol{n}{d-1}$ in the denominator,
and the Hamming bound tells us that we can do no better than
$\Vol{n}{\frac{d-1}{2}}$ in the denominator. Halving the radius
reduces the volume of the sphere dramatically, leading to a large gap
between this bound and the bound from the Gilbert proof. Figure
\ref{fig:bounds} plots these bounds as a function of $R$ and $\delta$.
The Gilbert proof above shows that there are codes on and to the left
of the Gilbert bound. (Any code \emph{on} the Gilbert bound which is
not also on an axis is an asymptotically good code.) Hamming showed
that there do not exist codes to the right of the Hamming bound. The
area in between is still open.
\begin{figure}[t]
\begin{center}
\epsfig{file=plot.eps,width=4in,angle=270}
\caption{Bounds on $R$ and $\delta$}
\label{fig:bounds}
\end{center}
\end{figure}
\section{Random Linear Codes}
\label{sec:random-linear-codes}
\begin{theorem}[Vashamov]
Suppose that $2^k -1 \leq \frac{2^n}{\Vol{n}{d-1}}$. Then there
exists a linear code $C$ with a minimum distance $d$ and so that
$$\length{C} \geq \frac{2^n}{\Vol{n}{d-1}}$$
\end{theorem}
\begin{proof}
Pick $G \in \bit^{k\times n}$ at random. Then let $C = \set{xG \vert
x \in \bit^k}$. To show that $C$ has minimum distance $d$, it
suffices to show that $\wt(xG) \geq d$ for all $x \not = \vec{0}$.
Fix an $x \not = \vec{0}$. Then
$$\Pr_G \left[\wt(xG) < d\right] = \frac{\Vol{n}{d-1}}{2^n}$$
Hence, via union bound:
\begin{eqnarray*}
\Pr_G \left[\exists x \not = \vec{0} \mbox{ s.t. } \wt(xG) <
d\right] &=& \frac{\left(2^k-1\right)\Vol{n}{d-1}}{2^n}\\
&<&1
\end{eqnarray*}
Hence, there exists a $G$ so that $\wt(xG) < d)$ for all non-zero
$x$, and so $C$ is a linear code with minimum distance at least $d$.
\end{proof}
\section{Bounds, revisted}
\label{sec:bounds-revisted}
Can we do better than the Gilbert-Vashamov bound for, at least for
specific $n$, $k$ and $d$? Yes, we've already seen codes that do
better. However, asymptotically, they exist on the \emph{axises} of
the diagram in Figure~\ref{fig:bounds}.
\begin{description}
\item[Hamming codes] If we let $d=3$, then the Gilbert-Vashamov
construction gives a lower bound on the number of codewords as:
$$\length{C} \geq \frac{2^n}{\Vol{n}{2}} = \frac{2^n}{1 + n + {n
\choose 2}} \approx \Theta\left(\frac{2^n}{n^2}\right)$$
We know
that Hamming codes actually do better than this: $\length{C} =
\frac{2^n}{n+1}$. Asymptotically, however, $d$ is constant and so
$\delta$ goes to 0 as $n$ gets large. Hence, Hamming codes are not
asymptotically good.
\item[Hadamard codes] With these codes, $n=2^k$ and $d =
\frac{n}{2}$. So asymptotically, $R = \frac{k}{n}$ goes to 0 as $n$
gets large and Hadamard codes are not asymptotically good. However,
$$\Vol{n}{\frac{n}{2}} \approx 2^{n-1},$$
and hence the Gilbert-Vashamov bound gives
$$\length{C} \geq \frac{2^n}{\Vol{n}{\frac{n}{2}}} \approx 2$$
and we know that Hadamard codes do \emph{much} better than this.
\item[BCH codes] If you fix $d$ and let $n \rightarrow \infty$, then BCH
codes have $\Theta\left( \frac{2^n}{n^{\frac{d-1}{2}}}\right)$
codewords. The Gilbert-Vashammov bound gives that it will have at
least $\Theta\left( \frac{2^n}{n^{d-1}}\right)$ codewords, a very
loose bound.
\item[Reed-Solomon Codes] In a $q$-ary construction, the greedy
Gilbert-Vashamov bound implies that there are codes such that
$$k \geq n- d - \Theta\left(\frac{n}{\log q}\right).$$
Reed-Solomon codes, it turns out, are such that
$$k \geq n- d - 1,$$
a much better result. (Also, there are codes from algebraic geometry
such that
$$k \geq n- d - \Theta\left( \frac{n}{\sqrt{q}}\right),$$
also a better result.)
\end{description}
Hence, is the Gilbert-Vashamov result tight? Madhu doesn't think so.
However, all the ``counterexamples'' above lie on the $R$- or
$\delta$-axis of Figure~\ref{fig:bounds}. Hence, they are not
asymptotically good codes, and are not \emph{direct} counterexamples
to the bound.
\section{Wozencraft Ensamble of Codes}
\label{sec:wozencraft-ensambles}
We would like to make the Gilbert-Vashamov ``constructions'' more
deterministic, if possible. So much, in fact, that we are willing to
accept an exponential ($2^{0(n)}$-time) algorithm to create a good
linear code.
As a first step to that end, we consider \emph{Wozencraft ensambles}
of linear codes:
\begin{definition}
The space $\bit^n$ is \emph{packed} with linear codes $C_1$, $C_2$,
\ldots $C_t$ (each having $2^k$ elements) if:
\begin{enumerate}
\item For all $i \not = j$, $C_i \cap C_j = \set{\vec{0}}$, and
\item $\bigcup_i C_i = \bit^n$.
\end{enumerate}
\end{definition}
Note that if $C_1$, $C_2$, \ldots $C_t$ pack $\bit^n$, then
$t =\frac{2^n -1}{2^k-1}$.
\begin{theorem}
If $C_1$, $C_2$, \ldots $C_t$ pack $\bit^n$ and $\epsilon t \geq
\Vol{n}{d-1}$, then more than an $(1-\epsilon)$ fraction of the
$C_i$'s have distance $d$.
\end{theorem}
\begin{proof}
For all $C_i$ of distance $\Delta(C_i) < d$, there exists a
representative $v_i \in C_i$ in the set
$\Ball{\vec{0}}{d-1}\setminus \set{\vec{0}}$. If $i\not = j$, then
$v_i \not = v_j$. Hence, there can be only
$\length{\Ball{\vec{0}}{d-1}} -1$ codes with a representative that
close to $\vec{0}$, and so only that many codes of distance less
than $d$. Since $\epsilon t \geq \Vol{n}{d-1}$, the number of codes
with a representative with in $d$ of $\vec{0}$ must be less than
$\epsilon t$. Hence, $t-\epsilon t = (1-\epsilon)t$ of the codes
must have a distance larger than $d$.
\end{proof}
Do packings exist? Let's build one. We need
$$t = \frac{2^n-1}{2^k-1}$$
codes. So, we first need $2^k -1$ to
divide $2^n-1$, which happens if $k$ divides $n$.
Now, to construct a packing, let $n=ck$, and construct $C_1$, $C_2$,
\ldots $C_t$ as follows:
\begin{itemize}
\item Work over the field $\F_2^k$, interpreted as $\F_{2^k}$. Call
this field $K$ for convenience.
\item In this interpretation, a message (usually an element of
$\F^k_2$) will be a single field element of $K$.
\item The space $\bit^n$ can now be viewed as $\F^c_{2^k} =
K^c$. Hence, an codeword is now $c$ field elements.
\end{itemize}
Consider vectors $(\alpha_1, \alpha_2, \ldots \alpha_c) \in K^c$ such
that
\begin{enumerate}
\item $\alpha_i = 0$ for not all $i$, and
\item for the first $i$ so that $\alpha_i \not = 0$, $\alpha_i =1$
\end{enumerate}
How many such vectors are there? If $\alpha_1$ is the first non-zero
entry, it must be 1 and there are $(2^k)^{c-1}$ ways to chose the
$c-1$ remaining entries. If $\alpha_2$ is the first non-zero
entry, it must be 1 and there are $(2^k)^{c-2}$ ways to chose the
$c-2$ remaining entries. So, the number of such vectors is:
$$\left(2^k\right)^{c-1} + \left(2^k\right)^{c-2} +\ldots
\left(2^k\right) + 1 = \frac{\left(2^k\right)^{c}-1}{2^k -1} =
\frac{2^{ck}-1}{2^k-1} = \frac{2^n-1}{2^k-1} =t.$$
Hence, we can associate each code with such a vector.
So, let $C'_{(\alpha_1, \alpha_2, \ldots \alpha_c)} : x \rightarrow
(\alpha_1 x, \alpha_2 x, \ldots \alpha_c x)$ be a function from
message to codeword. Then we can let the code
$$C_{(\alpha_1, \alpha_2, \ldots \alpha_c)} = \set {C'_{(\alpha_1,
\alpha_2, \ldots \alpha_c)}(x) \vert x\in K}$$
Have we packed the space $K^c$ with these codes? To show that, we will
give a function from $K^c \setminus \set{\vec{0}}$ to codes. Given $y
= (y_1, y_2 \ldots y_c) \in K^c$, we can compute the index $(\alpha_1,
\alpha_2, \ldots \alpha_c)$ of the code that contains it via:
\begin{itemize}
\item Suppose $y_{j}$ is the first non-zero entry in $y$. Then it must
be that $\alpha_1=0$, $\alpha_2 = 0$,\ldots $\alpha_{j-1}=0$.
\item Since the first non-zero element of $(\alpha_1, \alpha_2, \ldots
\alpha_c)$ must be 1, we know that $\alpha_j = 1$ and $x = y_j$.
\item $\alpha_{j+1} = \frac{y_{j+1}}{x}$,
\item $\alpha_{j+2} = \frac{y_{j+2}}{x}$,and so on until
\item $\alpha_{c} = \frac{y_{c}}{x}$.
\end{itemize}
Hence, each element of $K^c \setminus \set{\vec{0}}$ can belong to
exactly one code, and so the codes pack the space $K^c$.
\end{document}