# code

Let $A$ be an alphabet. A 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 not a code is given by $C=\{ab,c,a,bc\}$. Here the word $abc$ can be written either as $(ab)c$ or as $a(bc)$ in terms of elements of $C$. Since $ab\neq a$ nor $c\neq 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 block code, and call $n$ the block length of the code. An important property of a code is the code’s 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.

Title code Code 2013-03-22 14:21:21 2013-03-22 14:21:21 mathcam (2727) mathcam (2727) 9 mathcam (2727) Definition msc 68P05 msc 68P30 code block length minimum distance