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

read `C11.txt`:

#=====================================#
#1. Read and understand pp. 141-150 of Raymond Hill's book A First Course in Coding Theory .
#Done

#=====================================#
#2. Read and understand procedure Irreds(q,d,x) added after class. By finding the number of 
#irreducible polynomials over GF(q) of degree up to 8, and using the OEIS, find the following numbers
#(DO NOT do them directly!)
#nops(Irreds(q,20,x)), for q=2,5,7,11

#Find the irreducible polynomials up to degree 8:
#Commented out because it takes a long time to run
#for q in qList do
 #print(nops(Irreds(q,8,x)));
#od:

qList:=[2,5,7,11]:
for q in qList do
 print(NumIrreds(q,8));
 print(NumIrreds(q,20));
od:


with(NumberTheory):

NumIrreds:=proc(q,d) local factors,result,i:
factors:=Divisors(d):
(add(Moebius(i)*q^(d/i), i in factors))/d:
end:

#For degree 8:
#q=2: 30
#q=5: 48750
#q=7: 720300
#q=11: 26793030

#For degree 20:
#q=2: 52377
#q=5: 4768371093720
#q=7: 3989613300756720
#q=11: 33637499745331128504

#=====================================#
#3.Write a procedure
#MulTable(q,f,x)
#that inputs a prime q, a polynomial f (of x) and outputs the multiplication table in the 
#ring GF(q)[x]/f(x), where you order the non-zero polynomials of degree degree(f,x)-1, in 
#some order but starting at 1, both rows and columns are labeled by these polynomials and 
#computes a similar multipliction table as in the top of p. 144 (except don't have the 0). 
#Try to recreate that table.

MulTable:=proc(q,f,x) local T,d,i,P,p1,p2:
T:=table():
d:=degree(f,x):
P:=AllPols(q,d-1,x):
for p1 in P minus {0} do
 for p2 in P minus {0} do
  T[p1,p2]:= Mul(q,p1,p2,x,f):
 od:
od:
op(T):
end:

MulTable(2,x^2+x+1,x);

#=====================================#
#4. Pick your favorite irreducible polynomial of degree 3 over GF(q), construct its 
#multiplication table, with the rows and columns labelled by the non-zero polynomials over 
#GF(3) of degree ≤ 2, and verify that it is a field (i.e. that every row has a 1 in it)
#Now pick your favorite reducible polynomial, construct its multiplication table and show 
#that it is NOT a field, i.e. that there are some polynomials, mod f(x) (and mod q) that do 
#not have multiplicative inverses.

FieldChecker:=proc(q,f,x) local T,p1,p2,foundList,allPols,d:
foundList:=[]:
T:=MulTable(q,f,x):
d:=degree(f,x):
allPols:=AllPols(q,d-1,x):
for p1 in allPols do
 for p2 in allPols do
  if T[p1,p2]=1 then
   foundList:=[op(foundList), p1]:
   break:
  fi:
 od:
od:
#This should be the same as allPols except 0, if not, not a field
foundList:
end:

nops(AllPols(3,2,x));
nops(FieldChecker(3, 1+x+2*x^2+x^3, x));
nops(FieldChecker(3, x+x^2+x^3, x));

#=====================================#
#5. Since using the syndrom table takes too long for G24(), just treat it as a regular code (a 
#collection of 4096 members of GF(2)^24) and do the decoding by inputting a received vector of 
#length 24, and finding out whether the "sphere" of radius 3 around v belogs to LtoC(2,G24()), and 
#then decodes it to that vector. In fact make it more general and for a any code over GF(q)^n 
#write a procedure
#NearestNeigbor(C,v)
#that finds the member of C whose Hamming distance to v is minimal.

#Not sure how this is different from the NN(C,v) procedure we made in class?

NearestNeighbor:=proc(C,v)
NN(C,v):
end:

DecodeG24:=proc(v)
C:=LtoC(G24()):
NN(C,v):
end: