#OK to post
#GLORIA LIU, Feb 22 2024, Assignment 10

read `C11.txt`:

#=====================================#
#1. Write a procedure
#Hampcm(r,q) that outputs the parity-check matrix (in standard form) of Ham(r,q),

#HamListHelper(r,q,d) outputs the list of all non-zero r-tuples whose first non-zero entry
#is at the d'th position, and is 1. 
HamListHelper:=proc(r,q,d) local i:
#print([op(Fqn(q,r-d))]);
[seq([0$(d-1), 1, op(i)], i in [op(Fqn(q,r-d))])]:
end:

wt:=proc(v) local i, result:
result:=0:
for i in v do
 if i<>0 then
  result:=result + 1:
 fi:
od:
result:
end:

Hampcm:=proc(r,q) local S,i,result,column:
S:=[]:
for i from 1 to r do
 S:=[op(HamListHelper(r,q,i)), op(S)]:
od:
#Permute columns to be in standard form
result:=[]:
for column in S do
 if wt(column) <> 1 then
  result:=[op(result), column]:
 fi:
od:
#append identity at end
result:=[op(result), seq([0$(i-1), 1, 0$(r-i)], i=1..r)]:
TRA(result):
end:

#=====================================#
#2. Write a procedure
#Ham(r,q)
#that outputs a generating matrix for Ham(r,q)
Ham:=proc(r,q)
antiPCM(q,Hampcm(r,q)):
end:

#=====================================#
#3.Using the bottom half of p. 88, write a procedure
#DecodeHamming(q,r,v)
#that decodes a received vector v if Ham(r,q) was used. Experiment with it, by coding a random 
#message vector, getting a code-word, randomly changing ONE place, and then decoding it. Did you get 
#the same thing?

DecodeHamming:=proc(q,r,v) local S,H,b,j,Ht,result:
H:=Hampcm(r,q):
S:=Syn(q,H,v):
if S=[0$(nops(H))] then
 RETURN(v):
fi:
Ht:=TRA(H):
for j from 1 to nops(Ht) do
 for b from 1 to q-1 do
  if S=b*Ht[j] then
   result:=[op(1..j-1, v), v[j]-b mod q, op(j+1..nops(v),v)]:
   RETURN(result):
  fi:
 od:
od:
end:

#Test DecodeHamming
TestDecodeHamming:=proc(q,r) local M,C,v,c,v1:
M:=Ham(r,q):
C:=LtoC(q,M):
v:=C[rand(1..nops(C))()]:
c:=rand(1..nops(v))():
v1:=v + [0$(c-1), 1, 0$(nops(v)-c)]:
if DecodeHamming(q,r,v1)=v then
 print(Success);
fi:
end: