%% ================================================================
\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.

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.)

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

What we are \textbf{not} talking about:

\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 talking about 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 today's
talk.

% xxx see convo?  or what ...

\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 today.  Please see \cite{bib:ms} and \cite{bib:ber} for more
information on this topic.

\end{itemize}

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

%% ----------------------------------------------------------------
\subsection{The binary symmetric channel}

bsc

chan cap

cap is 0 at p=1/2

%% ----------------------------------------------------------------
\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 an oblate spheroid.  In particular, one often makes assumptions that
permit analysis of a system using linear rather than non-linear differential
equations.  In engineering, by contrast, one designs systems rather than
studying pre-existing systems.  Here, 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 elements.  See \cite{bib:ln} for
background on finite fields.  For today, $q$ will simply be 2.)  Furthermore,
since we divide a message $M$ into 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{Definition.} A \bfidx{code} is any subset $C$ of the vector space
$\F_q^n$.  If $C$ is a subspace, 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 today will be linear.)

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.

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

%% ----------------------------------------------------------------
\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 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 minimum weight over 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.

Easily, the Hamming weight is a vector-space norm, if we use the standard inner
product and if we define $|c|$ on $F_q$ to have value 0 when $c=0$, 1
otherwise.

% w(2,2,2) == |c| w(1,1,1)

% xxx this is a norm per se.

% 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

%% ----------------------------------------------------------------
\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 were 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.  Assuming for the
sake of argument that the bit-error probability is less than 0.5, 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?  Assuming $p < 0.5$, 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}

xxx barbell diagram w/ distances 0, 1, 2, 3.

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 (for this paragraph only) suppose we used 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.  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.  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.

% xxx refer to channel capacity here.

In the following figure we see two (of several possible) injective maps
of $\F_2$ into $\F_2^3$:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.0,2.0)
%\put(0.0,0.0){\framebox(6.0,2.0)}
\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(1.1,0.8){\line(1,0){1.0}}
\put(1.1,0.8){\line(0,1){1.0}}
\put(1.1,1.8){\line(1,0){1.0}}
\put(2.1,0.8){\line(0,1){1.0}}
%
\put(0.5,0.2){\line(1,1){0.6}}
\put(1.5,0.2){\line(1,1){0.6}}
\put(0.5,1.2){\line(1,1){0.6}}
\put(1.5,1.2){\line(1,1){0.6}}
\put(1.5,1.2){\line(1,1){0.6}}
%
\put(0.2,0.15){000}
\put(1.6,0.15){100}
\put(0.2,1.15){001}
\put(1.6,1.15){101}
\put(0.8,0.75){010}
\put(2.2,0.75){110}
\put(0.8,1.75){011}
\put(2.2,1.75){111}
%
\thicklines
\put(0.5,0.2){\line(0,1){1.0}}
%\put(0.5,0.2){\line(2,5){0.6}}
%\put(0.5,0.2){\line(5,2){2.6}}
\put(0.5,0.2){\line(1,1){1.6}}
\thinlines
\end{picture}

Notice that in one case, the two codewords have distance 1 between them; in the
other, they have distance 3.  The latter is the 3-bit repetition code, which
obviously is the highest-distance map from $\F_2$ to $\F_2^3$ that sends $0$ to
$000$.  Here we have $q=2$, $k=1$ and $n=3$.  For higher $n$, $k$ and $q$, it's
not immediately obvious how to spread out codewords in this maximum-distance
manner.

xxx parck too.  xxx not bottom square.

xxx we want the codewords spread out over the cube, as far apart from one
another as possible.

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 algebraic-geometric approaches have happened to prove
very fruitful (\cite{bib:pre}).

xxx ldpc's and random codes too; what else

xxx

\setlength{\unitlength}{1.0in}
\begin{picture}(6.0,2.0)
%\put(0.0,0.0){\framebox(6.0,2.0)}
\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(1.0,0.7){\line(1,0){1.0}}
\put(1.0,0.7){\line(0,1){1.0}}
\put(1.0,1.7){\line(1,0){1.0}}
\put(2.0,0.7){\line(0,1){1.0}}
%
\put(0.5,0.2){\line(1,1){0.5}}
\put(1.5,0.2){\line(1,1){0.5}}
\put(0.5,1.2){\line(1,1){0.5}}
\put(1.5,1.2){\line(1,1){0.5}}
%
\put(0.2,0.15){000}
\put(1.6,0.15){100}
\put(0.2,1.15){001}
\put(1.6,1.15){101}
\put(0.7,0.65){010}
\put(2.1,0.65){110}
\put(0.7,1.65){011}
\put(2.1,1.65){111}
%
\thicklines
\put(0.5,0.2){\line(0,1){1.0}}
\put(0.5,0.2){\line(1,1){1.5}}
\thinlines

%\end{picture}
%xxx
%\setlength{\unitlength}{1.0in}
%\begin{picture}(6.0,2.0)

%\put(0.0,0.0){\framebox(6.0,2.0)}
\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(4.0,0.7){\line(1,0){1.0}}
\put(4.0,0.7){\line(0,1){1.0}}
\put(4.0,1.7){\line(1,0){1.0}}
\put(5.0,0.7){\line(0,1){1.0}}
%
\put(3.5,0.2){\line(1,1){0.5}}
\put(4.5,0.2){\line(1,1){0.5}}
\put(3.5,1.2){\line(1,1){0.5}}
\put(4.5,1.2){\line(1,1){0.5}}
%
\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(3.5,0.2){\line(1,1){1.0}}
\put(3.5,0.2){\line(1,3){0.5}}
\put(3.5,0.2){\line(3,1){1.5}}
\put(4.5,1.2){\line(-1,1){0.5}}
\put(5.0,0.7){\line(-1,1){0.5}}
\thinlines
\end{picture}

a;sdkjf;aldksf

\setlength{\unitlength}{1.0in}
\begin{picture}(6.0,2.0)
%\put(0.0,0.0){\framebox(6.0,2.0)}
\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.2,0.15){\small{000}}
\put(1.6,0.15){\small{100}}
\put(0.2,1.15){\small{001}}
\put(1.6,1.15){\small{101}}
\put(0.45,0.40){\small{010}}
\put(1.85,0.40){\small{110}}
\put(0.45,1.40){\small{011}}
\put(1.85,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

%%\put(0.0,0.0){\framebox(6.0,2.0)}
%\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(4.0,0.7){\line(1,0){1.0}}
%\put(4.0,0.7){\line(0,1){1.0}}
%\put(4.0,1.7){\line(1,0){1.0}}
%\put(5.0,0.7){\line(0,1){1.0}}
%%
%\put(3.5,0.2){\line(1,1){0.5}}
%\put(4.5,0.2){\line(1,1){0.5}}
%\put(3.5,1.2){\line(1,1){0.5}}
%\put(4.5,1.2){\line(1,1){0.5}}
%%
%\put(3.2,0.15){000}
%\put(4.6,0.15){100}
%\put(3.2,1.15){001}
%\put(4.6,1.15){101}
%\put(3.7,0.65){010}
%\put(5.1,0.65){110}
%\put(3.7,1.65){011}
%\put(5.1,1.65){111}
%%
%\thicklines
%\put(3.5,0.2){\line(1,1){1.0}}
%\put(3.5,0.2){\line(1,3){0.5}}
%\put(3.5,0.2){\line(3,1){1.5}}
%\put(4.5,1.2){\line(-1,1){0.5}}
%\put(5.0,0.7){\line(-1,1){0.5}}
%\thinlines

\end{picture}

%% ----------------------------------------------------------------
\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 \bfidx{even weight}.  The extra bit may be
thought of as a \bfidx{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$.)

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
parity-check codes, embedding $\F_2^{n-1}$ into $\F_2^n$.

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

The repetition codes have good error-correcting ability: even with high error
rates, one simply makes larger and larger repetition blocks.  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} the repetition-code family has rate 0 and relative
minimum distance 1; asymptotically the parity-check family has rate 1 and
relative minimum distance 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 0 and 1.

Clearly, the repetition and parity-check codes are not good.  It may be shown
(\cite{bib:ms}) that good codes exist.

xxx find 1st such in MS.  Then describe how less trivial they are to
construct.

%% ----------------------------------------------------------------
\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$.

We encode by embedding $\F_q^k$ into $\F_q^n$.  Not any embedding will do: 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, in order to maximize the code's
error-control ability.  Or, given a fixed minimum distance, we would like to
minimize $n$, to keep the code's rate high.  Ideally, we would like the rate
and the relative minimum distance to both be high.  However, there are results
(see \cite{bib:ms}) which show that there are upper and lower bounds on the
asymptotic rate and relative minimum distance.  (Some of these bounds are easy
to prove (although we won't today); sharper bounds have taken more work to
produce.)

xxx square plot here

xxx show singleton, plotkin, g-v

xxx in particular, d in terms of n,k.

xxx xref cube diagrams above; minimize n,q; maximize k,d.

%% ================================================================
\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.
Such a linear transformation always 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.  However, as long as I don't insist on which elements of $\F_q^k$ map
to which elements of $C$, 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
does exist.  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 $$

and $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 x$, we write $\vec x G$ rather than $G \vec x$.
(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.)

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 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.

%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 (xxx xref) 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 (xxx xref).

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 y$ to be zero if and only if $\vec y$ 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 y$, not $\vec y H$.

How can such a matrix $H$ be constructed, given $G$?  First, some terminology.
Using the standard dot product, we can make $\F_q^n$ into an inner product
space.  Then:

\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$.  That
is, $C^\perp = \{\vec v \in \F_q^n : \vec u \cdot \vec v = 0 \textrm{ for all }
\vec u \in C\}$.  (Note that the term \emph{dual code} here has nothing to do
with the term \emph{dual space} from linear algebra.)

It is a standard result from linear algebra (in fact, a frequent
algebra-qualifier item at Arizona State) that for any subspace $W$ of any
finite-dimensional inner product space $V$, $V = W \oplus W^\perp$.  Here, this
means $\F_q^n = C \oplus C^\perp$.  This permits us to use a result of algebra
which shows that there is a \bfidx{short exact sequence} $$ 0 \to \F_q^k
\stackrel{G}{\to} \F_q^n \stackrel{H}{\to} \F_q^{n-k} \to 0 $$ The exactness
property means that the image of each homomorphism (linear transformation,
since we're working with vector spaces) is equal to the kernel of the next.
The shortness property means that $G$ is injective and $H$ is surjective.

% xxx Furthermore, since we're working over a vector space, the short exact
% sequence splits and have have an injection and a surjection going the other
% way.

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.  Next (xxx prove), it fortuitously happens that 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 given $G$, we can compute $H$ by simply taking
the kernel basis of $G$.

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 y$ is 0 only when $\vec y$ 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 y$ by $H$ just adds
up the bits of $\vec y$ mod 2.  The result will be zero precisely when $\vec y$
has even parity, which is the case iff $\vec y$ 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.

Also note that since $H$ checks elements of $C$, and since $G$ has rows forming
a basis for $C$, necessarily
$$ H G^t = 0 $$

%%% ----------------------------------------------------------------
%\subsection{Computing $H$ for systematic codes}
%
%IA/AI stuff for systematic codes
%
%$H G^t = 0$
%
%$G = [ I_k | A ]$
%
%$H = [ -A^t | I_{n-k} ]$
%
%
%$H = [ -A^t | I_{n-k} ]$
%
%$G^t = [ \frac{I_k}{A^t} ]$
%
%xxx see MS, and cite

%% ----------------------------------------------------------------
\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 millions or billions of
codewords.

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

A useful diagram from \cite{bib:ms}, attributed therein to a D.~Slepian, is the
following:

% xxx of the U. of What ...

\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 u = u_1\cdots u_k$}
\put(0.7,0.9){Message}
\put(1.9,1.1){$\vec x = x_1\cdots x_n$}
\put(1.95,0.9){Codeword}
\put(2.55,0.4){$\vec e = e_1\cdots e_n$}
\put(2.94,0.6){\vector(0,1){0.8}}
\put(2.55,0.2){Error vector}
%\put(3.2,1.1){$\vec y = y_1\cdots y_n$}
\put(3.2,1.1){$\vec y = \vec x + \vec e$}
\put(3.1,0.9){Received vector}
\put(4.5,1.1){$\hat{\vec u} = \hat{u}_1\cdots \hat{u}_k$}
\put(4.55,0.9){Estimate of}
\put(4.65,0.7){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), we have the following key fact:
\begin{eqnarray*}
	\vec y    &=& \vec x + \vec e \\
	H\vec y &=& H(\vec x+\vec e) = H\vec x + H\vec e = H\vec e
\end{eqnarray*}
This makes use of the fact that $H \vec x$ is zero for all codewords $\vec x$.

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

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

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, vectors in the same coset share the same syndrome.

xxx more facts

xxx the construction algorithm

%	msg_words = all of Fqk
%	code_words = G(msg_words)
%	syndromes = all of Fqnk
%	rcvd_words = all of Fqn
%
%	// for each syndrome
%	//   find coset leader: xlat of 0 vr such that syndrome == cur
%	//   print coset
%
%	for each s {
%		s = syndromes[i];
%		int min_weight = n;
%		int min_idx = -1;
%
%		for each recvd_word r with Hr == s {
%			if (w(r) < min_weight) {
%				min_weight = weight;
%				min_idx = j;
%			 }
%		}
%
%		tvector<intmod_t> leader = rcvd_words[min_idx];
%	}

xxx the decoding algorithm

\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 and their corresponding codewords are as follows:
\begin{eqnarray*}
	0 &\mapsto& 000 \\
	1 &\mapsto& 111
\end{eqnarray*}
Possible received vectors are:
$$
000,001,010,011, 100,101,110,111
$$
Possible syndromes are:
$$
00,01,10,11
$$
So the standard array looks like the following (using $s$ for syndrome):
$$
\begin{array}{ccc}
	 0  &  1  &  \\
	000 & 111 & s=00 \\
	010 & 101 & s=01 \\
	100 & 011 & s=10 \\
	001 & 110 & s=11 \\
\end{array}
$$

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

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

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

%% ================================================================
\newpage
\section{To-do pseudo-section}

xxx decoding error; other terms from MS

xxx rep 3 is simplex on the cube

xxx efficiency

xxx error rate

xxx simple codes

xxx params are n,k,d,q; maximize one

xxx hamming and simplex codes

xxx they aren't good either.

%xxx min dist vs. error correction; sphere packing

%xxx ``max likelihood''

%channel capacity

%xxx xref to bounds thms, and Shannon.
%
%xxx show the tradeoff between parameters
%
%xxx maximize which, given which
%
%xxx binary symmetric channel; p(err)

xxx pv IA/AI stuff for G/H when systematic.

xxx bsc

xxx nkdq ``params''

xxx d is norm

xxx when do we need weak (or no) codes:  kbd/mouse; modem.  vs. deep space,
or home power-line networking.

%% ================================================================
\newpage
\section{xxx Pointers}

xxx make sure to include ptrs to GOMs (shannon, hamming, golay, ...)

xxx put shannon in bib

xxx make sure to include ptrs to open problems

xxx what else: construct good codes and find efficient decoders.

xxx codes not over fields

xxx non-linear codes

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

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

% xxx and ch. 1 of ___, and ch. 1 of ___, and ... .
