MATB24H3 Lecture Notes - Parity-Check Matrix, Hamming Weight, Generator Matrix

106 views9 pages
Published on 21 Apr 2013
School
UTSC
Department
Mathematics
Course
MATB24H3
University of Toronto at Scarborough
Department of Computer & Mathematical Sciences
MAT B24S Fall 2011
MAT B24
Lecture 13.
1 Binary Linear Codes
In this application messages will be encoded using the binary alphabet {0,1}=
B.Bwill be used to create message words that will be encoded, transmitted,
received and then decoded.
The Hamming 7-4 code starts with ‘messages’ that have length 4 each
rep. a letter. i.e. all possible messages: 24= 16.
space 0000
A 0001
B 0010
C 0011
D 0100
E 0101
F 0110
G 0111
H 1000
I 1001
J 1010
K 1011
L 1100
M 1101
N 1110
O 1111
To simply send these is simple but if an
error occurs then it cannot be detected. i.e.
say message received is 1 which decodes to
the word BEAN but the correct message is
2
B E A N
1) 0010 0101 0001 1110
there is one mistake and one
B E E F
2) 0010 0101 0101 0110
There is one mistake in each of the words
0001 and 1110 which are not detectable.
We want to detect single-error transmissions and to correct, the error.
1
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in
To do these we lengthen the words to have 7 characters where the last 3
‘check’ for errors. i.e. if x1, x2, x3, x4are the first 4 characters and the last 3
are given by equations carefully chosen.
EXAMPLE:
x5=x1+x3+x4
x6=x1+x2+x3
x7=x2+x3+x4
in Z2
these chosen equation are called parity check equations. Now the question
remains: How do we choose these equations?
The above equations give the following codes in Z7
2for the possible mes-
sages in Z4
2
message code no.
0000 0000000 0
0001 0001101 1
0010 0010111 2
0011 0011010 3
0100 0100011 4
0101 0101110 5
0110 0110100 6
0111 0111001 7
1000 1000110 8
1001 1001011 9
1010 1010001 10
1011 1011100 11
1100 1100101 12
1101 1101000 13
1110 1110010 14
1111 1111111 15
The coded words are in Z7
2. The final 3 characters are the parity-check
position of the message.
Definition: The Hamming weight of a word uis wt(u) = number of char-
2
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in
acters equal to 1.
Example: If u= 0110100, v = 0101110 find wt(u), wt(v).
wt(0110100) = 3 wt(0101110) = 4
Definition: If u, v are two words then let d(u, v) denote the number of
entries in uand vthat are different call this the distance between uand v.
Example: If u= 0110100,v= 0101110,w= 1111111 find d(u,v), d(v,w)
and d(u,w).
d(u,v) = 3 d(v,w) = 3 d(u,w) = 4
Definition: We add two words by adding corresponding characters in Z2.
Example: If u= 0110100,v= 0101110,w= 1111111 find u+v,v+wand
u+w.
u+v= 0011010 v+w= 1010010 u+w= 1001011
NOTE wt(u+v) = d(u,v).
Now a single error can occur in any one of the 7 characters.
If uis send and uis received with a single error then d(u, u) = 1 or
wt(u+u) = 1. To check for errors we check the parity check. If the code
words are at least 3 units apart then by looking to see the closest code word
to uwe can correct it. i.e. if u= 0100110 is received
=since we know
x5=x1+x3+x4
x6=x1+x2+x3
x7=x2+x3+x4
we know there is an error. We look and compare this to the rest of the code
words. For example the distance between uand u1is:
d(u,0001101) = 4
3
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

Already have an account? Log in

Document Summary

In this application messages will be encoded using the binary alphabet {0, 1} : b will be used to create message words that will be encoded, transmitted, received and then decoded. The hamming 7-4 code starts with messages" that have length 4 each rep. a letter. i. e. all possible messages: 24 = 16. space. To simply send these is simple but if an error occurs then it cannot be detected. i. e. say message received is 1 which decodes to the word bean but the correct message is. There is one mistake in each of the words. We want to detect single-error transmissions and to correct, the error. To do these we lengthen the words to have 7 characters where the last 3. Check" for errors. i. e. if x1, x2, x3, x4 are the rst 4 characters and the last 3 are given by equations carefully chosen.

Get OneClass Grade+

Unlimited access to all notes and study guides.

YearlyMost Popular
75% OFF
$9.98/m
Monthly
$39.98/m
Single doc
$39.98

or

You will be charged $119.76 upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.