{VERSION 6 0 "SGI MIPS UNIX" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 
{CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 3 0 -1 -1 -1 0 
0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 
0 0 1 1 0 0 0 0 0 0 1 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 19 "Linear Cyclic Codes" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 83 "This worksheet details the example
 of the linear cyclic code presented in the text." }}{PARA 0 "" 0 "" 
{TEXT -1 171 "The code has 128 code words hence it can encode the ASCI
I character set.\nThe code has hamming distance d(C) = 5 so it can cor
rect up to 2 errors and detect up to 4 errors." }}{PARA 0 "" 0 "" 
{TEXT -1 74 "Michael Monagan, October 1998, October 2002, November 200
7, November 2010." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "n := 2
^4-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"#:" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 21 "The codes will be in " }{XPPEDIT 18 0 "R = Z[2]
;" "6#/%\"RG&%\"ZG6#\"\"#" }{TEXT -1 1 "[" }{XPPEDIT 18 0 "x;" "6#%\"x
G" }{TEXT -1 3 "]/(" }{XPPEDIT 18 0 "x^n-1;" "6#,&)%\"xG%\"nG\"\"\"F'!
\"\"" }{TEXT -1 2 ")." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Fa
ctor( x^n-1 ) mod 2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*,,(*$)%\"xG\"
\"%\"\"\"F)*$)F'\"\"$F)F)F)F)F),(F%F)F'F)F)F)F),(*$)F'\"\"#F)F)F'F)F)F
)F),,F%F)F*F)F/F)F'F)F)F)F),&F'F)F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 51 "g := Expand( (x^4+x^3+1)*(x^4+x^3+x^2+x+1) ) mod 2;" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG,,*$)%\"xG\"\")\"\"\"F**$)F(\"
\"%F*F**$)F(\"\"#F*F*F(F*F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "
Construct the set Ig = \{ " }{XPPEDIT 18 0 "f(x)*g(x);" "6#*&-%\"fG6#%
\"xG\"\"\"-%\"gG6#F'F(" }{TEXT -1 3 " : " }{XPPEDIT 18 0 "f(x);" "6#-%
\"fG6#%\"xG" }{TEXT -1 4 " in " }{XPPEDIT 18 0 "R;" "6#%\"RG" }{TEXT 
-1 34 " \} .   Obviously we can't try all " }{XPPEDIT 18 0 "f(x);" "6#
-%\"fG6#%\"xG" }{TEXT -1 40 " because there are too many : there are \+
" }{XPPEDIT 18 0 "2^15;" "6#*$\"\"#\"#:" }{TEXT -1 13 " elements of " 
}{XPPEDIT 18 0 "R;" "6#%\"RG" }{TEXT -1 30 " .  But we know Ig should \+
have" }{TEXT -1 2 "  " }{XPPEDIT 18 0 "2^(15-8) = 128;" "6#/)\"\"#,&\"
#:\"\"\"\"\")!\"\"\"$G\"" }{TEXT -1 17 " elements. Hence." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 123 "Ig := \{0,g\}: f := 1:\nwhile nops
(Ig) < 128 do\n   f := Nextpoly(f,x) mod 2;\n   Ig := Ig union \{ Rem(
f*g,x^n-1,x) mod 2 \};\nod:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "He
re is one of the elements of Ig." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 6 "Ig[2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*$)%\"xG\"
\")\"\"\"F(*$)F&\"\"%F(F(*$)F&\"\"#F(F(F&F(F(F(" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 66 "C := map( proc(a) local i; [seq(coeff(a,x,i),i
=0..n-1)] end, Ig ):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "C[2]
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#71\"\"\"F$F$\"\"!F$F%F%F%F$F%F%F%
F%F%F%" }}}{EXCHG }{EXCHG }{EXCHG }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 11 "a := Ig[2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"aG,,*$)%\"x
G\"\")\"\"\"F**$)F(\"\"%F*F**$)F(\"\"#F*F*F(F*F*F*" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 11 "b := Ig[4];" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%\"bG,.*$)%\"xG\"\"*\"\"\"F**$)F(\"\"&F*F**$)F(\"\"$F*F**$)F(\"
\")F*F**$)F(\"\"%F*F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
15 "c := a-b mod 2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*$)%\"xG\"\"*
\"\"\"F(*$)F&\"\"&F(F(*$)F&\"\"$F(F(*$)F&\"\"#F(F(F&F(" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 49 "A clever way to calculate the Hamming dis
tance is" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "subs( x=1, c );
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"&" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 3 "So " }{XPPEDIT 18 0 "d(I[2],I[4]) = 5;" "6#/-%\"dG6$&%\"IG
6#\"\"#&F(6#\"\"%\"\"&" }{TEXT -1 82 " so the Hamming distance of this
 code is no more than 5.  \nLet's determine d(C).  " }{TEXT -1 51 " I'
ll print out a set of all the Hamming distances." }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 39 "d := proc(a,b) subs(x=1,a-b mod 2) end:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "\{ seq( d(c,0), c = Ig minus
 \{0\} ) \};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<)\"\"&\"\"'\"\"(\"\")
\"\"*\"#5\"#:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "So d(C) = 5 whic
h means we have 2 bits of error correction and 4 for error detection.
" }}}}{MARK "1 2 0" 31 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }
{PAGENUMBERS 0 1 2 33 1 1 }