\documentclass[10pt]{article} \usepackage{amsfonts} \newtheorem{define}{Definition} %\newcommand{\Z}{{\bf Z}} \usepackage{psfig} \oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in \textheight=9in \textwidth=6.25in \begin{document} \input{preamble.tex} \lecture{5}{ September 22, 2004}{Madhu Sudan} { %The Swastik Kopparty} \section {Algebraic Codes} In this lecture we will study combinatorial properties of several algebraic codes. In particular, we will introduce: \begin{itemize} \item Reed-Solomon Codes based on univariate polynomials over finite fields. \item Reed-Muller Codes based on multivariate polynomials over finite fields. \item Hadamard Codes as an interesting special case of Reed Muller Codes. \item The Plotkin bound that shows that Hadamard codes are optimal for their distance. \end{itemize} \section {Projection Bound Revisited and Reed Solomon Codes} Recall that the projection bound for an $(n,k,d)_q$ code said that $d \leq n-k+1$. This was proved using the following argument: Project the $q^k$ codewords to the first $k-1$ coordinates. Since there are only $q^{k-1}$ possible $k-1$ tuples, there must be two codewords that projected to the same point. At worst, those two codewords can differ in only the remaining $n-(k-1)$ places. Thus the minimum distance is at least $n-(k-1) = n-k+1$. Althought the argument used above was very loose, this bound is tight! To show this, we will produce a code $\mathcal C: \F_q^k \rightarrow \F_q^n$ that has the following extremely strong property: $\forall S \subset [n], |S| = k$, the restriction map $\mathcal C|_S: \F_q^k \rightarrow \F_q^k$ is a bijection. Such a map is in fact well known. It is the polynomial evaluation map based on the following polynomial interpolation theorem: \begin{theorem} {\bf Polynomial Interpolation Theorem:} Let $F$ be a field. For any $\alpha_1, \alpha_2, \ldots \alpha_{l+1}\in F$, pairwise distinct, and any $y_1, y_2, \ldots, y_{l+1}\in F, \exists$ unique polynomial $p(x)$ with degree $\leq l$ such that $p(\alpha_i) = y_i, \forall i \in [l+1]$. \end{theorem} \begin{proof-idea} One treats the $l+1$ coefficients of the polynomial as unknowns. The $l+1$ conditions $p(\alpha_i) = y_i$ are linear constraints on them. Show that the linear system has a unique solution by proving the constraint matrix is invertible(it is a Vandermonde matrix). \end{proof-idea} \\ Thus if we pick distinct $\alpha_1, \ldots \alpha_{l+1} \in F$, we get a bijection:\\ \{Coefficients of $p$, a degree $l$ polynomial \} $\Leftrightarrow$ \{ $\left
$\}
As it is, this map is no good: we merely map $l+1$-tuples to $l+1$-tuples. But a slight variation on Theorem 1 (which follows directly from it) does the trick.
\begin{theorem}
{\bf Useful Polynomial Interpolation Theorem:} Let $F$ be a field. We are given $\alpha_1, \alpha_2, \ldots \alpha_{n}\in F$, pairwise distinct. Then for any distinct $i_1, i_2, \ldots i_{l+1} \in [n]$ and any $y_1, y_2, \ldots, y_{l+1}\in F, \exists$ unique polynomial $p(x)$ with degree $\leq l$ such that $p(\alpha_{i_t}) = y_i, \forall t \in [l+1]$.
\end{theorem}
This motivates the Reed Solomon Code (1960ish) as defined below:
\begin{itemize}
\item Given $n, q, k, \alpha_1, \ldots \alpha_n$, with $\alpha_i$ distinct elements of $\F_q$.
\item For $c = (c_0, c_1, \ldots c_{k-1})$, define polynomial $p_c(x) = c_0 + c_1x + \ldots c_{k-1}x^{k-1}$
\item The code is specified by the encoding function
$\rs : (c_0, c_1, \ldots c_{k-1}) := \left $, the evaluation of $p$ on each point of $\F_q^m$.
\end {itemize}
Note that this too is a linear code.
To determine the parameters of the code, we need a little bit of work.
\begin{itemize}
\item $n = q^m$
\item $k = {l+m \choose l}$ when $l \leq q-1$. This is merely the number of monomials of degree $\leq l$, and since the monomials form a basis for $P_m^l$, it is the dimension of our code. If $l \geq q$ it gets messy because of identities like $x^q = x, \forall x \in \F_q$, and thus we will ignore this case forever.
\item $d = \left(1-\frac{l}{q}\right)n$, because of the following result which will be proved later: Any non-zero polynomial on $\F_q^m$ of degree $\leq l$ is zero on at most $\frac{l}{q} q^m$ points. We already know this result for $m = 1$ (and indeed used it to prove the distance of the RS code).
\item $q = q$
\end{itemize}
Let us just pick some parameters arbitrarily to get a feel for the kinds of codes that we get.
\begin{itemize}
\item $m = 2$
\item $l = \frac{1}{3}q$
\item So $n = q^2$, $k = {\frac{1}{3}q + 2 \choose 2} \approx \frac{1}{18}q^2$, $d = \frac{2}{3}n = \frac{2}{3}q^2$
\end{itemize}
So $\exists [q^2, \frac{1}{18}q^2, \frac{2}{3}q^2]_q$ codes (note the constant rate and constant relative distance). Here $q \approx \sqrt{n}$, which is already much better than the RS code. With a slightly different choice of parameters, for any constant $m$, there is a family of $[q^m, \frac{1}{(2m)^m} q^m, \frac{1}{2} q^m]_q$ codes with good distance and $q \approx n^{1/m}$.
\section{The Plotkin Bound and Hadamard Codes }
Let us see what kind of binary RM codes exist. If we put $q = 2$, since $l \leq q-1$, we are forced to put $l = 1$. Thus we are dealing with linear multivariate polynomials over $\F_2$. The only parameter we can vary is $m$. We get $n=2^m$, $k = {m + 1\choose 1} = m+1$ and $d = 1/2 \cdot 2^m$. Now the rate of this code is horrendous, $m+1$ bits get encoded as $2^m$ bits. However, we get great relative distance (= 1/2). This code is called the Hadamard code.
Last lecture we saw the unnerving phenomenon that there cannot exist a binary code with more than $2$ codewords with relative distance $> 2/3$ \footnote{To recap, let $x,y,z$ be codewords in a code with relative distance $2/3 + \epsilon$. Look at $x-y$ and $x-z$. They are both of relative hamming weight $2/3 + \epsilon$. Thus they agree in at least $1/3 + 2\epsilon$ of the positions. So the relative distance between $y$ and $z$ is at most $2/3 - 2\epsilon$.} The Plotkin bound extends this idea to codes with relative distance $1/2$ and shows that the Hadamard codes are optimal for this distance.
\begin{theorem} {\bf Plotkin Bound:} If there exists a $(n,k,n/2)_2$ code, then $k \leq \log_2(2n)$.
\end{theorem}
\begin{proof-sketch}
Suppose the code consists of words $c_1, c_2, \ldots c_K \in {0,1}^n$. Create vectors $v_1, v_2 \ldots v_K \in {1,-1}^n$ by
$(v_i)_j = (-1)^{(c_i)_j}$. Now, the condition that $c_i$ and $c_j$ have distance at least $1/2$ is equivalent to the condition
that $v_i$ and $v_j$ have inner product $\left