#HW10 Nuray Kutlu

Hampcm:=proc(r,q) local A,i,a,Ham, id:
 Ham:=[]:
 A:= Fqn(q,r):
 for a in A do:
  i:= 1:
  while i<(nops(a)+1) and a[i]=0 do:
   i:=i=1:
  od:
  if i<(nops(a)+1) and a[i] =1 then:
   if a <> [0$(i-1),1, 0$nops(a)-i] then:
   Ham:= [op(Ham), [op(a)]]:
   fi:
  fi:
 od:
 for i from 1 to nops(Ham[1])  do
  id := [0$(i-1),1, 0$(nops(Ham[1]) -i)]:
  Ham := [op(Ham), [op(id)]]:
 od:
 Ham:=TRA(Ham):
 Ham:
end:

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


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

#DP(q,u,v):
DP:=proc(q,u,v) local i,n:
n:=nops(u):
add(u[i]*v[i],i=1..n) mod q:
end:
 
#Syn(q,H,y): The syndrom of the transmitted vector y if the PCM is H
#(a row vector of length n-k) 
Syn:=proc(q,H,y) local i:
[seq(DP(q,y,H[i]),i=1..nops(H))]:
end:


#Alphabet {0,1,...q-1}, Fqn(q,n): {0,1,...,q-1}^n
Fqn:=proc(q,n) local S,a,v:
option remember:
if n=0 then
 RETURN({[]}):
fi:

S:=Fqn(q,n-1):

{seq(seq([op(v),a],a=0..q-1), v in S)}:

end:


antiPCM:=proc(q,H) local A,B,M,n,rows,k,co,tempCol:
 rows:=nops(H): # this is n-k
 n:=nops(H[1]): # number of H columns
 k:= n-rows: 

 B:=extractMCols(1,k,H):                         # this is -A^T, we wish to return [I_k | A].
 tempCol := extractMCols(1,1,B):                 # take the first column, negate it
 A:= [[seq(op(tempCol[k]), k=1..nops(tempCol))]]:  # make the first column into a row
 
 for co from 2 to k do:
   tempCol := extractMCols(co,co,B): # take the (co)-th column 
   A:= [op(A), [seq(op(tempCol[k]), k=1..nops(tempCol))]]: # add the co-th column as a row
 od:

 A:= -A mod q: # we took the transpose, now we negate.

 co:=1:
 M:=A:
 for co from 1 to k do: #we will append the identity matrix row by row
  M[co] := [0$(co-1), 1, 0$(k-co),op(A[co])]:
 od:

 M:
end:

# a few helper functions:

# extracts rows i through j of matrix M, returns a matrix with those rows
extractMRows := proc(i,j,M) local colN,k:
 colN:=nops(M[1]): # number of columns of M
 [seq(M[k][1..colN] ,k=i..j)]
end:

# extracts columns i through j of matrix M, returns a matrix with those columns
extractMCols := proc(i,j,M) local rowN,k:
 rowN:= nops(M): # number of rows of M
 [seq( M[k][i..j] , k=1..rowN)]:
end:

#TRA(M): inputs a matrix M as a list of lists outputs the transpose matrix
#also as a list of lists
TRA:=proc(M) local i,j:[seq([seq(M[j][i],j=1..nops(M))],i=1..nops(M[1]))]:end: