Class Notes (811,132)
Mathematics (837)
MATB24H3 (13)
Lecture

Lecture13.pdf

9 Pages
159 Views

School
University of Toronto Scarborough
Department
Mathematics
Course
MATB24H3
Professor
Sophie Chrysostomou
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.