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 ${\bf v}=(v_1,v_2,...,v_n)$ , ${\bf w}=(w_1,w_2,...,w_n)$ are vectors in $V=F^n$ then we define

$$d({\bf v},{\bf w}) =\vert\{i \vert 1\leq i\leq n, v_i\not= w_i\}\vert$$

to be the Hamming distance between ${\bf v}$ and ${\bf w}$ . The function $d:V\times V\rightarrow \mathbb{N}$ is called the Hamming metric. The weight of a vector (in the Hamming metric) is $d({\bf v},{\bf0})$ .

Note that

$$d({\bf v},{\bf w}) =\vert\{i \vert 1\leq i\leq n, v_i-w_i\not= 0\}\vert =d({\bf v}-{\bf w},{\bf0})$$ (3.1)

for any vectors ${\bf v},{\bf w}\in F^n$ (or, more generally, any vectors in a linear code). Using this, it is easy to show that $d$ satisfies the properties of a metric:

• $d({\bf v},{\bf w})\geq 0$ for all ${\bf v},{\bf w}\in F^n$ and $d({\bf v},{\bf w})=0$ if and only if ${\bf v}={\bf w}$ .

• $d({\bf v},{\bf w})=d({\bf w},{\bf v})$ , for all ${\bf v},{\bf w}\in F^n$ .

• $d({\bf u},{\bf w})\leq d({\bf u},{\bf v})+d({\bf v},{\bf w})$ , for all ${\bf u},{\bf v},{\bf w}\in F^n$ .

Let $v\in F^n$ and let

$$B(v,r,F^n)=\{w\in Fn \vert d(v,w)\leq r\}.$$

This is called the ball of radius $r$ about $v$ . Since $F^n$ 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 $0\leq r\leq n$ and $q=\vert F\vert$ then

$$\vert B(v,r,F^n)\vert=\sum_{i=0}^r \left( \begin{array}{c} n\\ i \end{array} \right) (q-1)^i.$$

proof: Let

$$B_i(v,r,F^n) =\{w\in Fn \vert d(v,w)=i\}.$$

This is called the shell of radius $i$ about $v$ . It is consists of all vectors with exactly $i$ coordinates different from $v$ . There are $$\left( \begin{array}{c} n\\ i \end{array} \right)$$ ways to choose $i$ out of $n$ coordinates. There are $(q-1)^i$ ways to choose these $i$ coordinates to be different from those in $v$ . Thus,

$$\vert B(v,r,F^n)\vert=\sum_{i=0}^r \vert B_i(v,r,F^n)\vert ... ...t( \begin{array}{c} n\\ i \end{array} \right) (q-1)^i.$$

$\Box$

Example 3.3.6   If $F=\mathbb{F}_{11}$ and $V=F^{10}$ then

$$C=\{(x_1,x_2,...,x_{10}) \vert x_i\in F,\ x_1+2x_2+3x_3+...+9x_9+10x_{10}\equiv 0 ({\rm mod} 11)\}$$

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

For example, $(1,0,0,0,0,0,0,0,0,1)$ and $(1,1,1,1,1,1,1,1,1,1)$ are code words. Their Hamming distance is $8$ .

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 $1$ ), 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 $10$ ).

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

Definition 3.3.8   The weight distribution vector of a code $C\subset F^n$ is the vector

$$W(C)=(W_0,W_1,...,W_n)$$

where $W_i$ denote the number of codewords in $C$ of weight $1$ . Note that for an linear code $C$ , $W_0=1$ , since any vector space must contain the zero vector.

Example 3.3.9   In Example 3.3.2, the code $C$ has weight distribution vector $W(C)=(1,0,1,3,2,1)$ .