{VERSION 6 0 "IBM INTEL LINUX" "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 "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 }1 0 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 }{PSTYLE "" 0 256 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 1 0 -1 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 67 "Michael Monagan, October 1998.\nUpdated October 2002, Nov
ember 2007." }}}{EXCHG }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "inte
rface(imaginaryunit=_i); # so we can use I for the set in the text" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#^#\"\"\"" }}}{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#%\"xG" }{TEXT -1 3 "]/(" }{XPPEDIT 18 0 "x^n-1;
" "6#,&)%\"xG%\"nG\"\"\"F'!\"\"" }{TEXT -1 2 ")." }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 22 "Factor( 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 52 "g := Expand( (x^4+x^3+1)*
(x^4+x^3+x^2+x+1) ) mod 2;\n" }}{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 24 "Construct the set I = \{ " }
{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 w
e 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 28 " .  It suffices? to try all " }{XPPEDIT 18 0 "f(x);
" "6#-%\"fG6#%\"xG" }{TEXT -1 17 " of degree up to " }{XPPEDIT 18 0 "n
-degree(g,x);" "6#,&%\"nG\"\"\"-%'degreeG6$%\"gG%\"xG!\"\"" }{TEXT -1 
72 ".  Another way to do this would be to find 7 linearly independent \+
codes." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 119 "I := \{g\}: f :=
 1:\nwhile degree(f,x) < 8 do\n   f := Nextpoly(f,x) mod 2;\n   I := I
 union \{ Rem(f*g,x^n-1,x) mod 2 \};\nod:" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 34 "Here is one of the elements of I.." }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 6 "I[2];\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$
)%\"xG\"#7\"\"\"F(*$)F&\"\")F(F(*$)F&\"\"'F(F(*$)F&\"#6F(F(*$)F&\"\"(F
(F(*$)F&\"\"$F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Now there sh
ould be " }{XPPEDIT 18 0 "p^(n-deg(g,x));" "6#)%\"pG,&%\"nG\"\"\"-%$de
gG6$%\"gG%\"xG!\"\"" }{TEXT -1 37 " elements in I which in this case i
s " }{XPPEDIT 18 0 "2^7 = 128;" "6#/*$\"\"#\"\"(\"$G\"" }{TEXT -1 3 ".
  " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(I);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#\"$G\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "C
heck that I is cyclic." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 142 "
for i to nops(I) do\n    a := expand(x*I[i]);\n    if degree(a,x)=n th
en a := 1+a-x^n fi;\n    if not member(a,I) then print(not cyclic); fi
;\nod:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "Now check the dimension
 of I over " }{XPPEDIT 18 0 "Z[2];" "6#&%\"ZG6#\"\"#" }{TEXT -1 40 " .
  It should be 7.  We create a matrix " }{XPPEDIT 18 0 "A;" "6#%\"AG" 
}{TEXT -1 127 " where each element of I becomes a row in the matrix an
d reduce the matrix to row echelon form to  find the rank of the matri
x." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "C := map( proc(a) loc
al i; [seq(coeff(a,x,i),i=0..n-1)] end, I ):" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 23 "A := Matrix( [op(C)] ):" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 28 "B := Gausselim(A,'r') mod 2:" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 14 "dimension = r;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#/%*dimensionG\"\"(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
31 "Print out a basis for the code." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 25 "B := convert(B,listlist):" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 60 "C := map( proc(u) cat(op(u)) end, B[1..7] );       \+
        \n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"CG7)%011000110011111
0G%0011001111101100G%0001100111110110G%0000101001101110G%0000011010010
101G%0000001110100010G%0000000111010001G" }}}{EXCHG }{EXCHG }{EXCHG 
{PARA 256 "" 0 "" {TEXT -1 34 "Now construct the finite field GF(" }
{XPPEDIT 18 0 "2^4;" "6#*$\"\"#\"\"%" }{TEXT -1 8 ") using " }
{XPPEDIT 18 0 "Z[2];" "6#&%\"ZG6#\"\"#" }{TEXT -1 2 " [" }{XPPEDIT 18 
0 "y;" "6#%\"yG" }{TEXT -1 3 "]/(" }{XPPEDIT 18 0 "y^4+y+1;" "6#,(*$%
\"yG\"\"%\"\"\"F%F'F'F'" }{TEXT -1 17 ") and check that " }{XPPEDIT 
18 0 "y;" "6#%\"yG" }{TEXT -1 24 " is a primitive element." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "powers := [seq( Rem(y^i,y^4+y+1,y) \+
mod 2, i=1..15 )];\n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'powersG71%
\"yG*$)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'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 19 "nops(\{op(powers)\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#:" }
}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "Now find which " }{XPPEDIT 18 0 
"alpha = y^(2^i);" "6#/%&alphaG)%\"yG)\"\"#%\"iG" }{TEXT -1 15 "  are \+
roots of " }{XPPEDIT 18 0 "g(x);" "6#-%\"gG6#%\"xG" }{TEXT -1 2 " ." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "zeroes := [seq( Rem(eval(g
,x=a),y^4+y+1,y) mod 2, a=powers) ];\n" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%'zeroesG71\"\"\"F&\"\"!F&F&F'F'F&F'F&F'F'F'F'F&" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 16 "Confirming that " }{XPPEDIT 18 0 "y^(2^i)
;" "6#)%\"yG)\"\"#%\"iG" }{TEXT -1 15 " are roots for " }{XPPEDIT 18 
0 "i = 11,12,13,14;" "6&/%\"iG\"#6\"#7\"#8\"#9" }{TEXT -1 2 " ." }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "Now the theory says that the hammi
ng distance of this code, " }{XPPEDIT 18 0 "d(C);" "6#-%\"dG6#%\"CG" }
{TEXT -1 22 " is at least 5.  Check" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 6 "I[2];\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$)%\"xG
\"#7\"\"\"F(*$)F&\"\")F(F(*$)F&\"\"'F(F(*$)F&\"#6F(F(*$)F&\"\"(F(F(*$)
F&\"\"$F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "I[4];\n" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#,.*$)%\"xG\"#7\"\"\"F(*$)F&\"\")F(F(*$
)F&\"\"&F(F(*$)F&\"#5F(F(*$)F&\"\"$F(F(*$)F&\"\"#F(F(" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "I[2]+I[4] mod 2;\n" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#,.*$)%\"xG\"#6\"\"\"F(*$)F&\"\"(F(F(*$)F&\"\"&F(F(
*$)F&\"#5F(F(*$)F&\"\"'F(F(*$)F&\"\"#F(F(" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 3 "So " }{XPPEDIT 18 0 "d(I[2],I[3]) = 5;" "6#/-%\"dG6$&%\"IG
6#\"\"#&F(6#\"\"$\"\"&" }{TEXT -1 76 " so the hamming distance of this
 code is no more than 5.  \nLet's check that " }{XPPEDIT 18 0 "5 <= d(
a,b);" "6#1\"\"&-%\"dG6$%\"aG%\"bG" }{TEXT -1 54 " .  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 11 "d(I[2],0);\n" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#\"\"'" }}}{EXCHG }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 38 "min( seq( d(c,0), c = I minus \{0\} ) );" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#\"\"&" }}}{EXCHG }{EXCHG }{EXCHG }{EXCHG }{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "40 0 0" 0 }{VIEWOPTS 1 1 0 1 
1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }