%% ================================================================
\section{Introduction}

%% ----------------------------------------------------------------
\subsection{Motivation}

A mathematical problem originating in electrical engineering is the recovery of
a signal which is transmitted over a noisy medium.  Examples include electrical
signals traveling down a wire (e.g. data networking), radio signals traveling
through free space (e.g. cellular phones or space probes), magnetization
domains on a hard disk, or pits on an optical disk.  In the latter cases, the
issue is \emph{storage} rather than transmission; for brevity we will use the
term \emph{transmission} nonetheless.

Abstractly, let $\Sigma$ be a finite set, or \bfidx{alphabet}, of symbols.
Often, but not necessarily, $\Sigma = \{0, 1\}$, in which case symbols are
called \bfidx{bits}.  Let $\Sigma^*$ be the (infinite) set of all strings, or
\bfidx{messages}, of zero or more symbols over $\Sigma$.  Let $M$ be an
element of $\Sigma^*$, transmitted over some medium.  Due to physical phenomena
occurring during transmission, the transmitted string $M$ may differ from the
received string $M'$.  For example, let $\Sigma$ be the lower-case letters
along with the space character.  Errors include, but are not limited to, the
following: insertion or duplication of symbols (e.g. ``the house'' is received
as ``the houuse''), deletion of symbols (e.g. ``the huse''), and/or modified
symbols (e.g. ``the hopse'').  When we type, a common error is transposition
(``teh house'').

The essential idea is that protection against errors is accomplished by adding
additional symbols to $M$ in such a way that the redundant information may be
used to detect and/or correct the errors in $M'$.  This insertion of redundant
information is called \bfidx{coding}.  The term \bfidx{error control}
encompasses error detection and error correction.  We will be discussing
so-called \bfidx{block codes}, in which a message is divided into blocks of $k$
symbols at a time.  The transmitter will \bfidx{encode} by adding additional
symbols to each block of $k$ symbols to form a transmitted block of $n$
symbols.  The receiver will \bfidx{decode} by transforming each received block
of $n$ symbols back into a $k$-symbol block, making a best estimate which
$k$-symbol block to decode to.  (Note that you can mentally fix each
misspelling of ``the house'' above, without needing redundant information.  You
do this (a) by context, i.e.  those weren't just random letters, and (b) by
using your intelligence.  Automated error-control systems typically have
neither context nor intelligence, and so require redundancy in order to perform
their task.)

%I cna tpye tihs snetence with ltos of tranpsositions adn you can raed it
%witohut muhc diffiuclty.

Encoding circuitry is typically simple.  It is the decoding circuity which is
more complicated and hence more expensive in terms of execution time, number of
transistors on a chip, power consumption (which translates into battery life),
etc.  For this reason, in situations with low error rate it is common for a
receive to detect errors without any attempt at correcting them, then have the
sender transmit.  It is also for this reason that much of the effort in
coding-theory research involves finding better codes, and more efficient
decoding algorithms.

Different media require different amounts of redundancy.  For example,
communications between a motherboard and a mouse or keyboard are sufficiently
reliable that they typically have no error detection at all.  The higher-speed
USB protocol uses short cyclic redundancy checks (not discussed here) to
implement light error detection.  (For engineering reasons, higher-speed
communications are more error prone.  The basic idea is that at higher data
rates, voltages have less time to correctly swing between high and low values.)
Compact disks have moderately strong error-correction abilities (specifically,
\emph{Reed-Solomon codes}):  this is what permits them to keep working in spite
of little scratches.  Deep-space applications have more stringent
error-correction demands (\cite{bib:vo}).  An interesting recent innovation  is
home networking over ordinary power lines (\cite{bib:gib}).  Naturally, this
requires very strong error correction since it must keep working even when the
vacuum cleaner is switched on.

%% ----------------------------------------------------------------
\subsection{Non-topics}

What we are \textbf{not} discussing:

\begin{itemize}
\item
The type of coding discussed here is
technically referred to as \bfidx{channel coding}.  The term \bfidx{source
coding} refers to data compression done at the receiver, independently of any
error-control coding, in order to reduce transmission time or signal bandwidth.

\item We are not considering cryptographic codes.

\item There exist \bfidx{tree codes}, of which \bfidx{convolutional codes} are
a special case, which do not divide a message into blocks.  In engineering
practice these are quite important, but they are beyond the scope of this
discussion.  See \cite{bib:pw} for information on tree codes.

\item We are discussing systems designed to protect against \bfidx{random
errors}, i.e. we assume that the transmission medium is such that any given bit
has some probability $p$ of being incorrect.  In practice, some but not all
media are such.  In particular, a \bfidx{burst error} may occur when a nearby
electrical motor is switched on, in which case several consecutive symbols may
be incorrect.

\item Insertion, duplication, and deletion of symbols are called
\bfidx{synchronization errors}, since a transmitted $n$-symbol block may be
received with fewer or greater than $n$ symbols.

\item Codes exist to handle burst and synchronization errors, although they
won't be discussed here.  Please see \cite{bib:ms}, \cite{bib:ber}, and
\cite{bib:pw} for more information on this topic.

\end{itemize}

%% ================================================================
\newpage
\section{Fundamental terms and examples}

%% ----------------------------------------------------------------
\subsection{The binary symmetric channel}
\label{sec:bsc}

We are confining ourselves to communications channels in which only random
errors occur, rather than burst or synchronization errors.  Also, here we will
consider \bfidx{binary codes}, where the alphabet is $\{0, 1\}$.  We can
quantify the random-error property a bit more by assuming there is a
probability $p$ of any bit being flipped from 0 to 1 or vice versa.  This model
of a transmission medium is called the \bfidx{binary symmetric channel}, or
BSC: \emph{binary} since the symbols are bits, and \emph{symmetric} since the
probabilities of bit-setting and bit-clearing are the same.

