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

$\displaystyle 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

$\displaystyle 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:

Let $ v\in F^n$ and let

$\displaystyle 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

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

proof: Let

$\displaystyle 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 \begin{displaymath}\left( \begin{array}{c} n\ i \end{array}\right)\end{displaymath} 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,

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

$ \Box$

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

$\displaystyle 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

$\displaystyle 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)$.


David Joyner 2007-09-03