# OK to post homework
# Alex Varjabedian, 7-Feb-2024, Homework 6

Help := proc() print(`Fqn(q, n)\nLtoC(q, M)\nMinW(q, M)\nSearchLC(q, n, k, K)\nweight(v)`) end:
with(linalg):

###############################
# --------------------------- #
# PART 2 - Textbook Exercises #
# --------------------------- #
###############################

print(`PART 2`);
print(`5.1`);
print(`No, a binary [n, k, d]-code is also a binary (n, 2^k, d)-code, but 24 is not a power of 2, so this is not a linear code.`);
print(`5.2`);
print(`The paramters of E_n are [n, n-1, 2]. Since k = n - 1, our generator matrix is`);
matrix(5, 2, [``, 1, ``, 1, I[` n - 1`], `...`, ``, 1, ``, 1]);
print(`5.3`);
print(`We must show that C is closed under vector addition and scalar multiplication. Let x, y be in C. Then,`);
(x + y)*H^T;
`` = x*H^T + y*H^T;
`` = `0 + 0`;
`` = 0;
print(`Therefore, x + y is in C. Now, let x be in C and a be in GF(q). Then,`);
`(ax)`*H^T;
`` = a(x*H^T);
`` = `a*0`;
`` = 0;
print(`Therefore, ax is in C, so C is a linear code.`);
print(`5.5`);
print(`Let v, w be codewords of a binary linear code. Suppose that v has an odd weight. If w has an even weight, then v + w has an odd weight. Else, if w has an odd weight, then v + w has an even weight. So, we can define a bijection f(w) = v + w between the sets of even-weighted codewords and odd-weighted codewords. Therefore, these two sets have the same cardinality and, since they partition the binary linear code, we have proven that half of the codewords have even weight and the other half have odd weight.`);

#################################
# ----------------------------- #
# PART 3 - SearchLC(q, n, k, K) #
# ----------------------------- #
#################################

print(`PART 3`);

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:

LtoC := proc(q, M) local n, k, C, i, M1, c:
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 := 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:

weight := proc(v) local w, pos:
w := 0:
for pos in v do
 if pos <> 0 then w := w + 1 fi:
od:
w:
end:

SearchLC := proc(q, n, k, K) local fqn, subset1, element, minimum, i, minw, local_min:
minimum := [0]:
for i from 1 to K do
 fqn := Fqn(q, n):
 subset1 := {}:
 while nops(subset1) <> k do
  element := fqn[rand(1..nops(fqn))()]:
  fqn := fqn minus {element}:
  subset1 := subset1 union {element}:
 od:
 local_min := subset1[1]:
 minw := MinW(q, subset1):
 for element in subset1 do
  if minw = weight(element) then local_min := element fi:
 od:
 if weight(local_min) >= weight(minimum) then minimum := local_min fi:
od:
minimum:
end:

# For q = 2
print(`q = 2`);
for n from 4 to 10 do
 for k from 3 to 5 do
  print(SearchLC(2, n, k, 1000));
 od:
od:

# For q = 3
print(`q = 3`);
for n from 4 to 10 do
 for k from 3 to 5 do
  print(SearchLC(3, n, k, 1000));
 od:
od:

# For q = 5
print(`q = 5`);
for n from 4 to 10 do
 for k from 3 to 5 do
  print(SearchLC(5, n, k, 1000));
 od:
od: