next up previous contents
Next: About this document ... Up: Linear Codes Previous: Hamming Distance   Contents

Hamming Codes

One Good Code is the Hamming Code (it's a ``perfect code").
Define Hamming Code in terms of Its parity check matrix:
*n= $ \frac{q^n-1}{q-1}$ $ n-k=$ dimension of the code. *parity check matrix has all columns pairwise linearly independent. Ex q=2, k=3, working over $ \FF[2]$
n= $ \frac{q^3-1}{q-1}=\frac{2^3-1}{2-1}=7$
$ \FF[2]^4\longrightarrow\FF[2]^7$


Ex q=2, k=2, n= $ \frac{2^2-1}{2-1}=3$ $ \FF[2]^1\rightarrow\FF[2]^3$

$\displaystyle H$ $\displaystyle =$ $\displaystyle (1 1 1 1 1)$  
  $\displaystyle =$ $\displaystyle (-P^t I_{n-(n-k)} )$  
  $\displaystyle =$ $\displaystyle (-P^t I_k)$  
  $\displaystyle =$ $\displaystyle (-P^t \begin{array}{cc}1&0\\ 0&1 \end{array}) k=2$  
  $\displaystyle =$ $\displaystyle \left( \begin{array}{c\vert cc} 1&1&0\\ 1&0&1 \end{array}\right) \textrm{
over } \FF[2]$  

$ -P^t= {1 \choose 1}$ P=(-1 -1)
G=($ I_{dim}$ P)= ($ I_{n-k}$ P)= ($ I_1$ P)= (1 -1 -1)
C=span( $ \left( \begin{array}{c}1\\ -1 \\ -1 \end{array}\right)$ )
$ \FF[2]^1\rightarrow\FF[2]^3$
(1) $ \rightarrow \left( \begin{array}{c}1 \\ -1\\ -1 \end{array}\right)$ G= generating matrix $ \left( \begin{array}{c}\vec c_1t\\ \vec c_2t\\ \vec
c_3t \end{array}\right)
= \left( \begin{array}{cccc} 1&0&0&1\\ 0&1&0&1\\ 0&0&1&1 \end{array}\right)\\
=$rows of a generating matrix for a basis for the codewords. This matrix is in reduced-echelon form, and if not we can make it so.
% latex2html id marker 2794
$ \therefore$ write G = ($ I_k$ P) is an n$ x$k matrix. $ I_k$ is the identity matrix for a k-dimensional code, and there are n rows because the code is a subspace of $ \FF[2]^n$. C will always reduce to a reduced echelon matrix or the columns wouldn't be independent and C wouldn't be a code. H= parity check matrix = ($ P^t$ $ I_{n-k}$) G= ($ I_k$ P) Ex Parity $ \FF[q]^3 \longrightarrow \FF[q]^4$

$\displaystyle G$ $\displaystyle =$ $\displaystyle \left( \begin{array}{ccc\vert c} 1&0&0&1\\ 0&1&0&1\\ 0&0&1&1 \end{array}\right)$  
$\displaystyle G$ $\displaystyle =$ $\displaystyle \left(I_k \vert P\right)$  
$\displaystyle P$ $\displaystyle =$ $\displaystyle \left( \begin{array}{c}1\\ 1\\ 1 \end{array}\right)$  
$\displaystyle P^t$ $\displaystyle =$ $\displaystyle ( 1 1 1 )$  
$\displaystyle -P^t$ $\displaystyle =$ $\displaystyle ( -1 -1 -1 )$  

H= $ ( -P^t$ $ I_1)$= ( -1 -1 -1 1 ) [= ( 1 1 1 1 ) over $ \FF[2]$ ] $ H \vec x$ x $ \epsilon \FF[q]^n$ then $ H \vec x= 0$ $ \Leftrightarrow$ $ \vec x$ is a codeword.


One way to define a code is through the parity check matrix. Ex Parity codes have H= $ \overbrace{(\textrm{
-1 -1 -1 $\hdots$\ -1 1})}^{-P^t}$ (there are k-ones)
then G=($ I_k$ P)


Ex q=1, k=3, n=7 $ \FF[2]^4\rightarrow\FF[2]^7$

$\displaystyle H$ $\displaystyle =$ $\displaystyle (-P^t I_k)= \left( \begin{array}{cccc\vert ccc} 1&0&1&1&1&0&0\\ 1&1&0&1&0&1&0\\ 0&1&1&1&0&0&1 \end{array}\right)$  
$\displaystyle -P^t$ $\displaystyle =$ $\displaystyle \left( \begin{array}{cccc} 1&0&1&1\\ 1&1&0&1\\ 0&1&1&1 \end{array}\right)$  
$\displaystyle P$ $\displaystyle =$ $\displaystyle \left( \begin{array}{ccc} -1&-1&0\\ 0&-1&-1\\ -1&0 &-1\\ -1&-1&-1 \end{array}\right)$  
$\displaystyle G$ $\displaystyle =$ $\displaystyle (I_{n-k} P)= \left( \begin{array}{cccc\vert ccc}
1&0&0&0&-1&-1&0\\ 0&1&0&0&0&-1&-1\\ 0&0&1&0&-1&0 &-1\\
0&0&0&1&-1&-1&-1 \end{array}\right)$  

rows of G are a basis for C. 4 rows $ \Rightarrow$ 4 elements in basis, C is dim-4.

$\displaystyle \left( \begin{array}{c}1\\ 0\\ 0\\ 0 \end{array}\right)$ $\displaystyle \rightarrow$ $\displaystyle \left( \begin{array}{c}1\\ 0\\ 0\\ 0\\ -1\\ -1\\ 0 \end{array}\right)$  
$\displaystyle \left( \begin{array}{c}0\\ 0\\ 0\\ 1 \end{array}\right)$ $\displaystyle \rightarrow$ $\displaystyle \left( \begin{array}{c}0\\ 0\\ 0\\ 1\\ -1\\ -1\\ -1 \end{array}\right)$  
$\displaystyle \left( \begin{array}{c}0\\ 0\\ 1\\ 0 \end{array}\right)$ $\displaystyle \rightarrow$ $\displaystyle \left( \begin{array}{c}0\\ 0\\ 1\\ 0\\ -1\\ 0\\ 1 \end{array}\right)$  
$\displaystyle \left( \begin{array}{c}0\\ 1\\ 0\\ 0 \end{array}\right)$ $\displaystyle \rightarrow$ $\displaystyle \left( \begin{array}{c}
0\\ 1\\ 0\\ 0\\ 0\\ -1\\ -1 \end{array}\right)$  


Ex q=4, k=2, n=5, dim(c)=n-k=5-2=3, $ \FF[4]^3 \rightarrow \FF[4]^5$
H=($ -P^t$ $ I_k$), now find peicewise linearly independent vectors in $ \FF[4]^2$
$ \FF[4]=\{a+bx\vert a,b \epsilon \FF[4] \}$ = 0, 1, a, b (a=x, b=x+1)

$\displaystyle H$ $\displaystyle =$ $\displaystyle \left( \begin{array}{ccc\vert cc} 1&a&b&1&0\\ 1&b&a&0&1 \end{array}\right)$  
$\displaystyle P$ $\displaystyle =$ $\displaystyle \left( \begin{array}{cc} -1&-1\\ -a&-b\\ -b&-a \end{array}\right)$  
$\displaystyle G$ $\displaystyle =$ $\displaystyle \left( \begin{array}{ccccc} 1&0&0&-1&-1\\ 0&1&0&-a&-b\\
0&0&1&-b...
...left( \begin{array}{ccccc} 1&0&0&1&1\\ 0&1&0&a&b\\ 0&0&1&b&a \end{array}\right)$  
$\displaystyle C$ $\displaystyle =$ $\displaystyle Span(\left( \begin{array}{c}1\\ 0\\ 0\\ 1\\ 1 \end{array}\right),...
...end{array}\right),
\left( \begin{array}{c}0\\ 0\\ 1\\ b\\ a \end{array}\right))$  


$\displaystyle \FF[4]^3$ $\displaystyle \longrightarrow$ $\displaystyle \FF[4]^5$  
$\displaystyle \left( \begin{array}{c}1\\ 0\\ 0 \end{array}\right)$ $\displaystyle \longrightarrow$ $\displaystyle \left( \begin{array}{c}1\\ 0\\ 0\\ 1\\ 1 \end{array}\right)$  
$\displaystyle \left( \begin{array}{c}0\\ 1\\ 0 \end{array}\right)$ $\displaystyle \longrightarrow$ $\displaystyle \left( \begin{array}{c}0\\ 1\\ 0\\ a\\ b \end{array}\right)$  
$\displaystyle \left( \begin{array}{c}0\\ 0\\ 1 \end{array}\right)$ $\displaystyle \longrightarrow$ $\displaystyle \left( \begin{array}{c}
0\\ 0\\ 1\\ b\\ a \end{array}\right)$  

Check is x= $ \left( \begin{array}{c}1\\ 0\\ 0\\ a\\ b \end{array}
\right)$ a codeword? Use parity check matrix. Hx= $ \left( \begin{array}{ccccc} 1&a&b&1&0\\ 1&b&a&0&1 \end{array}\right)
\left( \begin{array}{c}1\\ 0\\ 0\\ a\\ b \end{array}\right)$ = $ \left( \begin{array}{c}1+a\\ 1+b
\end{array}\right) \neq 0$ Not a codeword. If you had received x, it was an error, and you would have to request it again.


Where was the error in $ \left( \begin{array}{c}1\\ 0\\ 0\\ a\\ b \end{array}
\right)$ ?
*Can we change one element to get a codeword?
C= Span( $ \left( \begin{array}{c}1\\ 0\\ 0\\ 1\\ 1 \end{array}\right), \left( \begin{arr...
...nd{array}\right)
= \left( \begin{array}{c}1\\ 0\\ 0\\ a\\ b \end{array}\right)$


Theorem Hamming codes have a minimum distance of 3. (Perfect) $ \Rightarrow$ we can fix one error
If x had been $ \left( \begin{array}{c}a\\ 0\\ 0 \\ a\\ b \end{array}\right)$ or some such vector, then there would have only been one error and we could have fixed it. Below is a second applet displaying how a code works. This applet encodes words using the Hamming Code( $ \FF[2]^4,\FF[2]^7$). This is the same code that was used in examples in this section. At the top, enter a word to be encoded. Upon hitting the ``encode" button, a box displaying the binary representation of the word will appear. Below the box with the binary string are boxes that show the encoded words over $ \FF[2]^7$. Because this code takes in words of four numbers, and our letters are represented by six numbers, the encoded blocks do not correspond to letters individually. After the codewords appear feel free to change the numbers around, simulating how errors are created. Press the ``parity check" button and the number of the first block with an error will appear. This applet only takes words six letters in length. If the word entered is too short, it will be padded with spaces. If the word is too long then the word will be trimmed to the appropriate length.


next up previous contents
Next: About this document ... Up: Linear Codes Previous: Hamming Distance   Contents
Frederick Leitner 2004-05-12