#C7.txt, Feb. 8, 2024
Help:=proc(): print(` NN(C,v), DecodeT(q,n,C) , GLC1(q,M,d) , GLC(q,n,d)`):end:


#Feb. 5, 2024, C6.txt#C5.txt, Feb. 1, 2024
Help6:=proc(): print(`LtoC(q,M), MinW(q,M)`):end:


Help5:=proc(): print(`Nei(q,c), SP(q,c,t), GRC(q,n,d), GRCgs(q,n,d) , MinD(C), CV(S,n)`):
print(`BDtoC(BD,n)`):
end:

#Old code
#Jan. 29, 2024 C4.txt
Help4:=proc(): print(`Fqn(q,n), HD(u,v), RV(q,n) , RC(q,n,d,K), SPB(q,n,t), BDfano(), BDex212() `):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:

#Def. (n,M,d) q-ary code is a subset of Fqn(q,n) with M elements with
#minimal Hamming Distance d between any two members
#It can detect up to d-1 errors
#
#If d=2*t+1 correct t errors.
#
#
#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:

#SPB(q,n,d): The best you can hope for (as far as the size of C) for q-ary (n,2*t+1) code
SPB:=proc(q,n,t) local i:
trunc(q^n/add(binomial(n,i)*(q-1)^i,i=0..t)):
end:


#RV(q,n): A random word of length n in {0,1,..,q-1}
RV:=proc(q,n) local ra,i:
ra:=rand(0..q-1):
[seq( ra(), i=1..n)]:
end:

#RC(q,n,d,K): inputs q,n,d, and K and keeps picking K+1 (thanks to Nuray) random vectors
#whenver the new vector is not distance <=d-1 from all the previous one 
RC:=proc(q,n,d,K) local C,v,i,c:
C:={RV(q,n)}:
for i from 1 to K do
 v:=RV(q,n):
  if min(seq(HD(v,c), c in C))>=d then
   C:=C union {v}:
  fi:
od:
C:
end:

BDfano:=proc():
{{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}:
end:




BDex212:=proc():
{{1,3,4,5,9},
{2,4,5,6,10},
{3,5,6,7,11},
{1,4,6,7,8},
{2,5,7,8,9},
{3,6,8,9,10},
{4,7,9,10,11},
{1,5,8,10,11},
{1,2,6,9,11},
{1,2,3,7,10},
{2,3,4,8,11}
}
end:

#end of old code

#Nei(q,c): all the neighbors of the vector c in Fqn(q,n)
Nei:=proc(q,c) local n,i,a: 
n:=nops(c):
{seq(seq([op(1..i-1,c),a,op(i+1..n,c)], a=0..q-1) , i=1..n)}:
end:

#SP(q,c,t): the set of all vectors in Fqn(q,n) whose distance is <=t from c
SP:=proc(q,c,t) local S,s,i:
S:={c}:
for i from 1 to t do
 S:=S union {seq(op(Nei(q,s)),s in S)}:
od:
S:
end:

GRC:=proc(q,n,d) local S,A,v:
A:=Fqn(q,n):
S:={}:
while A<>{} do:
 v:=A[1]:
 S:=S union {v}:
 A:=A minus SP(q,v,d-1):
od:
S:
end:


#GRCgs(q,n,d): George Spahn's version
GRCgs:=proc(q,n,d) local S,A,v:
print(`Warning: use at your own risk`):
A:=Fqn(q,n):
S:={}:
while A<>{} do:
 v:=A[rand(1..nops(A))()]:
 S:=S union {v}:
 A:=A minus SP(q,v,d-1):
od:
S:
end:

#MinD(C): The minimal (Hamming) distance of the code C
MinD:=proc(C) local i,j:
min( seq(seq(HD(C[i],C[j]),j=i+1..nops(C)), i=1..nops(C))):
 end:

#CV(S,n): the characteristic vector of the subset S of {1,...,n}
CV:=proc(S,n) local v,i:
v:=[]:
for i from 1 to n do
 if member(i,S) then
  v:=[op(v),1]:
 else
  v:=[op(v),0]:
 fi:
od:
v:
end:

BDtoC:=proc(BD,n) local s, C:
C:={seq(CV(s,n),s in BD)}:
C:=C union subs({0=1,1=0},C):
C union {[0$n],[1$n]}:
end:

##end of old stuff
#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:

####end of old code
#start new code for C7.txt

#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:

#GLC1(q,M,d): tries to add a new member to the current basis M out of the other vectors
#that still has min. weight d
GLC1:=proc(q,M,d) local n,A,c,M1:
n:=nops(M[1]):
A:=Fqn(q,n) minus LtoC(q,M):
for c in A do
 M1:=[op(M),c]:
 if MinW(q,M1)=d then
   RETURN(M1):
 fi:
od:
FAIL:
end:




#GLC(q,n,d): inputs q and n and d (for min. distance) greedily and randomly tries to
#get as large a linear code given by a basis as possible)
GLC:=proc(q,n,d) local M,M1:
M:=[[1$d,0$(n-d)]]:
M1:=GLC1(q,M,d):
while M1<>FAIL do
 M:=M1:
 M1:=GLC1(q,M,d):
od:
M:
end:

#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 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 reprenatives

SA:=proc(q,n,M) local SL,C,A:
 C:=LtoC(q,M):
 C:=C minus {[0$n]}:
 SL:=[[0$n],op(C)]:
 A:=Fqn(q,n) minus {op(SL[1])}:
  #write a function minW(A) that finds a vector of smallest weight among A
  #choose it as the next coset represntatice a1
  #the next row is a1+SL[1]:

    #keep updating A until you run out of vectors in Fq(q,n)
end:








#HW6

#1
#2
	#5.1
	# the code (11,24,5) is not a linear code since 24 is not a prime power
	#5.2
	#For the set E_n the parameters of it as a code would be [n,n-1,2].  The choice of n is trivial.  The minimum distance is 2 since the smallest 
	#possible non-zero word in E_n would have to be a vector with 2 ones. This informs one that the basis has n-1 elements concisting of all 
	#vectors of the form [1,0...0,1,0...,0], where the 2nd 1 is at the ith position.  Since any binary vector of even weight can be decomposed
	#into k pairs of binary vectors of weight 2, we just need to construct all binary vectors of weight 2.  This is achieved by having a vector 
	#with 1s in positions i and j, and then taking the sum of  [1,0...0,1,0...,0] with the first vector having the second 1 in the ith position, and
	# the second vector have the second one in the jth position.  This sum mod 2 will cancel the first 1, and then will have the desired vector as 
	#the resulting sum.  The generator matrix G = (g_ij) with dimensions n-1 x n is given as follows.  for j in [n-1], g_jj = 1, g_jn = 1.   
	#5.3
	#TO prove that the set C = {x \in V(n,q): xH^t = 0} is a linear code all we need to do is show that it is a subspace.  Note that trivially 
	# [0,...,0]H^t = 0, if x \in C, then for l in Z, l x H^t = l*(x H^t) = l * 0 = 0, and if y \in C then (x+y)H^t = xH^t + yH^t = 0 + 0 = 0.
	# since C is a subspace, then it is a linear code.  
	#5.5
	#Let C be a linear code on V(n,2), and let E_C represent the subgroup (subcode?) with exclusively even weight.
	# Suppose that there exists a word y \in C such that w(y) = 2l + 1, where l is a non-negative integer.
	#Therefore for an arbitrary x in E_C, w(y+x) = w(y) + w(x) - 2w(x \cap y) = 2l + 1 + 2r + 2m (lemma 2.6), where r is a natural number, and m = w(x \cap y)
	#thus w(y+x) = 2(r + l + m) + 1.  Since w(y+x) is odd, then it is not in E_C.  Therefore E_C + y is a coset of E_C.  Furthermore if there exist
	# v \in C, w(v) = 2p+1, v \neq y, then w(y+v) = 2m+1 + 2p+1 - 2w(v \cap y) = 2(m + p + 1 - w(v \cap y)).  Since y+v has an even weight then 
	#y+v \in E_C.  Therefore y = y + 2v = y + v + v \in v + C.  Since the cosets y+C and v + C share an element, then they are the same.  Furthmore 
	# since E_C and y+E_C are cosets they have an equal number of elements.  
#3 
#SearchLC(q,n,k,K) inputs GF(q^n), k for the number of vectors for a given subspace, and the number of trial K.  Outputs the set of vectors with 
#the greatest minimum weight
SearchLC := proc(q,n,k,K) local M, M1, posmax, i:
	M := [seq(RV(q,n),i=1..k)]:
	posmax := MinW(q,M):
	for i from 1 to K do
		M1 := [seq(RV(q,n),i=1..k)]:
		if MinW(q,M1) > posmax then
			M := M1:
			posmax := MinW(q,M1):
		fi:
	od:
	RETURN([M,posmax]):
end:

#desired output:
(*  seq(seq(seq(print(SearchLC(q,n,k,1000)), q in {2,3,5}),n=4..10),k=3..5);
                                                      [[[0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1]], 4]

                                                      [[[1, 0, 1, 2], [0, 0, 0, 0], [1, 2, 0, 1]], 3]

                                                      [[[4, 0, 4, 1], [4, 2, 2, 2], [2, 3, 4, 2]], 3]

                                                 [[[1, 1, 1, 1, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0]], 4]

                                                 [[[0, 0, 0, 0, 0], [1, 2, 0, 2, 0], [2, 1, 1, 2, 1]], 3]

memory used=7020.7MB, alloc=515.5MB, time=67.51
                                                 [[[3, 4, 0, 3, 1], [4, 0, 2, 1, 1], [4, 4, 3, 2, 0]], 4]

                                             [[[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 0, 0], [1, 1, 0, 0, 1, 1]], 4]

                                             [[[2, 1, 2, 2, 0, 1], [0, 2, 1, 0, 1, 1], [2, 0, 0, 2, 1, 2]], 4]

memory used=7454.4MB, alloc=515.5MB, time=72.28
                                             [[[0, 4, 3, 2, 4, 3], [1, 4, 0, 3, 4, 2], [4, 4, 4, 4, 2, 3]], 4]

                                        [[[1, 0, 0, 1, 0, 1, 1], [1, 0, 0, 1, 0, 1, 1], [0, 1, 0, 0, 1, 1, 1]], 4]

                                        [[[0, 2, 2, 0, 0, 1, 1], [1, 0, 2, 0, 1, 1, 0], [2, 1, 0, 2, 0, 2, 1]], 4]

                                        [[[0, 3, 1, 2, 4, 2, 1], [2, 4, 2, 2, 3, 3, 3], [3, 0, 1, 4, 4, 3, 0]], 5]

                                    [[[1, 1, 0, 1, 1, 0, 0, 0], [1, 0, 1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 1, 1, 1, 1]], 4]

                                    [[[2, 1, 0, 1, 2, 0, 0, 1], [1, 1, 0, 1, 0, 2, 1, 0], [0, 0, 2, 1, 2, 2, 2, 0]], 5]

memory used=7981.3MB, alloc=547.5MB, time=77.52
                                    [[[3, 2, 3, 2, 3, 3, 1, 3], [2, 3, 3, 1, 3, 4, 1, 4], [4, 0, 4, 1, 0, 2, 2, 1]], 5]

                               [[[0, 1, 1, 0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 1, 1, 1]], 6]

                               [[[1, 1, 0, 2, 2, 0, 2, 2, 2], [1, 0, 0, 1, 2, 1, 1, 1, 2], [1, 0, 2, 2, 0, 1, 0, 2, 1]], 5]

memory used=8427.3MB, alloc=611.5MB, time=82.80
                               [[[4, 3, 4, 1, 3, 3, 4, 4, 0], [3, 1, 1, 3, 3, 2, 1, 4, 2], [0, 4, 1, 3, 0, 3, 3, 1, 4]], 6]

                           [[[1, 0, 1, 0, 1, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 1, 0, 1, 0, 1], [1, 1, 1, 1, 0, 0, 0, 1, 1, 0]], 6]

                           [[[0, 0, 2, 2, 1, 2, 1, 0, 2, 2], [1, 1, 1, 2, 0, 0, 1, 0, 0, 2], [2, 1, 1, 1, 0, 2, 2, 1, 1, 0]], 6]

memory used=8811.7MB, alloc=643.5MB, time=88.03
                           [[[0, 2, 3, 1, 0, 2, 2, 2, 1, 2], [0, 0, 0, 2, 4, 2, 3, 1, 2, 1], [1, 2, 4, 0, 2, 0, 1, 3, 1, 2]], 7]

                                               [[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]], 4]

                                               [[[2, 1, 2, 0], [0, 1, 2, 1], [0, 2, 1, 2], [2, 2, 2, 2]], 2]

memory used=9441.5MB, alloc=771.8MB, time=94.34
memory used=9654.3MB, alloc=771.8MB, time=98.73
                                               [[[1, 2, 1, 2], [4, 0, 4, 0], [0, 1, 4, 2], [3, 2, 1, 4]], 2]

                                         [[[0, 0, 0, 0, 0], [1, 0, 1, 1, 0], [1, 1, 1, 0, 1], [0, 0, 0, 0, 0]], 3]

                                         [[[0, 0, 1, 0, 2], [0, 1, 0, 1, 0], [2, 1, 1, 0, 1], [2, 1, 1, 2, 2]], 2]

memory used=10096.5MB, alloc=771.8MB, time=104.58
memory used=10311.2MB, alloc=771.8MB, time=109.77
memory used=10515.5MB, alloc=771.8MB, time=115.08
                                         [[[3, 1, 2, 3, 3], [3, 1, 4, 4, 0], [1, 4, 2, 3, 2], [1, 1, 4, 2, 2]], 3]

                                   [[[0, 0, 1, 1, 0, 1], [0, 1, 0, 0, 1, 1], [0, 1, 0, 0, 1, 1], [1, 0, 0, 1, 1, 0]], 3]

                                   [[[0, 0, 0, 2, 1, 2], [0, 0, 2, 0, 2, 2], [1, 1, 0, 1, 0, 1], [1, 1, 0, 0, 1, 0]], 3]

memory used=10953.3MB, alloc=771.8MB, time=122.41
memory used=11157.2MB, alloc=771.8MB, time=127.67
memory used=11319.7MB, alloc=771.8MB, time=132.38
memory used=11450.1MB, alloc=771.8MB, time=136.61
memory used=11554.9MB, alloc=771.8MB, time=140.55
memory used=11638.6MB, alloc=771.8MB, time=144.26
                                   [[[0, 3, 1, 0, 3, 0], [2, 1, 2, 0, 3, 2], [2, 4, 3, 0, 1, 2], [0, 4, 4, 3, 4, 2]], 3]

                             [[[0, 0, 0, 1, 0, 1, 1], [1, 0, 1, 0, 1, 0, 0], [1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 1, 1]], 3]

                             [[[2, 0, 2, 1, 0, 2, 0], [0, 1, 1, 0, 1, 1, 1], [1, 1, 1, 0, 0, 2, 2], [1, 2, 1, 1, 0, 0, 1]], 4]

memory used=11958.6MB, alloc=803.8MB, time=149.59
memory used=12015.8MB, alloc=803.8MB, time=153.41
memory used=12061.2MB, alloc=803.8MB, time=156.98
memory used=12098.0MB, alloc=803.8MB, time=160.58
memory used=12127.0MB, alloc=803.8MB, time=164.14
memory used=12150.4MB, alloc=803.8MB, time=167.56
memory used=12169.2MB, alloc=803.8MB, time=170.95
memory used=12184.1MB, alloc=803.8MB, time=174.66
memory used=12195.9MB, alloc=803.8MB, time=178.61
memory used=12205.3MB, alloc=803.8MB, time=182.56
memory used=12213.1MB, alloc=803.8MB, time=186.48
memory used=12219.4MB, alloc=803.8MB, time=190.23
memory used=12224.1MB, alloc=803.8MB, time=194.14
memory used=12228.0MB, alloc=803.8MB, time=197.86
memory used=12231.1MB, alloc=803.8MB, time=201.72
memory used=12233.5MB, alloc=803.8MB, time=205.27
memory used=12235.8MB, alloc=803.8MB, time=209.08
memory used=12237.4MB, alloc=803.8MB, time=212.95
memory used=12239.0MB, alloc=803.8MB, time=216.95
memory used=12239.8MB, alloc=803.8MB, time=221.36
memory used=12240.5MB, alloc=803.8MB, time=225.59
memory used=12241.3MB, alloc=803.8MB, time=231.03
memory used=12242.1MB, alloc=803.8MB, time=235.69
memory used=12242.4MB, alloc=803.8MB, time=239.62
memory used=12242.9MB, alloc=803.8MB, time=244.73
memory used=12242.9MB, alloc=803.8MB, time=249.41
memory used=12243.7MB, alloc=803.8MB, time=253.50
memory used=12243.7MB, alloc=1059.8MB, time=257.78
memory used=12673.9MB, alloc=1059.8MB, time=267.03
                             [[[1, 1, 2, 0, 1, 4, 0], [3, 2, 0, 0, 2, 2, 0], [4, 3, 4, 2, 4, 2, 1], [4, 0, 1, 1, 1, 3, 4]], 3]

                       [[[1, 0, 1, 1, 0, 1, 0, 0], [1, 0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1, 1]], 3]

                       [[[1, 2, 2, 0, 0, 0, 2, 1], [1, 0, 2, 2, 1, 2, 1, 1], [2, 2, 1, 0, 2, 2, 2, 0], [0, 2, 1, 1, 2, 0, 0, 1]], 4]

memory used=13178.9MB, alloc=1091.8MB, time=276.27
memory used=13609.9MB, alloc=1155.8MB, time=285.67
                       [[[3, 2, 2, 3, 0, 1, 3, 4], [1, 2, 1, 1, 1, 1, 3, 2], [0, 0, 4, 1, 4, 1, 4, 4], [0, 4, 1, 0, 4, 4, 0, 1]], 4]

                 [[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1, 0, 1, 1], [1, 1, 0, 0, 1, 1, 0, 1, 1], [1, 1, 1, 0, 1, 0, 1, 1, 0]], 4]

                 [[[1, 2, 0, 0, 2, 1, 2, 1, 2], [1, 0, 0, 2, 2, 0, 0, 2, 0], [0, 1, 1, 1, 1, 2, 0, 1, 2], [0, 2, 1, 2, 0, 2, 0, 0, 0]], 4]

memory used=14179.4MB, alloc=1187.8MB, time=300.52
memory used=14633.6MB, alloc=1251.8MB, time=312.70
                 [[[4, 4, 2, 2, 0, 2, 2, 2, 3], [0, 1, 1, 3, 3, 0, 0, 2, 0], [0, 1, 2, 3, 1, 0, 3, 0, 2], [3, 1, 2, 4, 1, 1, 2, 2, 0]], 5]

           [[[0, 1, 1, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 1, 0, 1, 0, 0, 1, 1], [0, 1, 1, 1, 1, 1, 0, 0, 0, 0], [1, 0, 1, 1, 1, 1, 1, 0, 1, 1]], 4]

           [[[0, 1, 1, 2, 1, 0, 0, 0, 1, 0], [2, 1, 0, 0, 1, 1, 1, 2, 2, 0], [1, 1, 0, 2, 1, 1, 2, 0, 1, 1], [0, 1, 0, 0, 0, 2, 1, 1, 1, 1]], 5]

memory used=15251.9MB, alloc=1283.8MB, time=327.67
memory used=15668.0MB, alloc=1347.8MB, time=341.86
           [[[2, 1, 2, 0, 4, 0, 1, 0, 1, 1], [0, 2, 4, 0, 1, 2, 1, 4, 4, 3], [0, 2, 1, 2, 0, 2, 3, 0, 1, 3], [1, 4, 4, 0, 2, 0, 1, 1, 2, 0]], 6]

memory used=16482.7MB, alloc=1539.8MB, time=359.00
                                        [[[0, 1, 1, 0], [0, 1, 1, 0], [1, 1, 0, 0], [0, 1, 0, 1], [1, 1, 1, 1]], 2]

                                        [[[2, 2, 1, 1], [2, 0, 0, 2], [0, 1, 0, 2], [0, 1, 2, 1], [1, 2, 2, 1]], 2]

memory used=17024.6MB, alloc=1539.8MB, time=375.05
memory used=17484.3MB, alloc=1571.8MB, time=390.06
memory used=17983.2MB, alloc=1571.8MB, time=408.56
                                        [[[0, 4, 4, 1], [1, 0, 3, 3], [3, 0, 3, 1], [2, 2, 3, 4], [3, 2, 0, 4]], 2]

                                [[[1, 0, 1, 0, 0], [0, 1, 1, 0, 1], [0, 1, 0, 1, 1], [0, 1, 1, 0, 1], [0, 0, 1, 1, 0]], 2]

memory used=18598.2MB, alloc=1603.8MB, time=426.47
                                [[[2, 0, 0, 0, 2], [2, 1, 1, 0, 2], [1, 0, 0, 1, 2], [0, 0, 1, 0, 1], [2, 0, 1, 2, 2]], 2]

