TABLE OF CONTENTS In this section I survey the theory of error-correcting codes.
A binary code of length n is simply a nonempty set of binary vectors of length n. More generally, we have the following definition. Let Q be a finite set with q elements. A nonempty subset C of Q n = Q Q Q is called a q-ary code of length n.
The vectors belonging to a code are called code words. A code with only one code word is called trivial. Whenever convenient, codes are assumed to have at least two code words. The set Q is called the alphabet. We use the term vector for an n-tuple over an arbitrary alphabet, not only in the case when Q is a field. The elements of Q n are also called points or words. The set Q n is called the ( q-ary) Hamming space.
The Hamming distance between two vectors x = ( x 0 , x 1 ,...,x n ? 1), y =( y 0 , y 1 ,...,y n ?1) in Q n is the number of coordinates in which they differ, i.e.,
The Hamming distance satisfies the triangle inequality,
for all x , y , z ? Q n, and is a metric. If V ?
