#Homework 7, Isaac Lam, February 12th 2024

#Class Code

#LtoC(q,M): inputs a list of basis vectors for our linear code over GF(q)
#outputs all the codewords (the actual subset of GF(q)^n with q^k elements
LtoC:=proc(q,M) local n,k,C,c,i,M1:
option remember:
k:=nops(M):
n:=nops(M[1]):
if k=1 then
 RETURN({seq(i*M[1] mod q,i=0..q-1) }):
fi:
M1:=M[1..k-1]:
C:=LtoC(q,M1):
{seq(seq(c+i*M[k] mod q,i=0..q-1),c in C)}:
end:


#MinW(q,M): The minimal weight of the Linear code generated by M over GF(q)
MinW:=proc(q,M) local n,C,c:
n:=nops(M[1]):
C:=LtoC(q,M):

min( seq(HD(c,[0$n]), c in C minus {[0$n]} )):

end:

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:

#HD(u,v): The Hamming distance between two words (of the same length)
HD:=proc(u,v) local i,co:
co:=0:
for i from 1 to nops(u) do
  if u[i]<>v[i] then
      co:=co+1:
  fi:
od:
co:
end:

#NN(C,v), inputs a code C (subset of Fqn(q,n) where n:=nops(v)) finds
#the set of members of C closest to v
NN:=proc(C,v) local i,rec,cha:
cha:={C[1]}:
rec:=HD(v,C[1]):
for i from 2 to nops(C) do
 if HD(v,C[i])<rec then
  cha:={C[i]}:
  rec:=HD(v,C[i]):
 elif HD(v,C[i])=rec then
   cha:=cha union {C[i]}:
 fi:
od:
  
cha:
end:

#Constructs once and for all a table that sends every member of Fqn(q,n) to one of
#its nearest neighbor
DecodeT:=proc(q,n,C) local S,v,T:
S:=Fqn(q,n):

for v in S do
T[v]:=NN(C,v)[1]:
od:
op(T):
end:

#End of Class Code

#3.
#LC(N)
#inputs a positive integer N, larger than 1, and outputs 1 with probability 1/N and 0 otherwise
#For example, LC(10) should output 1 about one tenth of the times.
#Test it out by doing
#add(x[LC(10)],i=1..10000);
#and make sure that it is close to 1000*x[1]+9000*x[0]

LC:=proc(N) local num:

num := 0:

if rand(1..N)()=1 then end if num := 1 end if:

num:

end:

add(x[LC(10)],i=1..10000);
1000*x[1]+9000*x[0];



#4. 
#TestCode(q,n,C,N,K)
# inputs a code q-ari code,C, on n letters a subset of GF(q)^n, a positive integer N and a large positive integer K and K times does the following
#Constructs, once and for all the table
#T:=DecodeT(q,n,C) :
#Picks a random member v, of C
#for each component of v, with probabiliy 1/N, changes it (you can add 1 mod q), getting a (possibly) distorted vector v1.
#See whether T[v1]≠ v. If it is add it to the counter
#output evalf(co/K)

TestCode:=proc(q,n,C,N,K) local v,count,length,vect,i,j,T:

count:=0:
length:=nops(C):
T:=DecodeT(q,n,C):

for j from 1 to K do:
     v:=C[rand(1..length)()]:
     vect:=v:
     for i from 1 to nops(vect) do
         if LC(N)=1 then
              vect[i] := (vect[i] + 1) mod q
         end if:
    end do:

    if T[vect]<>T[v] then count:=count+1 end if:

end do:

evalf(count/K):

end:


#5.

for N in [2,3,4,5,6,7,8,9,10,15,20,30] do:
 print(N, TestCode(2,7,GRC(2,7,3),N,10000)):
end do:


# N    Error Rate
# 2    0.9399
# 3    0.7385
# 4    0.5572
# 5    0.4164
# 6    0.3368
# 7    0.2730
# 8    0.2174
# 9    0.1864
#10    0.1509
#15    0.0738
#20    0.0433
#30    0.0219

#6. 

# SA(q,n,M): inputs a basis M of a linear [n,nops(M),d] code outputs Slepian's
# standard array as a matrix of vectors containing all the vectors in GF(q)^n (alas Fqn(q,n))
# such that the first row an ordering of the members of the actual code (LtoC(M)) with
# [0$n] the first entry and the first columns are the coset representatives
SA:=proc(q,n,M) local slepArr,C,A,r,coset:

    C:=LtoC(q,M);

    C:=C minus {[0$n]}:

    slepArr:=[[[0$n],op(C)]];
    A:=Fqn(q,n) minus {op(SL[1])};

    while nops(A) > 0 do:
        coset:=minW(A):

        slepArr:=[op(SL), [coset$n]+slepArr[1] mod q]:
        A:=A minus {op(slepArr[nops(slepArr)])}:
    end do:

    SL:
end;