Class Notes
(811,132)

Canada
(494,510)

University of Toronto Scarborough
(30,852)

Mathematics
(837)

MATB24H3
(13)

Sophie Chrysostomou
(12)

Lecture

# Lecture13.pdf

by
OneClass8101

Unlock Document

University of Toronto Scarborough

Mathematics

MATB24H3

Sophie Chrysostomou

Winter

Description

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. 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: 2 = 16.
space 0000
A 0001 To simply send these is simple but if an
B 0010
C 0011 error occurs then it cannot be detected. i.e.
say message received is 1 which decodes to
D 0100 the word BEAN but the correct message is
E 0101 2
F 0110
G 0111 B E A N
H 1000 1) 0010 0101 0001 1110
I 1001 there is onmistake ↑ and one ↑
J 1010 B E E F
K 1011 2) 0010 0101 0101 0110
L 1100
M 1101 There is one mistake in each of the words
N 1110 0001 and 1110 which are not detectable.
O 1111
We want to detect single-error transmissions and to correct, the error.
1 To do these we lengthen the words to have 7 characters where the last 3
‘check’ for errors. i.e.1if2x 3x 4x ,x are the ﬁrst 4 characters and the last 3
are given by equations carefully chosen.
EXAMPLE:
x5 = x 1 x +3x 4
x6 = x 1 x +2x 3 in Z2
x = x + x + x
7 2 3 4
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 Zor the possible mes-
4 2
sages in 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
7
The coded words are in Z 2 The ﬁnal 3 characters are the parity-check
position of the message.
Deﬁnition: The Hamming weight of a word u is wt(u) = number of char-
2 acters equal to 1.
Example: If u = 0110100,v = 0101110 ﬁnd wt(u),wt(v).
wt(0110100) = 3 wt(0101110) = 4
Deﬁnition: If u,v are two words then let d(u,v) denote the number of
entries in u and v that are diﬀerent call this the distance between u and v.
Example: If u = 0110100,v = 0101110,w = 1111111 ﬁnd d(u,v),d(v,w)
and d(u,w).
d(u,v) = 3 d(v,w) = 3 d(u,w) = 4
Deﬁnition: We add two words by adding corresponding characters in Z . 2
Example: If u = 0110100,v = 0101110,w = 1111111 ﬁnd u+v,v+w and
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 u is send and u is 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 u we can correct it. i.e. if u = 0100110 is received
=⇒ since we know
x 5 x +1x + x3 4
x 6 x +1x + x2 3
x 7 x +2x + x3 4
we know there is an error. We look and compare this to the rest of the code
′
words. For example the distance between u and u is: 1
d(u ,0001101) = 4
3 The distance of u and each of the codes is:
′ ′ ′
d(u ,u 0 = 3 d(u ,u )6= 2 d(u ,u )12 3
′ ′ ′
d(u ,u 1 = 4 d(u ,u )7= 5 d(u ,u )13 4
′ ′ ′
d(u ,u 2 = 3 d(u ,u )8= 2 d(u ,u )14 3
′ ′ ′
d(u ,u 3 = 4 d(u ,u )9= 5 d(u ,u )15 4
d(u ,u ) = 4 d(u u ) = 6
4 10
d(u ,u ) = 1 d(u ,u ) = 5
5 11
We note that d(u ,u ) is5the smallest, therefore the correct word is u . 5
This is time consuming so we want to develop a faster way.
2 Generator and Parity Check Matrices
So far this is what we want:
1. To lengthen the words from length 4 to 7.
2. To have minimum distance between two such words of 3.
3. To have a generator matrix G so that
wG = u w ∈ Z 4 u ∈ Z 7
2 2
such that u is the code word of message w.
4. To have a parity check matrix H that checks for errors and gives us
back the nearest neighbor decoding.
We will attempt to do this, keeping in mind that we have made the fol-
lowing assumption: only a single error transmission per code. Our
system will not correct codes with more than one error.
We now face the question we encountered earlier: How to create the
equations?
4 In our example we noticed that d(u,v) ≥ 3 for all u,v in the code.
We examine why this is true: If x = [x ,x 1x 2x 3x 4x 5x ]6an7 y =
[y1,y2,y3,4 ,5 ,6 ,7 ] then the last three digits were formed using
x5 = x 1 x +3x 4
x6 = x 1 x +2x 3 in Z2
x = x + x + x
7 2 3 4
Thus if x1,y1are diﬀerent =⇒ x ,y5, 5nd x ,y6al6o are. If x ,y2ar2
diﬀerent =⇒ x ,y , and x ,y also are. Thus, the equations should be
6 6 7 7
chosen so that (a) x aipears in at least 2 of them, and (b) each of
x5, x6, x7, must be the sum of 3 of x ,1▯▯ ,x .4This last restriction will
be explained later on.
Example: Determine if the following are good choices for parity check equa-
tions:
is not a good
x5 = x1+ x 2
selection of
x6 = x2+ x 3
parity check
x7 = x1+ x 3 equations
x5 = x 2 x 3 x 4
x = x + x + x is a good selection of
6 1 3 4 parity check equations
x7 = x 1 x 2 x 3
How to create G:
th
G has as the form [IX] and it has as an column the coeﬃcients a1▯▯▯an
of x ,x ,x ,x such that
1 2 3 4
a 1 1 a 2 +2a x3+3a x 4 4 i
EXAMPLE: If the parity check equations are:
x = x + x + x
5 1 3 4
x6 = x1+ x 2 x ,3 in Z2

More
Less
Related notes for MATB24H3