next up previous contents
Next: Hamming Codes Up: Linear Codes Previous: Parity Codes   Contents

Hamming Distance

Hamming Distance $ \alpha, \beta$ vectors in $ \FF[2]^n$ (or more generally $ \FF[q]^n$)

Hamming Distance, the distance between $ \alpha$ and $ \beta$

$\displaystyle d(\alpha, \beta) = \char93 $   $\displaystyle \mbox{of places where $\alpha$\ and $\beta$
disagree.}$$\displaystyle $



Ex
  1. $ \FF[2]^3$ d( $ \left( \begin{array}{c} 1\\ 0\\
0
\end{array} \right)$, $ \left( \begin{array}{c} 0\\ 1\\
1
\end{array} \right)) = 3$
  2. d( $ \left( \begin{array}{c} 1\\ 0\\
0
\end{array} \right)$, $ \left( \begin{array}{c} 1\\ 1\\
0
\end{array} \right)) = 1$
  3. d( $ \left( \begin{array}{c} 1\\ 0\\
0
\end{array} \right)$, $ \left( \begin{array}{c} 0\\ 1\\
0
\end{array} \right)) = 2$
  4. d( $ \left( \begin{array}{c} 1\\ 0\\
0
\end{array} \right)$, $ \left( \begin{array}{c} 1\\ 0\\ 0
\end{array} \right)) = 0$
  5. d( $ \alpha, \alpha$) = 0


(Codes) is C= set of codewords $ \leq \FF[2]^n$
We define the Hamming distance for C as

$\displaystyle d(C)=
min\{d(x,y)\vert x\neq y \epsilon C\}$

here we took $ x \neq y$ so that we did not get d(x,x)=0. We will use hamming distance to find the codeword closest to the decoded word and to correct an error in our encoded word. This is called ``maximum likelihood decoding". We won't be able to to this for the ``parity bit" codes but the ``Hamming codes" will let us fix one error (and detect up to three) in a received word.


Ex Minimum Distance for $ \FF[2]^2 \rightarrow
P \rightarrow \FF[2]^3$
C= \begin{displaymath}\{ \left( \begin{array}{c} 0 \\ 0 \\ 0 \end{array} \right),
...
...t),
\left( \begin{array}{c} 1 \\ 1 \\ 0 \end{array} \right) \}\end{displaymath}


\begin{displaymath}
\begin{tabular}{c\vert\vert c\vert c\vert c\vert c}
d & $\...
...} 1 \\ 1 \\ 0 \end{array}
\right)$&2&2&2&0\\
\end{tabular}
\end{displaymath}

Because C is a linear code, then:

$\displaystyle d(C)=min \{d(z,0)\vert\neq z\epsilon C\}$


$\displaystyle \textrm{because} d(x,y)$ $\displaystyle =$ $\displaystyle \textrm{\char93  places where x and y disagree}$  
  $\displaystyle =$ $\displaystyle \textrm{\char93  places where z=x-y are not zero}$  
  $\displaystyle =$ $\displaystyle d(z,0)$  

Minimum distance is 2.
next up previous contents
Next: Hamming Codes Up: Linear Codes Previous: Parity Codes   Contents
Frederick Leitner 2004-05-12