## The Hamming metric

We've seen so far come simple examples of codes. What is needed is some notion of how to compare codewords. Geormetrically, two codewords are far'' from each other if there are a lot'' of coordinates where they differ. This notion is made more precide in the following definition.

Definition 3.3.4   If , are vectors in then we define

to be the Hamming distance between and . The function is called the Hamming metric. The weight of a vector (in the Hamming metric) is .

Note that

 (3.1)

for any vectors (or, more generally, any vectors in a linear code). Using this, it is easy to show that satisfies the properties of a metric:

• for all and if and only if .

• , for all .

• , for all .

Let and let

This is called the ball of radius about . Since is finite, this ball has only a finite number of elements. It is not hard to count them using a little bit of basic combinitorics. Since this count shall be needed later, we record it in the following result.

Lemma 3.3.5   If and then

proof: Let

This is called the shell of radius about . It is consists of all vectors with exactly coordinates different from . There are ways to choose out of coordinates. There are ways to choose these coordinates to be different from those in . Thus,

Example 3.3.6   If and then

is called the ISBN code. This is an -ary linear code of length . This is the same code used in book numbering except that the number is denoted by on the inside cover of a book.

For example, and are code words. Their Hamming distance is .

Example 3.3.7   The U. S. Post Office puts a bar code on each letter to help with its delivery. What are these funny symbols? Translated into digits, they are given in the following table.

 number bar code 1 | | | | | 2 | | | | | 3 | | | | | 4 | | | | | 5 | | | | | 6 | | | | | 7 | | | | | 8 | | | | | 9 | | | | | 0 | | | | |

Each word'' in the postal bar-code has 12 digits, each digit being represented by short bars (we regard as a 0 ) and longer bars (which are regarded as a ), as above. The 12 digits are interpreted as follows: The first 5 digits are your zip code, the next 4 digits are the extended zip code, the next 2 digits are the delivery point digits, and the last digit is a check digit (all the digits must add to 0 mod ).

For example, suppose that after translating the bars into digits, you found that the postal code on an envelope was , where indicates a digit which was smudged so you couldn't read it. Since the sum must be 0 mod , we must have .

Definition 3.3.8   The weight distribution vector of a code is the vector

where denote the number of codewords in of weight . Note that for an linear code , , since any vector space must contain the zero vector.

Example 3.3.9   In Example 3.3.2, the code has weight distribution vector .

david joyner 2008-04-20