memory used=19159.0MB, alloc=1603.8MB, time=442.41
memory used=19702.7MB, alloc=1603.8MB, time=460.80
memory used=20245.4MB, alloc=1603.8MB, time=484.70
memory used=20788.4MB, alloc=1603.8MB, time=500.12
memory used=21331.8MB, alloc=1603.8MB, time=513.88
                                [[[4, 3, 2, 3, 3], [4, 4, 4, 4, 3], [1, 2, 4, 2, 4], [0, 2, 3, 3, 0], [4, 4, 4, 3, 1]], 2]

                         [[[1, 0, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0], [1, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 1], [1, 1, 1, 0, 0, 1]], 3]

                         [[[0, 0, 0, 0, 1, 1], [2, 0, 2, 0, 0, 0], [0, 1, 1, 0, 0, 0], [2, 2, 2, 1, 2, 2], [2, 2, 2, 1, 0, 0]], 2]

memory used=22001.7MB, alloc=1603.8MB, time=527.08
memory used=22532.4MB, alloc=1603.8MB, time=540.41
memory used=23063.2MB, alloc=1603.8MB, time=554.30
memory used=23593.8MB, alloc=1603.8MB, time=568.42
memory used=24124.3MB, alloc=1603.8MB, time=583.26
memory used=24654.8MB, alloc=1603.8MB, time=598.11
memory used=25184.9MB, alloc=1635.8MB, time=612.73
                         [[[3, 3, 1, 0, 1, 1], [0, 4, 3, 1, 0, 3], [4, 3, 3, 2, 2, 1], [2, 2, 0, 3, 1, 4], [4, 1, 1, 4, 0, 4]], 3]

                 [[[0, 0, 0, 0, 0, 0, 0], [1, 0, 1, 1, 1, 0, 1], [0, 1, 0, 0, 1, 1, 1], [0, 0, 1, 1, 0, 1, 1], [1, 0, 1, 1, 1, 0, 1]], 3]

                 [[[2, 0, 1, 1, 2, 1, 0], [0, 2, 1, 0, 2, 0, 1], [1, 2, 1, 2, 2, 0, 0], [0, 1, 0, 1, 2, 0, 0], [0, 0, 0, 2, 1, 1, 1]], 3]

