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= 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. Below is a second applet displaying how a code works. This applet encodes words using the Hamming Code( ). 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 . 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: About this document ... Up: Linear Codes Previous: Hamming Distance   Contents
Frederick Leitner 2004-05-12