The fundamental theorem of communication is \bfidx{Shannon's theorem}
(\cite{bib:sha}), which when restricted to the BSC says that if $p<1/2$,
reliable communication is possible:  we can always make a code long enough that
decoding mistakes are very unlikely.  Shannon's theorem defines the
\bfidx{channel capacity}, i.e.  what minimum amount of redundant data needs to
be added to make communication reliable.  (See \cite{bib:sud} for a nice
proof.) Note however that Shannon's theorem proves only the existence of codes
with desirable properties; it does not tell how to construct them.

% xxx formula \Pi p^k (1-p)^{n-k}

In \cite{bib:ms} it is shown that if $p$ is exactly $1/2$ then no communication
is possible, but that if $p>1/2$ then one may interchange 0 and 1, and then
assume $p<1/2$.  (For example, if $p=1$, then it is certain that all 0's become
1's and vice versa, and after renaming symbols there is no error whatsoever.)

If $n$ bits are transmitted in a block, the probability of all bits being wrong
is $(1-p)^n$.  The probability of an error in the first position is
$p(1-p)^{n-1}$, and the same for the other single-position errors.  Any given
double error has probability $p^2(1-p)^{n-2}$, and so on; the probability of an
error in all $n$ positions is $p^n$.  Since we assume $p<1/2$, the most likely
scenario is no error at all.  Each single-bit error case is the next likely,
followed by each of the double-bit error cases, etc.  (For example, with $n=3$
and $p=0.1$, these probabilities are 0.729, 0.081, 0.009, and 0.001.) So, when
I send you something that gets garbled in transit, you can only guess what
happened to the message.  But since we assume that fewer bit errors are more
probable, you can use the \bfidx{maximum likelihood} assumption to help guide
your guesses, as we will see below.

%% ----------------------------------------------------------------
\subsection{Linear codes}

In physics, to facilitate analysis of a problem one often makes certain
simplifying assumptions.  For example, orbital mechanics is simpler, but
fractionally less accurate, if one assumes the earth is a perfect sphere rather
than a lumpy oblate spheroid.  In particular, one often makes assumptions that
permit analysis of a system using linear rather than non-linear differential
equations, since the former are easy to solve.  In engineering, by contrast,
one designs systems rather than studying pre-existing systems:  one has the
liberty of designing in linearity (and other simplifying assumptions) from the
start.

In this spirit, to facilitate analysis, we immediately replace the abstract
alphabet $\Sigma$ with the finite field of $q$ elements, $\F_q$.  (Recall  that
a finite field has a prime-power number of elements.  See \cite{bib:ln} for
background on finite fields.  For this paper, $q$ will simply be 2 so you won't
need any particular expertise in finite fields.)  Furthermore, since we divide
a message $M$ into blocks of $k$ symbols each, i.e. $k$-tuples over $\F_q$, we
have vectors over a field.  This permits the application of the well-known and
powerful tools of linear algebra.

\textbf{Definitions:}
\begin{itemize}

\item A \bfidx{block code} (here, we will just call it a \bfidx{code}) is any
subset of the set of all $n$-tuples over $\Sigma$, for some positive integer
$n$.  Since we take $\Sigma=\F_q$, this means that a code is any subset $C$ of
the vector space $\F_q^n$.

\item If $C$ is not just a subset of $\F_q^n$ but a subspace as well, then we
say that $C$ is a \bfidx{linear code}.  In this case, we take $k$ to be the
dimension of $C$.  (All codes discussed here are linear.)

\item The parameter $k$ is called the \bfidx{dimension} of the linear code $C$;
$n$ is called the \bfidx{length} of $C$.

\item The \bfidx{encoding problem} is that of \bfidx{embedding} the smaller
vector space $\F_q^k$ into the larger vector space $\F_q^n$, in a maximal way
as will be discussed below.

\item A vector in $\F_q^k$ is called a \bfidx{message word}; its image in
$C$ is called a \bfidx{codeword}.

\item During transmission, a codeword may be turned into any element of
$\F_q^n$.  We will call this a \bfidx{received word}.

\end{itemize}

\textbf{Notation.} For brevity, we will often write $n$-tuples in the form
$111$ rather than $(1,1,1)$.  There is no ambiguity as long as each coordinate
takes only a single digit, which is certainly the case over $\F_2$.

%% ----------------------------------------------------------------
\subsection{The repetition codes}

\textbf{Example.} The three-bit \bfidx{repetition code} embeds $\F_2$ into
$\F_2^3$ via the following: $0 \mapsto 000$ and $1 \mapsto 111$.  Here, $k=1$
and $n=3$.  Note that there are $2^3=8$ elements of $\F_2^3$, but only two of
them are codewords.

More generally, we have a \bfidx{family} of $n$-bit repetition codes, embedding
$\F_2$ into $\F_2^n$: 0 maps to the vector consisting of $n$ zeroes, and 1 maps
to $n$ ones.  Clearly, these are linear codes.

%% ----------------------------------------------------------------
\subsection{Minimum distance}

\textbf{Definition.}  The \bfidx{Hamming weight} of a vector $\vec v$ in
$\F_q^n$ is given by the number of non-zero entries in $\vec v$.  This is a
function $w: \F_q^n \to \Z$.  For example, $w(101) = 2$.

\textbf{Definition.}  The \bfidx{Hamming distance} between vectors $\vec u$ and
$\vec v$ in $\F_q^n$ is given by the number of non-zero entries in their
difference.  That is, $d: \F_q^n \times \F_q^n \to \Z$ is given by $d(\vec u,
\vec v) = w(\vec u - \vec v)$.  For example, $d(101, 110) = w(010) = 1$.

\textbf{Definition.}  The \bfidx{minimum distance} of a code $C$ is the
smallest distance between distinct pairs of vectors of $C$.  If $C$ is linear,
then the difference of $\vec u$ and $\vec v$ is also in $C$, so the minimum
distance is then the \bfidx{minimum weight} over all non-zero vectors in $C$.
For example, the three-bit repetition code has minimum distance 3.  We overload
the letter $d$ by writing the minimum distance of $C$ as $d(C)$, or simply $d$.
From the context, it's clear which meaning of $d$ is intended.

(Note:  For some codes it is clear what the minimum distance.  For others,
while it may be relatively easy to compute a lower bound on a code's minimum
distance, the \bfidx{true minimum distance} may be much harder to find.  For
some families of codes, true minimum distances are unknown.)

%% ----------------------------------------------------------------
\subsection{Error detection and error correction}
\label{sec:edec}

By example, we will see how error-detection and error-correction abilities of a
code are related to the code's minimum distance.  Suppose we are sending single
0's and 1's using a three-bit repetition code.  You may trust me to encode only
0 or 1, as 000 or 111, respectively, but due to noise you might receive any of
000, 001, 010, 011, 100, 101, 110 or 111.  If you were to receive the block
111, then you may assume that either I sent 111 and all bits are intact, or I
sent 000 and there was a triple bit error.  Using the \bfidx{maximum
likelihood} assumption from above, the former conclusion is the more likely.
Now suppose you receive the message 101 from me.  Which is more likely: that I
sent 000 and two bits were flipped, or that I sent 111 and the middle bit was
flipped?  Again, the latter is the more likely.

That is:
\begin{itemize}
\item If you receive 000 (weight 0), then you decode to 0, and you assume
	there were no errors in transmission.
\item If you receive 100, 010, or 001 (weight 1), then you decode to 0,
	and you believe there was a single bit error in transmission.
\item If you receive 110, 101, or 011 (weight 2), then you decode to 1,
	and you believe there was a single bit error in transmission.
\item If you receive 111 (weight 3), then you decode to 1, and you assume
	there were no errors in transmission.
\end{itemize}

In the following figure I mark codewords with an open circle.
Maximum-likelihood decoding involves finding the codeword which is nearest to a
given received word:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.0)
%\put(0.0,0.0){\framebox(6.5,1.0)}
%
\put(0.58,0.8){$000$}
\put(0.52,0.62){$w=0$}
\put(0.7,0.4){\circle{0.25}}
\put(0.7,0.4){\circle*{0.05}}
\thicklines
\put(2.2,0.4){\vector(-1,0){1.4}}
\thinlines
%
\put(1.78,0.8){$100,010,001$}
\put(2.02,0.62){$w=1$}
%\put(2.2,0.4){\circle{0.25}}
\put(2.2,0.4){\circle*{0.05}}
%\put(2.2,0.4){\line(1,0){1.4}}
%
\put(3.28,0.8){$110,101,011$}
\put(3.52,0.62){$w=2$}
%\put(3.7,0.4){\circle{0.25}}
\put(3.7,0.4){\circle*{0.05}}
\thicklines
\put(3.7,0.4){\vector(1,0){1.4}}
\thinlines
%
\put(5.08,0.8){$111$}
\put(5.02,0.62){$w=3$}
\put(5.2,0.4){\circle{0.25}}
\put(5.2,0.4){\circle*{0.05}}
\end{picture}

For this 3-bit repetition code, you can correctly \bfidx{detect} any one-bit
error.  If a triple bit error occurs, you won't know it; if a double-bit error
occurs, it will look like a single-bit error instead.  In these latter two
cases, you would have made a \bfidx{decoding error}.

Now suppose we use a four-bit repetition code.  I encode 0 as 0000 and 1 as
1111.  If you receive a vector of weight 0 or 1, you decode to 0; if you
receive a vector of weight 3 or 4, then you decode to 1.  However, if you
receive a vector with two zero bits and two one bits, then you know something
is wrong (I can be trusted to only have sent 0000 or 1111, neither of which you
got), but it's a coin toss whether two bits got set by error, or two bits got
cleared by error:

% xxx perfect here

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.1)
%\put(0.0,0.0){\framebox(6.5,1.1)}
%
\put(0.08,0.8){$0000$}
\put(0.02,0.42){$w=0$}
\put(0.2,0.2){\circle{0.25}}
\put(0.2,0.2){\circle*{0.05}}
\thicklines
\put(1.7,0.2){\vector(-1,0){1.4}}
\thinlines
%
\put(1.28,0.9){$1000,0100$}
\put(1.28,0.7){$0010,0001$}
\put(1.52,0.42){$w=1$}
%\put(1.7,0.2){\circle{0.25}}
\put(1.7,0.2){\circle*{0.05}}
%\put(1.7,0.2){\line(1,0){1.4}}
%
\put(2.78,0.9){$1100,1010,1001$}
\put(2.78,0.7){$0110,0101,0011$}
\put(3.02,0.42){$w=2$}
\put(3.2,0.2){\vector(-1,0){0.4}}
\put(3.2,0.2){\vector(1,0){0.4}}
\put(2.97,0.00){?}
\put(3.37,0.00){?}
%\put(3.2,0.2){\circle{0.25}}
\put(3.2,0.2){\circle*{0.05}}
%\put(3.2,0.2){\line(1,0){1.4}}
%
\put(4.28,0.9){$1110,1101$}
\put(4.28,0.7){$1011,0111$}
\put(4.52,0.42){$w=3$}
%\put(4.7,0.2){\circle{0.25}}
\put(4.7,0.2){\circle*{0.05}}
\thicklines
\put(4.7,0.2){\vector(1,0){1.4}}
\thinlines
%
\put(6.08,0.8){$1111$}
\put(6.02,0.42){$w=4$}
\put(6.2,0.2){\circle{0.25}}
\put(6.2,0.2){\circle*{0.05}}
\end{picture}

For this 4-bit repetition code, you can reliably \bfidx{correct} any 1-bit
error, but you can only \bfidx{detect} a 2-bit error.

More generally, we see intuitively that if the minimum distance $d$ of a code
$C$ is odd, then $C$ can detect and correct up to $(d-1)/2$ errors per block.
If $d$ is even, then $C$ can correct up to $d/2 - 1$ errors per block, and can
detect up to $d/2$ errors per block.

Thus, when an error-control system is being designed, the error statistics of
the transmission medium must be known so that the minimum distance can be made
high enough that the chance of $d/2$ or more errors occurring in a block is
vanishingly small.  (Shannon's theorem guarantees the existence of such codes.)
Any fixed code may be defeated by worse-than-expected noise:  either a system
must be designed to handle worst-case noise, or it must be parameterized such
that parameters may be adaptively adjusted at run time to match changing
channel conditions.

%% ----------------------------------------------------------------
\subsection{The even-weight parity check codes}

Let $n=k+1$.  Embed $\F_2^k$ into $\F_2^n$ by sending $$(a_0, a_1, \ldots, a_k)
\;\textrm{ to }\; (a_0, a_1, \ldots, a_k, a_0+\ldots+a_k)$$ where the sum is
taken mod 2.  For example, with $k=4$, $1110$ maps to $11101$.  By
construction, every codeword has even weight.  The extra bit may be thought of
as a parity bit:  It is 0 when the input message word has an even number of 1
bits, and 1 when the input message word has an odd number of 1 bits.  (Of
course, we could define an odd-weight parity-check code as well.  Since it
would lack the zero vector, though, it would be not be a subspace of $\F_2^n$.)
Thus, these are called the \bfidx{even-weight} \bfidx{parity check} codes.

Since $\F_2^k$ consists of all $k$-tuples, including those with 1 in a single
position and zeroes elsewhere, the code contains some $(k+1)$-tuples of weight
2.  Since all codewords have even weight, this means that these parity-check
codes have minimum distance 2.  From the above discussion, this means they can
detect single-bit errors, but can't correct any errors at all.  These are
useful in the case when the probability of a single bit error is quite small
but non-zero, and the probability of a double bit error is vanishingly small.
They enable the receiver to flag a block as bad, and request the sender to
retransmit it.

As with the repetition codes, these form a \bfidx{family} of codes: the $n$-bit
even-weight parity-check codes, embedding $\F_2^{n-1}$ into $\F_2^n$.  Since
$q=2$, the difference of two even-weight vectors is another even-weight vector.
Thus these are linear codes.

%% ----------------------------------------------------------------
\subsection{A graphical perspective}

\label{sec:pack}
Here is what the 3-bit repetition and parity-check codes look like,
respectively, inside $\F_2^3$:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.0,1.75)
%\put(0.0,0.0){\framebox(6.0,1.75)}
\put(0.5,0.2){\line(1,0){1.0}}
\put(0.5,0.2){\line(0,1){1.0}}
\put(0.5,1.2){\line(1,0){1.0}}
\put(1.5,0.2){\line(0,1){1.0}}
%
\put(0.75,0.45){\line(1,0){1.0}}
\put(0.75,0.45){\line(0,1){1.0}}
\put(0.75,1.45){\line(1,0){1.0}}
\put(1.75,0.45){\line(0,1){1.0}}
%
\put(0.5,0.2){\line(1,1){0.25}}
\put(1.5,0.2){\line(1,1){0.25}}
\put(0.5,1.2){\line(1,1){0.25}}
\put(1.5,1.2){\line(1,1){0.25}}
%
\put(0.0,0.15){\small{000}}
\put(1.8,0.15){\small{100}}
\put(0.0,1.15){\small{001}}
\put(1.8,1.15){\small{101}}
\put(0.25,0.40){\small{010}}
\put(2.05,0.40){\small{110}}
\put(0.25,1.40){\small{011}}
\put(2.05,1.40){\small{111}}
%
\thicklines
\put(0.5,0.2){\line(1,1){1.25}}
\thinlines

%%%

\put(3.5,0.2){\line(1,0){1.0}}
\put(3.5,0.2){\line(0,1){1.0}}
\put(3.5,1.2){\line(1,0){1.0}}
\put(4.5,0.2){\line(0,1){1.0}}
%
\put(3.75,0.45){\line(1,0){1.0}}
\put(3.75,0.45){\line(0,1){1.0}}
\put(3.75,1.45){\line(1,0){1.0}}
\put(4.75,0.45){\line(0,1){1.0}}
%
\put(3.5,0.2){\line(1,1){0.25}}
\put(4.5,0.2){\line(1,1){0.25}}
\put(3.5,1.2){\line(1,1){0.25}}
\put(4.5,1.2){\line(1,1){0.25}}
%
\put(3.0,0.15){\small{000}}
\put(4.8,0.15){\small{100}}
\put(3.0,1.15){\small{001}}
\put(4.8,1.15){\small{101}}
\put(3.25,0.40){\small{010}}
\put(5.05,0.40){\small{110}}
\put(3.25,1.40){\small{011}}
\put(5.05,1.40){\small{111}}
%
\thicklines
\put(3.5,0.2){\line(1,1){1.00}}
\put(3.5,0.2){\line(1,5){0.25}}
\put(3.5,0.2){\line(5,1){1.25}}
\put(3.75,1.45){\line(3,-1){0.75}}
\put(4.75,0.45){\line(-1,3){0.25}}
\put(4.75,0.45){\line(-1,1){1.00}}
\thinlines
\end{picture}

On the left, $\F_2$ could have been sent to any edge, e.g. 000 and 001, but the
two codewords would have distance 1 between them; as shown, they have distance
3.  Likewise, on the right, $\F_2^2$ could have been sent to a face of the
cube, with minimum distance 1; as shown, the codewords are spread out over the
cube, as far apart from one another as possible, with minimum distance 2.
These are clearly the highest-distance 1-dimensional and 2-dimensional
subspaces, respectively, of $\F_2^3$.  Here we have $q=2$, $n=3$ and $k=1$ or
$2$.  For higher $n$, $k$ and $q$, though, it's not immediately obvious how to
spread out codewords in this maximum-distance manner.

In general, the encoding problem consists in large part of finding a way of
constructing such embeddings such that all codewords are as far apart from one
another as possible.  This problem clearly is combinatorial in nature.
However, in recent years various approaches have happened to prove fruitful,
including finite geometry (\cite{bib:ak}) and algebraic geometry
(\cite{bib:pre2}).

%% ----------------------------------------------------------------
\subsection{Rate, relative minimum distance, and asymptotics}

The repetition codes have good error-correcting ability.  However, the drawback
is that most of the transmitted data is redundant.  For the 5-bit repetition
codes, only one of every 5 bits is actual data.  The parity-check codes, on the
other hand, add just a single redundant bit, but tolerate fewer errors.

\textbf{Definition.}  The \bfidx{rate} of a code is the ratio $R=k/n$.

The repetition codes have rate $R=1/n$.  As $n$ increases, $R$ approaches zero.
The parity-check codes have rate $R=(n-1)/n$, which approaches 1 as $n$
increases.

\textbf{Definition.}  The \bfidx{relative minimum distance} of a code is the
ratio $\delta=d/n$.

The repetition codes have relative minimum distance $\delta=n/n=1$.  The
parity-check codes have relative minimum distance $2/n$, which approaches 0 as
$n$ increases.

Of course, $R$ and $\delta$ are both confined to the unit interval.  We say
that \bfidx{asymptotically} (as $n$ gets big) the repetition-code family has
$R=0$ and $\delta=1$; asymptotically the parity-check family has $R=1$ and
$\delta=0$.  For large $n$, the repetition codes carry vanishingly little
actual data; their overhead is too large.  For large $n$, the parity-check
codes detect vanishingly few errors per block; their overhead is too small.

\textbf{Definition.} A \bfidx{good code} (really, a good \emph{family} of
codes) is one whose asymptotic rate and asymptotic relative minimum distance
are both bounded away from zero.

Clearly, the repetition and parity-check codes are not good.  It can be shown
that good codes exist; see \cite{bib:ms} for examples.

%% ----------------------------------------------------------------
\subsection{Code parameters; upper and lower bounds}

A linear code is parameterized by the four integers $n$, $k$, $d$ and $q$, or
equivalently by the four rational numbers $n$, $R$, $\delta$ and $q$.
Sometimes one says that $C$ is an $[n,k,d]$ code, or perhaps an $[n,k,d]_q$
code.  For example, the 5-bit binary repetition code is a $[5,1,5]_2$ code.
(Similarly, we might write an asymptotic parameterization of a family of codes
as $[R,\delta]$ or $[R,\delta]_q$.)

We encode by embedding $\F_q^k$ into $\F_q^n$.  Not any embedding will do: as
we saw in section \ref{sec:pack}, the canonical injection which appends $n-k$
zeroes is an embedding, but it has minimum distance 1.  We want to find an
embedding which keeps the vectors as far apart from one another as possible,
maximizing $d$, in order to maximize the code's error-control ability.  Or,
given a fixed minimum distance, we would like to minimize $n$ or maximize $k$,
to keep the code's rate high.  Ideally we would like the rate and the relative
minimum distance to both be high, but there are results (see \cite{bib:ms},
\cite{bib:pw}, \cite{bib:wal}) which show that there are \bfidx{upper bounds}
on the asymptotic rate and relative minimum distance.

Both $R$ and $\delta$ are in the unit interval, so we may think of a parameter
space which looks like the unit square:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.5)
%\put(0.0,0.0){\framebox(6.5,1.5)}
%
\put(3.7,0.92){\emph{Asymptotic Singleton upper bound}}
\put(3.6,0.95){\vector(-1,0){1.3}}
\put(3.7,0.72){\emph{Good codes exist}}
\put(3.6,0.75){\vector(-1,0){1.5}}
\put(3.7,0.52){\emph{Asymptotic Plotkin upper bound}}
\put(3.6,0.55){\vector(-1,0){1.25}}
\put(3.7,1.22){\emph{Unattainable ideal}}
\put(3.6,1.25){\vector(-1,0){0.5}}
\put(3.0,1.25){\circle*{0.05}}
\put(3.7,0.22){\emph{Repetition codes}}
\put(3.6,0.25){\vector(-1,0){0.5}}
\put(3.0,0.25){\circle*{0.05}}
\put(0.1,1.22){\emph{Parity-check codes}}
\put(1.5,1.25){\vector(1,0){0.4}}
\put(2.0,1.25){\circle*{0.05}}
\put(1.5,0.75){$R$}
\put(2.0,0.25){\line(1,0){1.0}}
\put(2.0,0.25){\line(0,1){1.0}}
\put(3.0,0.25){\line(0,1){1.0}}
\put(2.0,1.25){\line(1,0){1.0}}
\thicklines
\put(2.0,1.25){\line(1,-1){1.0}}
\put(2.0,1.25){\line(1,-2){0.5}}
\put(2.5,0.05){$\delta$}
\thinlines
\end{picture}

Note that there are particular codes with parameters in various places on this
square.  The zero-appending code, given by the map from $\F_q$ to $\F_q^n$
which appends $n-1$ zeroes, has $R=1/n$ and $\delta=1/n$.  Asymptotically, both
are zero.  Also, the identity code with $n=k=1$ has $R=1$ and $\delta=1$.
However, this has no error-control ability at all.

The \bfidx{Singleton bound} states that for all codes, $d \le n-k+1$.  Thus,
for any code with $n>1$, the $R=1$, $\delta=1$ corner is unattainable.
Asympotically, the Singleton bound shows that $R+\delta \le 1$.  This means
that the asymptotic $(R,\delta)$ of a family of codes must be below the main
diagonal.  Clearly, this applies to even the identity codes, for which $R=1$
but $\delta \to 0$.  The Plotkin bound shows that the asymptotic $(R,\delta)$
must be below the lower diagonal as well, where the $\delta$ intercept is
$1-1/q$.  See \cite{bib:wal} for a lucid discussion of these and other bounds.

The Singleton and Plotkin bounds provide upper limits on the best code
families:  no codes can be asymptotically better.  There are also \bfidx{lower
bounds} which specify how good the best codes can be, but don't constrain how
bad the worst codes can be (for example, the zero-appending code mentioned
above).  One proves a lower bound, showing that there exist codes with
$(R,\delta)$ above some curve in $R,\delta$ space; the problem of actually
producing such codes is another problem entirely.  Both of these issues are
topics of research.

%% ================================================================
\newpage
\section{Encoding}

%% ----------------------------------------------------------------
\subsection{The generator matrix}

Up to now we haven't really put much linear algebra to work.  To facilitate
analysis, we now require not only that we have linear block codes mapping
injectively from $\F_q^k$ into $\F_q^n$, but furthermore that the injective
mapping is a vector-space homomorphism, i.e. a linear transformation.  There
are many advantages to using a linear transformation, not the least of which is
that instead of having to remember $q^k$ images for all the message words, we
need to remember only the images of $k$ basis vectors.

Such a linear transformation exists for any linear code.  For example,
$\{000,100,010,110\}$ is a subspace of $\F_2^3$, but I can send $\F_2^2$ into
it by $00 \mapsto 110$, $01 \mapsto 100$, $10 \mapsto 000$, $11 \mapsto 010$.
This is a 1-1 map but it isn't linear since it doesn't send zero to zero.  As
long as I don't insist on which elements of $\F_q^k$ map to which elements of
$C$, though, I can produce a linear map:  since $\F_q^k$ and $C$ are vector
spaces of the same dimensions over the same field, an isomorphism exists.  To
obtain it explicitly if only $C$ is given, form a tall matrix the rows of which
are all the vectors of $C$, then row-reduce and discard zero rows.  The result
is a basis for $C$.  Then, send the $i$th standard basis vector in $\F_q^k$ to
the $i$th basis vector of $C$.

However it is obtained, we write a \bfidx{generator matrix}
$$ G : \F_q^k \to \F_q^n $$
where $C$ is the image of $G$ in $\F_q^n$.  For convenience later on (although
it seems quite strange at the moment), we write $G$ as a $k\times n$ matrix:
to encode the message word $\vec m$, we write $\vec m G$ rather than $G \vec
m$.  (If this seems awkward, you may wish to temporarily think in terms of an
$n\times k$ generator matrix, then transpose it when you're done.  Also, from
the context it is clear whether I'm treating $\vec m$ as a row or column
vector.)

What is a generator matrix for the repetition codes?  Clearly, we write ($n=5$
here)
$$ G = \left[ \begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 \\
\end{array} \right]
$$

For the parity-check code, we want (with $n=5$)
$$ 
\left[ \begin{array}{ccccc} a, & b, & c, & d, & a+b+c+d \end{array} \right]
=
\left[ \begin{array}{cccc} a, & b, & c, & d \end{array} \right]
\left[ \begin{array}{ccccc}
  1 & 0 & 0 & 0 & 1 \\
  0 & 1 & 0 & 0 & 1 \\
  0 & 0 & 1 & 0 & 1 \\
  0 & 0 & 0 & 1 & 1 \\
\end{array} \right]
$$
so
$$ 
G = \left[ \begin{array}{ccccc}
  1 & 0 & 0 & 0 & 1 \\
  0 & 1 & 0 & 0 & 1 \\
  0 & 0 & 1 & 0 & 1 \\
  0 & 0 & 0 & 1 & 1 \\
\end{array} \right]
$$

%and thinking transposed for the moment

%$$ 
%\left[ \begin{array}{c} a \\ b \\ c \\ d \\ a+b+c+d \end{array} \right]
%=
%\left[ \begin{array}{cccc}
%  1 & 0 & 0 & 0 \\
%  0 & 1 & 0 & 0 \\
%  0 & 0 & 1 & 0 \\
%  0 & 0 & 0 & 1 \\
%  1 & 1 & 1 & 1 \\
%\end{array} \right]
%\left[ \begin{array}{c} a \\ b \\ c \\ d \end{array} \right]
%$$

Of course, when $\vec{\veps}_i$ is the $i$th standard basis vector for
$\F_q^k$, $\vec{\veps}_i G$ is the $i$th row of $G$.  Unless $k=1$ and $q=2$,
there will be more than one basis vector, hence more than one permutation of
the basis, along with various linear combinations of the basis vectors.  Thus
the generator matrix is generally not unique.  Two different generator matrices
are equivalent, though, if they generate the same subspace $C$ of $\F_q^n$.  To
test for equivalence of two generator matrices, test for equality of their
row-echelon forms.

(Computational note: finite fields have the property that computer arithmetic
is exact.  Thus, there is no roundoff error, and algorithms such as row
reduction may be implemented easily for finite fields, with naive pivoting.)

%two different $G$'s will send some particular vector in $\F_q^k$ to different
%images in $\F_q^n$ (they will act differently on the standard basis for
%$\F_q^k$).

%Then $\{\vec{\veps}_1 G, \ldots, \vec{\veps}_k G\}$ is a basis for the image
%of $G$, which is precisely $C$.

%% ----------------------------------------------------------------
\subsection{Systematic codes}

We've been saying that a linear code $C$ is a $k$-dimensional subspace of
$\F_q^n$.  From this definition, $G$ could take any form as long as it has rank
$k$.  However, our two examples so far (repetition and parity-check codes) have
an additional property:  the first $k$ bits of each $n$-bit codeword are
identical to the $k$ bits of the corresponding message word.

\textbf{Definition.}  A linear code is \bfidx{systematic} if its generator
matrix $G$ is of the form $[I_k | A]$ for some $k \times (n-k)$ matrix $A$,
where $I_k$ is the $k \times k$ identity matrix.

Any linear code can be made systematic:  just put $G$ in row-echelon form.

%% ================================================================
\newpage
\section{Decoding}

%% ----------------------------------------------------------------
\subsection{The parity-check matrix}

If a linear code $C$ has been chosen, we've just seen that encoding is easy:
it's just matrix multiplication.  But how do we decode, and moreover, how do we
do so efficiently?  This might seem to be a harder problem.  In fact, in
general it is.  There have been codes which were published before any decoding
algorithm was known.  And even for well-known codes, one area of current
research is to develop improved decoding algorithms.

Below, it will be useful to find a so-called \bfidx{parity-check matrix}, $H$,
such that $C$ is precisely the kernel of $H$.  (The terminology originally
comes from parity-check codes, but it is a poor choice of words: all linear
codes, not just the parity-check ones, have a parity-check matrix.) That is, we
will want $H \vec v$ to be zero if and only if $\vec v$ is in $C$.  By the
rank-nullity theorem, $H$ will necessarily be $(n-k) \times n$.  Unlike with
$G$, we post-multiply, i.e. we write $H \vec v$, not $\vec v H$.

How can such a matrix $H$ be constructed, given $G$?  First, some terminology.

\textbf{Definition.}  The \bfidx{dual code} of $C$, written $C^\perp$, is the
set of vectors in $\F_q^n$ which are orthogonal to all vectors of $C$, using
the standard dot product.  (Note that the term \emph{dual code} here has
nothing to do with the term \emph{dual space} from linear algebra.) That is,
$$C^\perp = \{\vec v \in \F_q^n : \vec u \cdot \vec v = 0 \textrm{ for all }
\vec u \in C\}$$ 


(The Hamming weight is a vector-space norm, if we define $|c|$ on $F_q$ to have
value 0 when $c=0$, 1 otherwise.  If we use the standard dot product, then
$\F_q^n$ satisfies all the axioms for an inner product space \emph{except} for
the positive-definiteness of the dot product.  E.g. if $\F_q$ has
characteristic 2, the non-zero vector $(1,1)$ dotted with itself is $1+1=0$.
Note that the Hamming weight is computed in $\Z$: it is the number of non-zero
coordinates in a vector.  However, the dot product is computed in $\F_q$.  Thus
the Hamming weight and Hamming distance are positive definite, while the dot
product is not.  This means that inner-product-space results such as $\F_q^n =
C \oplus C^\perp$ do not apply:  the intersection of a subspace and its perp
can contain more than just the zero vector.  In fact, a code can be \bfidx{self
dual}, i.e.  $C=C^\perp$.  For example, $\{00,11\}$ is a self-dual subspace of
$\F_2^2$.  From the result immediately below, a self-dual code must have even
$n$, and $k$ must be $n/2$.)

% xxx can *any* inner product be defined on Fqn?

% inner product:
% left-lin (left add and sc mul)
%xy = yx
% xx >0 if x != 0

%norm:
% ||cx|| = |c|.||x||.   Need |c| defined for Fq!
% ||x|| = 0 iff x = 0
% ||x|| >= 0
% |x.y| <= ||x||.||y||

% distance:
% d(x,y) >= 0
% d(x,y) = d(y,x)
% d(x,z) <= d(x,z) + d(z,y)
% d(x,x) = 0
% d(x,y) != 0 if x != y

We already have $G$; it remains to actually compute a matrix for $H$.  Suppose
that our problem were reversed, i.e. if we had $H$, how would we compute $G$?
That's easy:  since the kernel of $H$ is the image of $G$ (which is $C$) we
could just compute the kernel basis of $H$, which is a standard elementary
linear algebra problem.  $G$ would have rows equal to the elements of that
basis.

Now, I claim that, fortuitously, the generator matrix of $C^\perp$ is $H$ and
the parity-check matrix of $C^\perp$ is $G$.  That is, $C^\perp$'s $G$ and $H$
are swapped from $C$'s.  Also note that $(C^\perp)^\perp$ is just $C$.  We are
given $G$, which is $C$'s generator matrix as well as $C^\perp$'s parity-check
matrix.  The kernel basis of $G$ is the generator matrix for $C^\perp$, which
is also the parity-check matrix for $C$.  So this trick means that not only can
we get a $G$ by computing a kernel basis of an $H$, but vice versa as well.

It remains to prove that $C^\perp$ has generator matrix $H$ and parity-check
matrix $G$.  Remember the convention that a generator matrix acts by
post-multiplication and that a parity-check matrix acts by pre-multiplication.
So in this role, $H$ maps $\F_q^{n-k}$ to $\F_q^n$ by sending $\vec z$ to $\vec
z H$, and $G$ maps $\F_q^n$ to $\F_q^k$ by sending $\vec v$ to $G \vec v$.  To
avoid confusion (only for the duration of this proof) we will write $\oG$ for
$G: \F_q^k \to \F_q^n$ acting by post-multiplication and $\Go$ for $G: \F_q^n
\to \F_q^k$ acting by pre-multiplication.  Likewise, we will write $\Ho$ for
$H: \F_q^n \to \F_q^{n-k}$ and $\oH$ for $H: \F_q^{n-k} \to \F_q^n$.  Plain $G$
and $H$ refer to the matrices without respect to a linear transformation.

We want the following short exact sequences:
\begin{eqnarray*}
0 \rightarrow \F_q^k \stackrel{\oG}{\rightarrow}
	&\F_q^n& \stackrel{\Ho}{\rightarrow} \F_q^{n-k} \rightarrow 0 \\
0 \leftarrow \F_q^k \stackrel{\Go}{\leftarrow}
	&\F_q^n& \stackrel{\oH}{\leftarrow} \F_q^{n-k} \leftarrow 0
\end{eqnarray*}
with $\im(\oG) = C = \ker(\Ho)$ and $\im(\oH) = C^\perp = \ker(\Go)$.  The
short exactness means that $\oG$ and $\oH$ are 1-1, while $\Ho$ and $\Go$ are
onto.  Thus, it suffices to show: (1) $\im(\oH) = C^\perp$; (2) $\oH$ is 1-1,
(3) $\ker(\Go) = C^\perp$, and (4) $\Go$ is onto.  Now, we already have that the
matrix $G$ has rank $k$ and $H$ has rank $n-k$.  Since row rank equals column
rank, (4) will follow from (3) by the rank-nullity theorem.  Likewise, (2) will
follow from (1) since $C^\perp$ has dimension $n-k$.

To prove (3), first let $\vec v \in C^\perp$.  The rows of $G$ form a basis for
$C$; let $\vec{g}_i$ be the $i$th row of $G$, for $i=1, \ldots, k$, where each
$\vec{g}_i$ is a vector of length $n$ (since it is in $\F_q^n$).  Also let
$\vec v = (v_1, \ldots, v_n)$.  The matrix-times-vector multiplication $\Go \vec
v$ consists of dot products of $\vec v$ with the rows of $G$:
\begin{eqnarray*}
	\Go \vec v &=&
	\left[\begin{array}{c} \vec{g}_1 \\ \vdots \\ \vec{g}_k \end{array}\right] 
	\left[\begin{array}{c} v_1 \\ \vdots \\ v_n \end{array}\right] \\
	&=& 
	\left[\begin{array}{c} \vec{g}_1 \cdot \vec v \\ \vdots
		\\ \vec{g}_k \cdot \vec v \end{array}\right] 
\end{eqnarray*}
Since each $\vec{g}_i$ is in $C$ and since $\vec v$ is in $C^\perp$, all the
dot products are zero and so $\Go \vec v = 0$.

Conversely, let $\vec v \in \ker(\Go)$.  Then $\Go \vec v = 0$.  Again, this
product consists of dot products of rows of $G$ with $\vec v$, so $\vec{g}_i
\cdot \vec v = 0$ for all $\vec{g}_i$'s.  Let $\vec c$ be an arbitrary element
of $C$.  Since the $\vec{g}_i$'s are a basis for $C$, $\vec c = \sum_{i=1}^k
c_i \vec{g}_i$ for some $c_i$'s in $\F_q$.  Then
\begin{eqnarray*}
	\vec v \cdot \vec c &=& \vec v \cdot \sum_{i=1}^k c_i \vec{g}_i \\
	&=& \sum_{i=1}^k c_i (\vec v \cdot \vec{g}_i) = 0
\end{eqnarray*}
Therefore $\vec v \in C^\perp$.

To prove that $\im(\oH) = C^\perp$, notice in general that when a matrix $X$
acts on a standard basis by $X \vec{\veps}_i$, the image of that basis consists
of the columns of $X$.  Likewise, when $X$ acts on a standard basis by
$\vec{\veps}_i X$, the image of that basis consists of the rows of $X$.  It
will suffice to show that the rows of $H$ are a basis for $C^\perp$.  Remember
that we set up $H$ to check the elements of $C$, and since $G$ has rows forming
a basis for $C$, necessarily $$ H G^t = 0 $$ This means that the rows of $H$
are orthogonal to the rows of $G$, which shows that the rows of $H$ are in
$C^\perp$.  Since we know that $H$ has rank $n-k$, the image of the standard
basis for $\F_q^{n-k}$ under $\oH$ is linearly independent, and $\im(\oH)$ must
be all of $C^\perp$.

\textbf{Example.} Let's carry out this computation for the two families of
codes we've seen so far.  The 5-bit repetition code has generator matrix
$$ G = \left[ \begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 \\
\end{array} \right]
$$
We then compute the kernel basis (in row-echelon form)
$$ H = \left[ \begin{array}{cccccc}
1 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 \\
\end{array} \right]
$$
Intuitively, this makes sense:  recalling that we are working mod 2, this means
that $H \vec v$ is 0 only when $\vec v$ has all coordinates the same.  The two
possible cases are $00000$ and $11111$, which are precisely the codewords of
the 5-bit repetition codes.

Next, the 5-bit parity-check code has generator matrix
$$ G = \left[ \begin{array}{cccccc}
1 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 \\
\end{array} \right]
$$
We then compute
$$ H = \left[ \begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 \\
\end{array} \right]
$$
Intuitively, this also makes sense:  pre-multiplying $\vec v$ by $H$ just adds
up the bits of $\vec v$ mod 2.  The result will be zero precisely when $\vec v$
has even parity, which is the case iff $\vec v$ is in $C$.

As an added bonus, since the first $G$ is the same as the second $H$, and vice
versa, we now see that the repetition and parity-check families are duals of
one another.

% ----------------------------------------------------------------
\subsection{Computing $H$ for systematic codes}

The parity-check matrix is particularly easy to compute when $C$ is systematic,
i.e. when $G$ is in row-echelon form.  For example, take $k=3$, $n=6$ and
suppose
\begin{eqnarray*}
	G &=& [ I_k | A ] 
	= \left[\begin{array}{cccccc}
		1 & 0 & 0 & a_{14} & a_{15} & a_{16} \\
		0 & 1 & 0 & a_{24} & a_{25} & a_{26} \\
		0 & 0 & 1 & a_{34} & a_{35} & a_{36} \\
	\end{array}\right]
\end{eqnarray*}

Writing $G^t \vec m$ rather than $\vec m G$ to save horizontal space on the
paper, a message word $(m_1, m_2, m_3)$ is encoded as
\begin{eqnarray*}
	\left[\begin{array}{cccccc}
		1 & 0 & 0 \\
		0 & 1 & 0 \\
		0 & 0 & 1 \\
		a_{14} & a_{24} & a_{34} \\
		a_{15} & a_{25} & a_{35} \\
		a_{16} & a_{26} & a_{36} \\
	\end{array}\right]
	\left[\begin{array}{c}m_1 \\ m_2 \\ m_3\end{array}\right]
	&=& 
	\left[\begin{array}{c}
		m_1 \\m_2 \\m_3 \\
		a_{14}m_1+a_{24}m_2+a_{34}m_3 \\
		a_{15}m_1+a_{25}m_2+a_{35}m_3 \\
		a_{16}m_1+a_{26}m_2+a_{36}m_3
	\end{array}\right]
\end{eqnarray*}
%We want to write an $H$ such that $H$ times this codeword is zero:
%\begin{eqnarray*}
%	\left[\begin{array}{cccccc}
%		? & ? & ? & ? & ? & ? \\
%		? & ? & ? & ? & ? & ? \\
%		? & ? & ? & ? & ? & ? \\
%	\end{array}\right]
%	\left[\begin{array}{c}
%		m_1 \\m_2 \\m_3 \\
%		a_{14}m_1+a_{24}m_2+a_{34}m_3 \\
%		a_{15}m_1+a_{25}m_2+a_{35}m_3 \\
%		a_{16}m_1+a_{26}m_2+a_{36}m_3
%	\end{array}\right]
%	&=& 
%	\left[\begin{array}{c}
%		0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\
%	\end{array}\right]
%\end{eqnarray*}
%But that's easy:
We want to write an $H$ such that $H$ times this codeword is zero,
but that's easy:
\begin{eqnarray*}
	\left[\begin{array}{cccccc}
		-a_{14} & -a_{24} & -a_{34} & 1 & 0 & 0 \\
		-a_{15} & -a_{25} & -a_{35} & 0 & 1 & 0 \\
		-a_{16} & -a_{26} & -a_{36} & 1 & 0 & 1 \\
	\end{array}\right]
	\left[\begin{array}{c}
		m_1 \\m_2 \\m_3 \\
		a_{14}m_1+a_{24}m_2+a_{34}m_3 \\
		a_{15}m_1+a_{25}m_2+a_{35}m_3 \\
		a_{16}m_1+a_{26}m_2+a_{36}m_3
	\end{array}\right]
	&=& 
	\left[\begin{array}{c}
		0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\
	\end{array}\right]
\end{eqnarray*}

We can generalize this example to see that if
$$ G = [ I_k | A ] $$
then
$$ H = [ -A^t | I_{n-k} ] $$
Thus, systematic $G$ and $H$ may be computed from one another by
inspection.

%% ----------------------------------------------------------------
\subsection{Brute-force decoding}

If I send you an encoded message, with errors in transit, how do you decode to
find out what I really meant to say?  If the message space is small, i.e.  if
$q$ and $n$ are small, then you could simply make a list of all possible
elements of $\F_q^n$, with the nearest-neighbor codeword precomputed by hand
for each.  This is what we did in section \ref{sec:edec}.  However this is
infeasible for larger codes, which might have billions of codewords or more: it
requires having a table of size $q^n$.

%% ----------------------------------------------------------------
\subsection{The coat of arms}

A useful diagram from \cite{bib:ms}, attributed therein to David Slepian, is
the following:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.0,2.0)
%\put(0.0,0.0){\framebox(6.0,2.0)}
\put(0.0,1.4){\framebox(0.7,0.5){Sender}}  \put(0.7,1.65){\vector(1,0){0.6}}
\put(1.3,1.4){\framebox(0.7,0.5){Encoder}} \put(2.0,1.65){\vector(1,0){0.6}}
\put(2.6,1.4){\framebox(0.7,0.5){Channel}} \put(3.3,1.65){\vector(1,0){0.6}}
\put(3.9,1.4){\framebox(0.7,0.5){Decoder}} \put(4.6,1.65){\vector(1,0){0.6}}
\put(5.2,1.4){\framebox(0.7,0.5){Recipient}}
%
\put(0.6,1.1){$\vec m = m_1\cdots m_k$}
\put(0.7,0.9){Message}
\put(1.8,1.1){$\vec u = u_1\cdots u_n$}
\put(1.85,0.9){Codeword}
\put(2.55,0.4){$\vec e = e_1\cdots e_n$}
%
\put(2.94,0.55){\vector(0,1){0.30}}
\put(2.94,1.15){\vector(0,1){0.25}}
\put(2.940,1.0){\circle{0.25}}
\put(2.94,0.875){\line(0,1){0.25}}
\put(2.815,1.0){\line(1,0){0.25}}
%
\put(2.55,0.2){Error vector}
%\put(3.2,1.1){$\vec v = v_1\cdots v_n$}
\put(3.3,1.1){$\vec v = \vec u + \vec e$}
\put(3.2,0.9){Received vector}
\put(4.5,1.1){$\hat{\vec e} = \hat{e}_1\cdots \hat{e}_n$}
\put(4.50,0.9){Estimate of}
\put(4.70,0.7){error}
\put(4.5,0.4){$\hat{\vec m} = \hat{m}_1\cdots \hat{m}_k$}
\put(4.15,0.2){Estimate of message}
%\put(4.65,0.1){message}
%
\end{picture}

Since we are assuming our channel only inserts random errors, without changing
the block length by loss of synchronization, we can think of the error vector
as being \emph{added} to the codeword during transmission.  Since we embed our
$\F_q^k$ into $\F_q^n$ using a linear transformation (rather than any old
injective map), and since $H \vec u$ is zero for all codewords $\vec u$, we
have the following key fact:
\begin{eqnarray*}
	\vec v &=& \vec u + \vec e \\
	H\vec v &=& H(\vec u+\vec e) = H\vec u + H\vec e = H\vec e
\end{eqnarray*}

%% ----------------------------------------------------------------
\subsection{Standard-array decoding}

\textbf{Definition.}  The quantity $H\vec v = H\vec e$ from the previous
section is called the \bfidx{syndrome} of $\vec v$.

When we form the quotient space $\F_q^n / C$, from elementary algebra we know
that the cosets of $C$ partition $\F_q^n$.  Since $C$ is precisely the kernel
of $H$, if two received vectors are in the same coset,
\begin{eqnarray*}
	\vec u &\sim& \vec v \\
	\vec u - \vec v &\in& C \\
	H(\vec u - \vec v) &=& 0 \\
	H \vec u &=& H \vec v
\end{eqnarray*}
Thus, two vectors are in the same coset iff they share the same syndrome.

Now, $\vec u$ was transmitted; $\vec v = \vec u + \vec e$ was received, but the
receiver can only guess at what $\vec e$ is.  Since $\vec v$ and $\vec e$ have
the same syndrome, the true error vector $\vec e$ is somewhere in $\vec v$'s
coset.  Furthermore, since we are using the \bfidx{maximum likelihood}
assumption mentioned in section \ref{sec:bsc}, the \emph{most likely} error
vector $\hat{\vec e}$ is the \emph{smallest-weight} vector in $\vec v$'s coset.
(A \bfidx{decoding error} means $\vec e \ne \hat{\vec e}$.)

So, the \bfidx{standard-array decoding algorithm} has two stages:  the first
stage is some precomputation before any data is received; the second is done as
each block is received.

Precomputation stage:

\begin{itemize}

\item Write down the elements of $\F_q^k$ and encode each element.  This is a
two-by-$q^k$ table, pairing up message words and codewords.  Sort this by
codeword for easy lookup later.

\item Write down the quotient space $\F_q^n/C$.  This requires making, for the
moment, a matrix of all $q^n$ elements of $\F_q^n$.  (Note that this algorithm
is also not OK for large codes, although the resulting tables will be smaller
than for the brute-force method.)

\item For each coset, search for the smallest-weight element in the coset.
This is called the \bfidx{coset leader}.  Compute and remember the syndrome of
the coset leader; forget about the rest of the coset.


\item Make a list pairing up syndromes and coset leaders.  This is a
two-by-$q^{n-k}$ table.  Sort this by syndrome for easy lookup later.

\end{itemize}

Decoding stage:

\begin{itemize}
\item Given a received vector $\vec v$, compute its syndrome $s$.
\item Look up this syndrome in the precomputed syndrome/leader table.
\item Find the most likely error vector $\hat{\vec e}$ corresponding to $s$.
\item Compute $\hat{\vec u} = \vec v - \hat{\vec e}$.
\item Look up $\hat{\vec u}$ in the precomputed message/codeword table to
	obtain $\hat{\vec m}$.  This is our best guess of what the transmitter
	sent.
\end{itemize}

Note that both table lookups are done on sorted data.  This means we don't have
to sequentially scan either table at run time.  The syndromes are all of
$\F_q^{n-k}$, so we can use base-$q$ arithmetic to go directly to the desired
element of the syndrome/leader table.  For the message/codeword table, we can
use a binary search, with a number of lookups roughly $\log_2$ of the table
size.

(Note that the message/codeword table isn't necessary.  Once we have a codeword
$\hat{\vec u}$, we can solve the linear system $\hat{\vec u} = \hat{\vec m} G$
for $\hat{\vec m}$ using row reduction.  This reduces table space, at the
expense of making the decoding stage use more computation.)

\textbf{Example.}  Let's compute the standard array for the 3-bit repetition
code.  We have

$$
G = \left[ \begin{array}{cccccc} 1 & 1 & 1 \\ \end{array} \right], \qquad
H = \left[ \begin{array}{cccccc}
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{array} \right]
$$
The message words are 0 and 1.  Their images under $G$ are $000$ and $111$.
So, the message/codeword table is as follows:
$$
	\begin{tabular}{cc}
	$\vec m$ & $\vec u$ \\
	\hline
	0 & 000 \\
	1 & 111 \\
	\end{tabular}
$$
The possible received vectors (all of $\F_q^n$) are:
$$
000,001,010,011, 100,101,110,111
$$
$C$ is:
$$
000, 111
$$
$\F_q^n/C$ is:
$$
\begin{array}{cc}
	\{000, & 111\}, \\
	\{010, & 101\}, \\
	\{100, & 011\}, \\
	\{001, & 110\} \\
\end{array}
$$
The coset leaders are the minimum-weight vectors of each coset.
These are as follows, with corresponding syndromes:
$$
\begin{tabular}{cc}
	$\hat{\vec e}$ & $s$ \\
	\hline
	000 & 00 \\
	010 & 01 \\
	100 & 10 \\
	001 & 11 \\
\end{tabular}
$$

Here is an example of using the standard array to decode a received vector:

\begin{itemize}
\item Receive $\vec v = 011$.
\item Compute $s = H\vec v = 10$
\item 10 in binary is 2 in decimal, so go to row 2 (with row indices starting
	at 0) of the syndrome/leader table.
\item At that spot, find $\hat{\vec e} = 100$.
\item Compute $\hat{\vec u} = \vec v - \hat{\vec e} = 011 - 100 = 111$.
\item Match codeword $111$ with message word $1$ in the message/codeword
	table to obtain $\hat{\vec m} = 1$.
\end{itemize}

%% ================================================================
\newpage
\section{The binary Hamming and simplex codes}

Having seen the repetition and parity-check codes, we will now round out our
set of simple examples with two more families.

Above we saw that for a linear code $C$ with parity-check matrix $H$, if $\vec
v = \vec u + \vec e$ is the received vector, then $H \vec v = H \vec e$.  In
the special case $q=2$, though, more may be said.  In this case, all the error
bits are 0 or 1.  Letting $\vec{\veps}_j$ be the standard basis for $\F_q^n$,
i.e. $\vec{\veps}_j$ has a 1 in the $j$th spot and zeroes elsewhere, $$\vec e =
\sum_{j=1}^n c_j \vec{\veps}_j $$ where all the $c_j$'s are zero or one.
Then
\begin{eqnarray*}
	H \vec e &=&  H \sum_{j=1}^n c_j \vec{\veps}_j \\
	&=&  \sum_{j=1}^n c_j H \vec{\veps}_j \\
	&=&  \sum_{j=1}^n c_j H_j
\end{eqnarray*}
where we write $H_j$ for the $j$th column of $H$.  That is, for a binary code,
the syndrome is the sum of the columns of $H$ where an error occurred.  If we
only wish to be able to correct a single-bit error, then we may assume that
$\vec e$ has at most a single 1-bit.  In that case, if $\vec v$ is a codeword,
then $H \vec v$ will be the zero vector, but if $\vec v$ is not a codeword,
then $H \vec v$ will be $H_j$ where $j$ is the position of the error bit.  One
way to make this easy is to simply make a parity-check matrix whose columns
encode all possible error positions.  For example,
$$
	H = \left[\begin{array}{ccccccc}
	0 & 0 & 0 & 1 & 1 & 1 & 1 \\
	0 & 1 & 1 & 0 & 0 & 1 & 1 \\
	1 & 0 & 1 & 0 & 1 & 0 & 1 \\
	\end{array} \right]
$$
Column 1 is 001 which is binary for 1; column 2 is 010 which is binary for 2;
etc.  (There is no column equal to 000, since a column of zeroes has no effect
on the syndrome.)

Let $r$ be the number of rows of $H$; the number of columns is $2^r-1$.  Since
$H$ is an $(n-k) \times n$ matrix, the binary \bfidx{Hamming codes} have
$k=2^r-1-r$ and $n=2^r-1$.  As $n$ gets big, $R=k/n$ goes to 1.  The binary
Hamming codes have minimum distance 3: notice that $1110\cdots0$ is always a
codeword, so $d \le 3$; meanwhile, the Hamming codes are
single-error-correcting so $d \ge 3$.  This forces $d=3$, and $\delta =d/n$
goes to zero as $n$ gets big. Thus, Hamming codes are not good codes.  However,
the decoding algorithm is fantastically simple.

The duals of the binary Hamming codes are called binary \bfidx{simplex codes}.
As discussed in \cite{bib:ms}, in the simplex codes all pairs of distinct
non-zero vectors are the same distance from one another, namely, $2^{r-1}$.
There are $2^r$ elements in the $r$ simplex code, so these are
$[2^r-1,r,2^{r-1}]$ codes.  Asymptotically, they have $R=0$ and $\delta=1/2$.

The Hamming code for $r=2$ is just the 3-bit repetition code, so the simplex
code for $r=2$ is the 3-bit parity-check code.  In the figures of section
\ref{sec:pack}, you can see that all distinct pairs of vectors have distance 2.
Here we see an analogy with the classification of finite groups:  even though,
say, the family of dihedral groups $\mathcal{D}_n$ and the family of symmetric
groups $\mathcal{S}_n$ (both parameterized by $n$) are distinct, they coincide
(up to isomorphism) for $n=3$.  Likewise, the simplex and parity-check codes
families are distinct, as are the Hamming and repetition families, but they
coincide for $n=3$.

%Recall from group theory that we have parameterized families of groups, e.g.
%the dihedral groups $\mathcal{D}_n$, the symmetric groups $\mathcal{S}_n$, the
%cyclic groups $\mathcal{C}_n$, etc.  These families are distinct as a whole,
%but they intersect for small $n$, e.g. $\mathcal{D}_3 = \mathcal{S}_3$.

% 1 1 1 0 0 0 0
% 1 0 0 1 1 0 0
% 0 1 0 1 0 1 0
% 1 1 0 1 0 0 1

% 1 0 0 0 0 1 1
% 0 1 0 0 1 0 1
% 0 0 1 0 1 1 0
% 0 0 0 1 1 1 1

% xxx perfect

%% ================================================================
\newpage
\section{Classification of codes}

To summarize, here are parameters for codes described in this paper.  Of
course, we have not constructed any good codes:  they take a bit more work to
define (\cite{bib:ms}).

\begin{small}
\begin{tabular}{|ccc|cc||ccc|cc|}
\multicolumn{5}{c}{Zero-appending codes} &
\multicolumn{5}{c}{Identity codes} \\
\hline $n$     & $k$   & $d$   & $R$   & $\delta$ & $n$ &   $k$ &   $d$ &   $R$ & $\delta$ \\
\hline
\hline 1     & 1   & 1   & 1   & 1     & 1 &   1 &   1 &   1 &     1 \\
\hline 2     & 1   & 1   & 1/2 & 1/2   & 2 &   2 &   1 &   1 &   1/2 \\
\hline 3     & 1   & 1   & 1/3 & 1/3   & 3 &   3 &   1 &   1 &   1/3 \\
\hline 4     & 1   & 1   & 1/4 & 1/4   & 4 &   4 &   1 &   1 &   1/4 \\
\hline $\to\infty$ & & & $\to 0$ & $\to 0$ & $\to\infty$ &     &     & $\to 1$ &   $\to 0$ \\
\hline
\end{tabular}
\end{small}

\begin{small}
\begin{tabular}{|ccc|cc||ccc|cc|}
\multicolumn{5}{c}{Parity-check codes} & \multicolumn{5}{c}{Repetition codes} \\
\hline $n$ &   $k$ &   $d$ &   $R$ & $\delta$ & $n$ &   $k$ &   $d$ &   $R$ & $\delta$ \\
\hline
\hline 2 &   1 &   2 & 1/2 &     1 & 1 &   1 &   1 &   1 &     1 \\
\hline 3 &   2 &   2 & 2/3 &   2/3 & 2 &   1 &   2 & 1/2 &     1 \\
\hline 4 &   3 &   2 & 3/4 &   1/2 & 3 &   1 &   3 & 1/3 &     1 \\
\hline 5 &   4 &   2 & 4/5 &   2/5 & 4 &   1 &   4 & 1/4 &     1 \\
\hline $\to\infty$ &     &     & $\to 1$ &   $\to 0$ & $\to\infty$ &     &     & $\to 0$ &   $\to 1$ \\
\hline
\end{tabular}
\end{small}

\begin{small}
\begin{tabular}{|c|ccc|cc||c|ccc|cc|}
\multicolumn{6}{c}{Hamming codes} & \multicolumn{6}{c}{Simplex codes} \\
\hline $r$ &           $n$ &   $k$ &   $d$ &     $R$ & $\delta$ & $r$ &           $n$ &   $k$ &   $d$ &    $R$ & $\delta$ \\
\hline
\hline 2 &           3 &   1 &   3 &   1/3 &     1 & 2 &           3 &   2 &   2 &  2/3 &   2/3 \\
\hline 3 &           7 &   4 &   3 &   4/7 &   3/7 & 3 &           7 &   3 &   4 &  3/7 &   4/7 \\
\hline 4 &          15 &  11 &   3 & 11/15 &  3/15 & 4 &          15 &   4 &   8 & 4/15 &  8/15 \\
\hline 5 &          31 &  26 &   3 & 26/31 &  3/31 & 5 &          31 &   5 &  16 & 5/31 & 16/31 \\
\hline $\to\infty$ &  &     &     &   $\to 1$ &   $\to 0$ &   $\to\infty$ & &    &     &  $\to 0$ &   $\to 1/2$ \\
\hline
\end{tabular}
\end{small}

%\setlength{\unitlength}{2.0in}
%\begin{picture}(6.5,1.5)
%%\put(0.0,0.0){\framebox(6.5,1.5)}
%% 1.0, 0.25 is the origin
%\put(0.5,0.75){$R$}
%\put(1.0,0.25){\circle*{0.02}}
%\put(1.0,0.25){\line(1,0){1.0}}
%\put(1.0,0.25){\line(0,1){1.0}}
%\put(2.0,0.25){\line(0,1){1.0}}
%\put(1.0,1.25){\line(1,0){1.0}}
%%\thicklines
%%\put(1.0,1.25){\line(1,-1){1.0}}
%%\put(1.0,1.25){\line(1,-2){0.5}}
%%\put(1.5,0.05){$\delta$}
%%\thinlines
%
%%Zero-appending codes
%
%\put(2.0,1.25){\circle*{0.02}}
%\put(1.5,0.75){\circle*{0.02}}
%\put(1.3,0.55){\circle*{0.02}}
%\put(1.2,0.45){\circle*{0.02}}
%\put(1.0,0.25){\circle*{0.04}}
%\put(2.0,1,25){\vector(-1,-1){0.98}}
%
%%1 1
%%0.5 0.5
%%0.3 0.3
%%0.2 0.2
%%0 0
%
%%%Identity codes
%
%\put(2.0,1.25){\circle*{0.02}}
%\put(1.5,1.25){\circle*{0.02}}
%\put(1.3,1.25){\circle*{0.02}}
%\put(1.2,1.25){\circle*{0.02}}
%\put(1.0,1.25){\circle*{0.04}}
%\put(2.0,1,25){\vector(-1,0){0.98}}
%
%%1 1
%%0.5 1
%%0.3 1
%%0.2 1
%%0 1
%
%%%Parity-check codes
%
%%\put(1.500,1.250){\circle*{0.02}}
%%\put(1.667,0.917){\circle*{0.02}}
%%\put(1.750,0.750){\circle*{0.02}}
%%\put(1.800,0.650){\circle*{0.02}}
%%\put(1.000,1.000){\circle*{0.02}}
%
%%%Repetition codes
%
%\put(2.0,1.25){\circle*{0.02}}
%\put(2.0,0.75){\circle*{0.02}}
%\put(2.0,0.55){\circle*{0.02}}
%\put(2.0,0.45){\circle*{0.02}}
%\put(2.0,0.25){\circle*{0.04}}
%\put(2.0,1,25){\vector(0,-1){0.98}}
%
%%1 1
%%1 0.5
%%1 0.3
%%1 0.2
%%1 0
%%
%%%Hamming codes
%
%%\put(2.0,0.3){\circle*{0.02}}
%%\put(1.4,0.5){\circle*{0.02}}
%%\put(1.2,0.7){\circle*{0.02}}
%%\put(1.0,0.8){\circle*{0.02}}
%%\put(1.0,0.0){\circle*{0.02}}
%
%%1 0.3
%%0.4 0.5
%%0.2 0.7
%%0.0 0.8
%%0 0
%
%%%Simplex codes
%
%%\put(1.6,0.6){\circle*{0.02}}
%%\put(1.5,0.4){\circle*{0.02}}
%%\put(1.5,0.2){\circle*{0.02}}
%%\put(1.5,0.1){\circle*{0.02}}
%%\put(1.0,0.0){\circle*{0.02}}
%
%%0.6 0.6
%%0.5 0.4
%%0.5 0.2
%%0.5 0.1
%%0 0
%
%\end{picture}



%\begin{tabular}{|c|c|c|c|c|}
%\multicolumn{5}{c}{Zero-appending codes} \\
%\hline $n$     & $k$   & $d$   & $R$   & $\delta$ \\
%\hline
%\hline 1     & 1   & 1   & 1   & 1     \\
%\hline 2     & 1   & 1   & 1/2 & 1/2   \\
%\hline 3     & 1   & 1   & 1/3 & 1/3   \\
%\hline 4     & 1   & 1   & 1/4 & 1/4   \\
%\hline $\to\infty$ & & & $\to 0$ & $\to 0$ \\
%\hline
%\end{tabular}
%\begin{tabular}{|c|c|c|c|c|}
%\multicolumn{5}{c}{Identity codes} \\
%\hline         $n$ &   $k$ &   $d$ &   $R$ & $\delta$ \\
%\hline
%\hline         1 &   1 &   1 &   1 &     1 \\
%\hline         2 &   2 &   1 &   1 &   1/2 \\
%\hline         3 &   3 &   1 &   1 &   1/3 \\
%\hline         4 &   4 &   1 &   1 &   1/4 \\
%\hline $\to\infty$ &   . &   . & $\to 1$ &   $\to 0$ \\
%\hline
%\end{tabular}
%
%\begin{tabular}{|c|c|c|c|c|}
%\multicolumn{5}{c}{Parity-check codes} \\
%\hline         $n$ &   $k$ &   $d$ &   $R$ & $\delta$ \\
%\hline
%\hline         2 &   1 &   2 & 1/2 &     1 \\
%\hline         3 &   2 &   2 & 2/3 &   2/3 \\
%\hline         4 &   3 &   2 & 3/4 &   1/2 \\
%\hline         5 &   4 &   2 & 4/5 &   2/5 \\
%\hline $\to\infty$ &   . &   . & $\to 1$ &   $\to 0$ \\
%\hline
%\end{tabular}
%\begin{tabular}{|c|c|c|c|c|}
%\multicolumn{5}{c}{Repetition codes} \\
%\hline           $n$ &   $k$ &   $d$ &   $R$ & $\delta$ \\
%\hline
%\hline           1 &   1 &   1 &   1 &     1 \\
%\hline           2 &   1 &   2 & 1/2 &     1 \\
%\hline           3 &   1 &   3 & 1/3 &     1 \\
%\hline           4 &   1 &   4 & 1/4 &     1 \\
%\hline $\to\infty$ &   . &   . & $\to 0$ &   $\to 1$ \\
%\hline
%\end{tabular}
%
%\begin{tabular}{|c|c|c|c|c|c|}
%\multicolumn{6}{c}{Hamming codes} \\
%\hline   r &           $n$ &   $k$ &   $d$ &     $R$ & $\delta$ \\
%\hline
%\hline   2 &           3 &   1 &   3 &   1/3 &     1 \\
%\hline   3 &           7 &   4 &   3 &   4/7 &   3/7 \\
%\hline   4 &          15 &  11 &   3 & 11/15 &  3/15 \\
%\hline   5 &          31 &  26 &   3 & 26/31 &  3/31 \\
%\hline   . & $\to\infty$ &   . &   . &   $\to 0$ &   $\to 0$ \\
%\hline
%\end{tabular}
%\begin{tabular}{|c|c|c|c|c|c|}
%\multicolumn{6}{c}{Simplex codes} \\
%\hline   r &           $n$ &   $k$ &   $d$ &    $R$ & $\delta$ \\
%\hline
%\hline   2 &           3 &   2 &   2 &  2/3 &   2/3 \\
%\hline   3 &           7 &   3 &   4 &  3/7 &   4/7 \\
%\hline   4 &          15 &   4 &   8 & 4/15 &  8/15 \\
%\hline   5 &          31 &   5 &  16 & 5/31 & 16/31 \\
%\hline   . & $\to\infty$ &   . &   . &  $\to 0$ &   $\to 0$ \\
%\hline
%\end{tabular}

% are the simplex codes good?  show why not.

%% ================================================================
% detect only is just Hy.  cheap.
% better, if systematic, then G(y1..yk) and check that the rest match.
% it's the correction which is expensive.

% rep 3 is simplex on the cube; cf D3 = S3.

%% ================================================================
\newpage
\section{More information}

The three most fundamental papers (dating from 1948-1950) are \cite{bib:sha},
\cite{bib:ham}, and \cite{bib:gol}.

There are many introductions to coding theory, of which I mention a few:  see
\cite{bib:ms} and \cite{bib:ber} for a thorough treatment of elementary as well
as advanced topics.  \cite{bib:vo} and \cite{bib:pre1} are less encyclopedic
and more elementary.  \cite{bib:ms} discusses only block codes, and does so in
depth; \cite{bib:pw} discusses block and tree codes.  See \cite{bib:sud} for an
algorithmic approach.

Topics of research in coding theory include the following:

\begin{itemize}
\item New families of codes, including some
	highly mathematical approaches (e.g. \cite{bib:pre2}).
\item Sharper bounds.
\item More efficient decoding algorithms.
\item Non-linear codes.
\item Codes over non-fields (e.g. \cite{bib:hkcss}).
\end{itemize}

\cite{bib:ms} contains many open problems.  \cite{bib:sud} has a large
bibliography; \cite{bib:ms} has a huge bibliography.

%% ================================================================
\section{Acknowledgements}

The presentation here is more or less from the first chapters of \cite{bib:ms},
\cite{bib:pw}, \cite{bib:ber}, and \cite{bib:vo}.  However, given that my
intended audience is mathematics students rather than electrical engineers, I
have chosen to write a more algebraic treatment.