memory used=25902.6MB, alloc=1635.8MB, time=628.47
memory used=26481.7MB, alloc=1635.8MB, time=645.81
memory used=27060.8MB, alloc=1635.8MB, time=664.23
memory used=27639.6MB, alloc=1635.8MB, time=685.27
memory used=28218.5MB, alloc=1635.8MB, time=709.70
memory used=28797.3MB, alloc=1635.8MB, time=732.41
memory used=29375.9MB, alloc=1635.8MB, time=752.53
                 [[[0, 1, 2, 2, 2, 0, 3], [4, 0, 4, 3, 1, 4, 2], [3, 2, 0, 4, 4, 1, 4], [2, 1, 4, 4, 4, 1, 4], [1, 1, 0, 0, 3, 3, 2]], 3]

          [[[1, 1, 1, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 0, 1, 0], [0, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 0, 0, 1]], 3]

          [[[1, 2, 0, 2, 0, 0, 0, 0], [0, 0, 2, 2, 2, 0, 2, 0], [0, 1, 2, 1, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0, 1, 1], [0, 2, 2, 2, 1, 2, 0, 2]], 3]

memory used=30125.7MB, alloc=1667.8MB, time=771.92
memory used=30765.7MB, alloc=1699.8MB, time=792.53
memory used=31439.3MB, alloc=1699.8MB, time=811.81
memory used=32112.4MB, alloc=1699.8MB, time=836.26
memory used=32785.2MB, alloc=1699.8MB, time=858.70
memory used=33458.0MB, alloc=1699.8MB, time=886.33
          [[[3, 0, 0, 3, 4, 3, 4, 4], [0, 3, 1, 4, 0, 1, 1, 0], [1, 2, 0, 4, 1, 3, 4, 3], [1, 1, 4, 4, 0, 4, 0, 3], [1, 0, 3, 4, 3, 4, 1, 0]], 3]

  [[[1, 0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 1, 1, 0, 1, 1, 0], [1, 0, 1, 1, 1, 0, 0, 1, 1], [1, 1, 1, 1, 0, 0, 0, 1, 0], [0, 0, 1, 1, 1, 0, 1, 0, 1]], 3]

memory used=34274.3MB, alloc=1731.8MB, time=909.92
  [[[2, 0, 1, 2, 0, 1, 1, 0, 2], [1, 0, 1, 1, 1, 1, 0, 1, 0], [0, 1, 0, 2, 1, 2, 2, 0, 1], [0, 0, 2, 0, 1, 2, 1, 1, 2], [0, 2, 2, 0, 1, 1, 0, 2, 1]], 4]

memory used=34922.1MB, alloc=1827.8MB, time=935.83
memory used=35643.0MB, alloc=1891.8MB, time=959.36
memory used=36409.6MB, alloc=1923.8MB, time=994.97
memory used=37191.8MB, alloc=1955.8MB, time=1049.66
memory used=37994.1MB, alloc=1987.8MB, time=1080.52
  [[[4, 3, 1, 0, 2, 0, 2, 1, 2], [0, 0, 1, 2, 1, 1, 1, 2, 4], [2, 1, 2, 4, 4, 4, 3, 1, 4], [4, 0, 0, 0, 0, 0, 1, 1, 3], [3, 0, 3, 1, 4, 0, 2, 0, 2]], 4]

[[[1, 1, 0, 1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0, 1, 1], [1, 1, 1, 1, 1, 1, 0, 0, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0, 0],

    [1, 1, 1, 1, 0, 1, 1, 1, 0, 1]], 4]

