next up previous contents
Next: Cyclic Codes Up: Linear Codes Previous: Parity Codes   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 $ \mathbb{F}_{2}$
n= $ \frac{q^3-1}{q-1}=\frac{2^3-1}{2-1}=7$
$ \mathbb{F}_{2}^4\longrightarrow\mathbb{F}_{2}^7$


Ex q=2, k=2, n= $ \frac{2^2-1}{2-1}=3$ $ \mathbb{F}_{2}^1\rightarrow\mathbb{F}_{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 } \mathbb{F}_{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)$ )
$ \mathbb{F}_{2}^1\rightarrow\mathbb{F}_{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 3108
$ \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 $ \mathbb{F}_{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 $ \mathbb{F}_{q}^3 \longrightarrow \mathbb{F}_{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 $ \mathbb{F}_{2}$ ] $ H \vec x$ x $ \epsilon \mathbb{F}_{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 $ \mathbb{F}_{2}^4\rightarrow\mathbb{F}_{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, $ \mathbb{F}_{4}^3 \rightarrow \mathbb{F}_{4}^5$
H=($ -P^t$ $ I_k$), now find peicewise linearly independent vectors in $ \mathbb{F}_{4}^2$
$ \mathbb{F}_{4}=\{a+bx\vert a,b \epsilon \mathbb{F}_{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 \mathbb{F}_{4}^3$ $\displaystyle \longrightarrow$ $\displaystyle \mathbb{F}_{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.


next up previous contents
Next: Cyclic Codes Up: Linear Codes Previous: Parity Codes   Contents
Frederick Leitner 2004-09-01