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