#OK to post homework
#Joseph Koutsoutis, 02-25-2024, Assignment 10

read `C11.txt`:

#1

Hampcm:=proc(r,q) local i,j,H,last_entries,v,id:
 H := MutableSet():
 last_entries := [[]]:
 
 #list all nonzero r-tuples whose first nonzero entry is 1
 for i from 0 to r-1 do:
  for v in last_entries do:
   insert(H, [0$(r-i-1), 1, op(v)]):
  od:
  last_entries := [seq(seq([j, op(v)], j=0..q-1), v in last_entries)]:
 od:

 #move columns to place the matrix in standard form
 id := [seq([0$(i-1), 1, 0$(r-i)], i=1..r)]:
 for v in id do:
  delete(H, v):
 od: 
 TRA([seq(v, v in H), op(id)]):
end:

#2

Ham:=proc(r,q): antiPCM(q, Hampcm(r,q)): end:

#3

DecodeHamming:=proc(q,r,v) local H,y,i,b:
 H := Hampcm(r,q):
 y := Syn(q,H,v):
 if y = [0$r] then return(v) fi:
 H := TRA(H):
 for i from 1 while y[i] = 0 do: od:
 b := y[i]:
 y := y / b mod q:
 for i from 1 while H[i] <> y do: od:
 v - [0$(i-1), b, 0$(nops(v) - i)] mod q:
end:



#test_decode tests our DecodeHamming method with q=q and r=r
#a total of t times. In each experiment, we generate a random
#codeword, change up to one place, and test to see if DecodeHamming
#is able to correct this error.
test_decode:=proc(q,r,t) local i,M,n,gen_place,gen_val,u,v,v1,k:
 M := Ham(r,q):
 n := (q^r-1)/(q-1):
 k := n - r:
 gen_place := rand(1..n):
 gen_val := rand(0..q-1):

 for i from 1 to t do:
  u := RV(q,k):
  v := Encode(q,M,u):
  v1 := Array(v): 
  v1[gen_place()] := gen_val(): 
  v1 := convert(v1,list):
  if v <> DecodeHamming(q,r,v1) then return(FAIL): fi:
 od:
 
 return(SUCCESS):
end:

#In the version of antiPCM in C11.txt, Maple doesn't like the assignment statement
#found on line 548 if the list is too long. I didn't want to touch the code since I didn't
#write it, so I just overrided antiPCM with the code below from a previous hw. 
#I do like the code currently included in C11.txt better though, and I'm pretty sure a small
#change in data structures would fix the error message.
antiPCM:=proc(q,H) local k,n,i,j,M:
n:=nops(H[1]):
k:=n-nops(H):

if [seq([op(k+1..n,H[i])],i=1..n-k)]<>[seq([0$(i-1),1,0$(n-k-i)],i=1..n-k)] then
 RETURN(FAIL):
fi:

for i from 1 to k do
 for j from 1 to k do
  if i=j then
   M[i,j] := 1:
  else
   M[i,j] := 0:
  fi:
 od:
 for j from k+1 to n do
  M[i,j] := -H[j-k,i] mod q:
 od:
od:
[seq([seq(M[i,j],j=1..n)],i=1..k)]:
end:


#Here I ran test_decode(q,r,100) for the values of q in [2,3,5,7] and r in [2,3,4,5].
#All of these tests succeeded. However, my code does not work if q is not prime.
#I think that I would need to use some of Maple's Galois field functions to fix this since
#all of my arithmetic is treating the entries as being in the ring Z/qZ rather than GF(q),
#but I didn't have time to fix this.
run_test_decode:=proc() local q,r:
 for q in [2,3,5,7] do:
  for r in [2,3,4,5] do:
   print(test_decode(q,r,100)):
  od:
 od:
end: