{VERSION 3 0 "IBM INTEL LINUX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 78 "ERROR-CORRECTING CODES WITH MAPLE, Math 149 B, UC Davis. P rof. De Loera " }}{PARA 0 "" 0 "" {TEXT -1 79 "______________________ _________________________________________________________" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 92 "The purpose of thi s maple demonstration is to illustrate how to manipulate several kind s of" }}{PARA 0 "" 0 "" {TEXT -1 95 "LINEAR CODES. Recall that code is linear is it is a vector space over Z_2. There is always" }} {PARA 0 "" 0 "" {TEXT -1 37 "a parity matrix associated with it!" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 104 "In cod es that are not linear it is typically very difficult to c orrect errors because it" }}{PARA 0 "" 0 "" {TEXT -1 98 "involves c omparing the received word with all others!! We are going \+ to see that this" }}{PARA 0 "" 0 "" {TEXT -1 96 "is not the case f or linear codes, thus the correction process is much f aster!" }}{PARA 0 "" 0 "" {TEXT -1 73 "_______________________________ __________________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "EXAMPLE 1: BASIC LINEAR COD ES AND HAMMING CODES." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 81 "Consider the following parity matrix where \+ the columns of the matrix" }}{PARA 0 "" 0 "" {TEXT -1 89 "are \+ precisely the binary representations of the numbers 1, 2, 3, . \+ . ., 2^(m-1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "m:=4:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "H:= []:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "for j from 1 to 2^m- 1 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " cb:=convert(j,base,2):" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " bv:=vector(m,0);" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 32 " for i from 1 to vectdim(cb) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " bv[m-i+1]:=cb[i]:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 " H:=augme nt(op(H),bv):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evalm(H);" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "Now we wish to find out who the code associated to H." }}{PARA 0 "" 0 "" {TEXT -1 84 "REMEMBER the NULLSPACE or KERNEL of this matrix is pr ecisely the code, " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 61 "QUESTION: How many words live inside this \+ code?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 26 "CODE:=Nullspace(H) mod 2; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "These 11 vector s are only the GENERATORS, they are a basis for the code. " }}{PARA 0 "" 0 "" {TEXT -1 40 "we have 2^11 =2048 words in tot al." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 93 " \+ We have seen that the number of errors that we can corr ect is determined" }}{PARA 0 "" 0 "" {TEXT -1 95 "by the diamete r of the code. This is equal to the minimum weight of a \+ non-zero" }}{PARA 0 "" 0 "" {TEXT -1 89 "word in the code! Rathe r than going over all 2048 code words we can use" }} {PARA 0 "" 0 "" {TEXT -1 25 "the following theorem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "THEOREM: Let C b e a linear code with parity matrix H, and let s be the " }}{PARA 0 "" 0 "" {TEXT -1 84 "minimum number of linearly depen dent columns in H. Then s equals the" }}{PARA 0 "" 0 "" {TEXT -1 26 "diameter of the code." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "Note that in our example H we can find already 3 linearly dependent vectors!" }}{PARA 0 "" 0 "" {TEXT -1 90 "Therefore , we have diameter (Code)=3, thus at \+ most ONE error can be corrected!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 91 "Our matrix H is \+ very very special , the code we get receives the name of a" } }{PARA 0 "" 0 "" {TEXT -1 90 "HAMMING CODE, they have a simple correction process for one-error correction:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 " Suppose you receive \+ as a message, the vector " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "r:=vector([0,1,1,1,1,1,0,1,1 ,1,1,1,1,1,0]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 89 "To determine if an error happened in this \+ received vector, we multiply the " }}{PARA 0 "" 0 "" {TEXT -1 73 " matrix H with r. The answer receives the name of SYNDRO ME." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "syndrome:=map(x -> x mod 2, evalm( H &* r));" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "Be cause this syndrome is not [0,0,0,0] we know r is NOT \+ a codeword!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 48 "QUESTION: How to correct the error in r?" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "EXPLANATI ON: Suppose c was transmitted but we received r. " }}{PARA 0 "" 0 "" {TEXT -1 96 "Then r= c+e , e=error vector with ones i n the positions where c and r differ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 93 "Note that H* r= H * \+ c + H* e= H* e, hence if somehow we can find e from" }}{PARA 0 "" 0 "" {TEXT -1 53 "H*e = H*r , we could correct th e error... " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 39 "For Hamming codes this is easy!! " }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 " 1) just find the \+ column of H that matches the syndrome." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 82 " 2) The number of th is column in H will be the same as the number of" }}{PARA 0 " " 0 "" {TEXT -1 56 "of the position in r that contains the \+ error." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 40 "Here is how find it in MAPLE:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 6 "fc:=0:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " cn:=0:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "while (fc <> 1) \+ and (cn < 2^m-1) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " cn:=cn+1; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 " if equal(col(H,cn),syndrome)= true then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " fc:=1;" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 5 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od ;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "This indicates the error \+ in the vector r is in the 9th position!" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 72 "EXAMPLE 2: BCH CODES \+ ( a favorite of NASA's voyager mission!)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 " Coming soon to a theater near you!!" }}}}{MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 2 1 1805 }