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= dimension of the code. *parity check matrix has all columns pairwise linearly independent. Ex q=2, k=3, working over
n=

Ex q=2, k=2, n=

P=(-1 -1)
G=( P)= ( P)= ( P)= (1 -1 -1)
C=span( )

(1) G= generating matrix 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.
write G = ( P) is an nk matrix. is the identity matrix for a k-dimensional code, and there are n rows because the code is a subspace of . 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 = ( ) G= ( P) Ex Parity

H= = ( -1 -1 -1 1 ) [= ( 1 1 1 1 ) over ] x then is a codeword.

One way to define a code is through the parity check matrix. Ex Parity codes have H= (there are k-ones)
then G=( P)

Ex q=1, k=3, n=7

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

Ex q=4, k=2, n=5, dim(c)=n-k=5-2=3,
H=( ), now find peicewise linearly independent vectors in
= 0, 1, a, b (a=x, b=x+1)

Check is x= a codeword? Use parity check matrix. Hx= = 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 ?
*Can we change one element to get a codeword?
C= Span(

Theorem Hamming codes have a minimum distance of 3. (Perfect) we can fix one error
If x had been or some such vector, then there would have only been one error and we could have fixed it.

Next: Cyclic Codes Up: Linear Codes Previous: Parity Codes   Contents
Frederick Leitner 2004-09-01