#OK to post homework
#GLORIA LIU, Feb 10 2024, Assignment 7

read `C7.txt`:

#=====================================#
#1. Read and understand pp. 55-60 of Chapter 6 of the book. 
#Optionally, read (or at least skim) pp. 60-65. 
#Do a first reading of pp. 67-71.
#Done

#=====================================#
#2. p. 59, lines 7 and 8 from the bottom (that start with (a) and (b)) has two typos. Find them!
#I'm thinking that in the box with the channel + noise, the first noise should be 0100 (corresponding to a) 
#and the second noise should be 0001 (corresponding to b)

#=====================================#
#3. using Maple's rand(1..n) command write a procedure
#LC(N)
#that 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 result:
result := 0:
if rand(1..N)()=1 then
 result := 1
fi:
result:
end:

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

#=====================================#
#4. Write a procedure
#TestCode(q,n,C,N,K)
#that 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,co,n1,v1,i,j,T:
co:=0:
n1:=nops(C):
T:=DecodeT(q,n,C):
for j from 1 to K do:
 v:=C[rand(1..n1)()]:
 v1:=v:
 for i from 1 to nops(v1) do
  if LC(N)=1 then
   v1[i] := (v1[i] + 1) mod q
  fi:
 od:
 if T[v1]<>T[v] then
  co:=co+1:
 fi:
od:
evalf(co/K):
end:

#=====================================#
#5. With the above program, run it with q=2, n=7, K=10000, C=GRC(2,7,3) and
#N=2,3,4,5,6,7,8,9,10,15,20,30
#What were the failure rates for each choice of N above?

NList:=[2,3,4,5,6,7,8,9,10,15,20,30]:
q:=2: n:=7: K:=10000: C:=GRC(2,7,3):

for N in NList do
 print(N, TestCode(q,n,C,N,K)):
od:

#Failure Rate Results:
#2, 0.9361000000
#3, 0.7360000000
#4, 0.5572000000
#5, 0.4200000000
#6, 0.3402000000
#7, 0.2573000000
#8, 0.2085000000
#9, 0.1753000000
#10, 0.1486000000
#15, 0.07200000000
#20, 0.04290000000
#30, 0.02320000000

#=====================================#
#6. Finish procedure SA(q,n,M) that we just started. Test it with
#q=2,n=4, M=[[1,0,1,1],[[0,1,0,1]]]
#and see whether you get the sane as the standard array for the small code in Example 6.6 on p. 59 of Hill's book (make sure that your top row agrees with his).

#SA(q,n,M): inputs a basis Mof a linear [n,nops(M),d] code outputs Slepian's Standad Array
#as a matrix of vectors containing all the vectors in FGF(q)^n (Fqn(q,n)) such that
#the first row is an ordering of the members of the actual code (LtoC(q,M)) with
#[0$n] the first entry and the first columns are the coset representatives

addListsByIndex:=proc(cr,SL,q) local result,i,j,toAdd:
 result:=[0$nops(SL)]:
 for i from 1 to nops(SL) do
  toAdd:=[0$nops(SL[1])]:
  for j from 1 to nops(SL[1]) do
   toAdd[j]:=cr[j] + SL[i,j] mod q:
  od:
  result[i]:=toAdd:
 od:
 result:
end:

SAGloria:=proc(q,n,M) local SL,C,A,cr,result,i,SL1:
 result:=[]:
 C:=LtoC(q,M):
 C:=C minus {[0$n]}:
 SL:=[[0$n],op(C)]:
 result:=[op(result), SL]:
 A:=Fqn(q,n) minus {op(SL[1])}:
 #print(A);
 A:=A minus {op(SL)}:
 #print(A);
 #write a function minW(A) that finds a vector of smallest weight among A
 #choose it as the next coset representative
 #add it as the first entry of the next row, 
 while A <> {} do
  cr:=NN(A,[0$n])[1]:
  SL1:= addListsByIndex(cr, SL,q):
  #print(SL1):
  A:=A minus {op(SL1)}:
  result:=[op(result), SL1]:
  #print(A):
 od:
 result:
end:

check:=SAGloria(2,4,[[1,0,1,1],[0,1,0,1]]):
for i in check do
 print(i);
od:

#For that example a single error will be corrected if it takes place in 1,3,or 4th place but not 2nd