68P05-Code.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{Code}
\pmcreated{2013-03-22 14:21:21}
\pmmodified{2013-03-22 14:21:21}
\pmowner{mathcam}{2727}
\pmmodifier{mathcam}{2727}
\pmtitle{code}
\pmrecord{9}{35835}
\pmprivacy{1}
\pmauthor{mathcam}{2727}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{68P05}
\pmclassification{msc}{68P30}
\pmdefines{code}
\pmdefines{block length}
\pmdefines{minimum distance}

\endmetadata

% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here

\newcommand{\mc}{\mathcal}
\newcommand{\mb}{\mathbb}
\newcommand{\mf}{\mathfrak}
\newcommand{\ol}{\overline}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\nor}{\vartriangleleft}
\newcommand{\Gal}{\text{Gal}}
\newcommand{\GL}{\text{GL}}
\newcommand{\Z}{\mb{Z}}
\newcommand{\R}{\mb{R}}
\newcommand{\Q}{\mb{Q}}
\newcommand{\C}{\mb{C}}
\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\begin{document}
Let $A$ be an alphabet.  A \emph{code over $A$} is any subset $C$ of the set of words $A^*$ on the alphabet $A$ such that $C$ has ``uniquue factorization into letters,'' i.e., such that for whenever $a_1\ldots a_n=b_1\ldots b_m$, with all $a_i,b_j\in C$, then we have $n=m$ and $a_i=b_i$ for all $i$. In other words, every ``word over $A$'' generated by $C$ (considered as an alphabet) can be uniquely factored into ``letters'' in C.  

An example of a subset of $A^*$ which is \emph{not} a code is given by $C=\lbrace ab, c, a, bc \rbrace$. Here the word $abc$ can be written either as $(ab)c$ or as $a(bc)$ in terms of elements of $C$. Since $ab \ne a$ nor $c\ne bc$, $C$ is not a code.

If we fix a length $n$ for the words, i.e. we require that $C\subset A^n$, then we call $C$ a \emph{block code}, and call $n$ the \emph{block length} of the code.  An important property of a code is the code's \emph{minimum distance}, given by the minimum Hamming distance between any pair of words in $C$.

This notion of code is obviously very general.  In practice (i.e., in coding theory) one typically takes codes with a little more structure.  See, in particular, linear codes.
%%%%%
%%%%%
\end{document}