memory used=38948.0MB, alloc=2019.8MB, time=1118.45
[[[0, 0, 0, 2, 2, 2, 0, 0, 1, 0], [1, 0, 1, 1, 2, 0, 1, 1, 1, 0], [1, 0, 0, 1, 2, 0, 1, 2, 2, 1], [1, 2, 0, 2, 1, 2, 0, 0, 0, 2],

    [0, 0, 1, 1, 2, 0, 0, 0, 2, 1]], 4]

memory used=39695.7MB, alloc=2115.8MB, time=1155.16
memory used=40409.1MB, alloc=2179.8MB, time=1186.44
memory used=41740.8MB, alloc=2755.8MB, time=1217.55
memory used=42578.9MB, alloc=2851.8MB, time=1249.73
memory used=43472.2MB, alloc=2915.8MB, time=1289.62
[[[2, 1, 4, 0, 3, 3, 2, 3, 4, 2], [4, 0, 2, 1, 3, 4, 2, 2, 0, 4], [3, 1, 2, 4, 4, 1, 1, 0, 0, 3], [2, 0, 0, 4, 1, 4, 3, 2, 1, 0],

    [1, 2, 1, 3, 0, 1, 3, 3, 4, 3]], 5] *)

#4
#I didn't have enough time to work out the bugs, for whatever reason it doesn't actual reduce the matrix.  
#adds a copies of row i to row j
(*
rowAdd := proc(q,M1,i,j,a) local M:
	M := M1:
	M[j] := (M[j]+a*M[i]) mod q:
	RETURN(M):
end:

rowSwap := proc(M1,i,j) local r,M:
	M := M1:
	r := M[i]:
	M[i] := M[j]:
	M[j] := r:
	RETURN(M):
	
end:

colSwap := proc(M1,i,j) local ci,l,k,M:
	M := M1:
	k := nops(M):
	ci := [seq(M[l][i], l=1..k)]:
	for l from 1 to k do
		M[l][i] := M[l][j]:
	od:
	for l from 1 to k do
		M[l][j] := ci[l]:
	od:
	RETURN(M):
end:


rowMult := proc(q,M1,i,a) local M:
	M := M1:
	M[i] := a*M[i] mod q:
	RETURN(M):
end:

SF := proc(q,M1) local h,i,j,k,n,M:
	M := M1 mod q:
	k := nops(M):
	n := nops(M[1]):
	for j from 1 to k do
		if M[j][j] = 0 then
			i := j+1:
			while M[j][j] = 0 and i < k+1 do
				if M[i][j] <> 0 then
					M := rowSwap(M,i,j):
					M := rowMult(q,M,j,M[j][j]&^(-1) mod q):
				fi:
				i := i + 1:	
			od:
			h := j + 1:
			while M[j][j] = 0 and h < n + 1 do
				if M[j][h] <> 0 then
					M := colSwap(M,j,h):
					M := rowMult(q,M,j,M[j][j]&^(-1) mod q):
				fi:
				h := h + 1;
			od:
		else
			M := rowMult(q,M,j,(M[j][j]&^(-1) mod q)):
		fi:
		i := 1:
		for i from 1 to n do
			if i <> j and M[i][j] <> 0 then 	
				rowAdd(q,M,j,i, -1*M[i][j] mod q):
			fi:
		od:
	od:
	M:
end:
*)

#HW7
#1
#2 I believe that the two typos are under channel + noise, where it just shows the same input vector and not the noise vector being added
#3
#LC(N)
LC := proc(N) local n:
	if N = 1 then 
		FAIL:
	else
		n := rand(1..N)():
			if n = N then 
				RETURN(1):
			else
				RETURN(0):
			fi:
	fi:
end:
#4 

TestCode := proc(q,n,C,N,K) local co,v,v1,i,j,T:
	T := DecodeT(q,n,C):
	co := 0:
	for i from 1 to K do:
		v := C[rand(1..nops(C))()]:
		v1 := [seq(v[j] + LC(N) mod q, j=1..n)]:
		if T[v1] <> v then 
			co := co + 1:
		fi:
	od:
	evalf(co/K):
end: