# OK to post homework
# Alex Varjabedian, 4-Feb-2024, Homework 5

Help := proc() print(`Fqn(q, n)\nneighbor(q, c)\nSP(q, c, t)\nGRC(q, n, d)\nSPB(q, n, t)\nPlotkinBound(n, d)`) end:
with(linalg):

###############################
# --------------------------- #
# PART 1 - Textbook Exercises #
# --------------------------- #
###############################

print(`PART 1`);
print(`2.1`);
print(`(6, 2, 6): {000000, 111111}`);
print(`(3, 8, 1): {000, 001, 010, 011, 100, 101, 110, 111}`);
print(`(4, 8, 2): {0000, 0011, 1100, 1001, 0110, 1010, 0101, 1111}`);
print(`(5, 3, 4): Not possible. Without loss of generality, let's begin with 00000. Then, without loss of generality, let's choose 11110 as our next code. From this point, any code with a minimum distance of 4 from 11110 will not have a minimum distance of 4 from 00000.`);
print(`(8, 30, 3): Not possible. Using the sphere-packing bound, 30(1 + 8) <= 2^8, so 270 <= 256, which is not possible.`);
print(`2.2`);
print(`Suppose that C is a binary (n, M, d)-code. If we partition all codewords into two sets partitioned on whether their last digit is a 0 or 1, we will see that one of those partitions contains at least M/2 codewords. Finally, we can remove the last digit of each code in that partition to obtain an (n-1, M' >= M/2, d) code. Let M = A_2(n, d). Then, we now know that A_2(n-1, d) >= (1/2)A_2(n, d), so A_2(n, d) <= 2A_2(n-1, d).`);
print(`2.3`);
print(`From Exercise 1.5, we can identify a 3-ary (3, 9, 2)-code as {000, 101, 202, 011, 112, 210, 022, 120, 221}. We can generalize this to say that {(a, b, a + b) | (a, b) in (F_q)^2} is a q-ary (3, q^2, 2)-code, where a + b is taken mod q. This is because (F_q)^2 contains q^2 elements, so M = q^2. Therefore, M = A_q(3, 2) = q^2.`);
print(`2.4`);
print(`Suppose we add a parity check to (F_2)^(n-1). We can call this code C. Since every codeword in C has an even weight, we know that C is a subset of E_n. Also, any vector in E_n can be reached using a vector in (F_2)^(n-1). Therefore, E_n = C, so E_n is obtained by adding an overall parity check to (F_2)^(n-1). Furthermore, since E_n = C, and |C| = 2^(n+1), we have |E_n| = M = 2^(n-1). So, since (F_2)^(n-1) has d = 1, we have two cases: either d = 2 for E_n already, or it is possible that d = 1 for E_n. In the latter case, the parity check would be different, which would make d = 2. So, in both cases, d = 2. Therefore, E_n is an (n, 2^(n-1), 2)-code.`);

############################
# ------------------------ #
# PART 3 - GRC and SPB (1) #
# ------------------------ #
############################

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:

neighbor := 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 := proc(q, c, t) local S, s, i:
S := {c}:
for i from 1 to t do
 S := S union {seq(op(neighbor(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:

SPB := proc(q, n, t) local i:
trunc(q^n/add(binomial(n, i)*(q-1)^i, i = 0..t)):
end:

print(`For q = 2`);
print(`For d = 3`);
for n from 5 to 20 do
 grc := nops(GRC(2, n, 3)):
 spb := SPB(2, n, 1):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:
print(`For d = 5`);
for n from 5 to 20 do
 grc := nops(GRC(2, n, 5)):
 spb := SPB(2, n, 2):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:
print(`For d = 7`);
for n from 5 to 20 do
 grc := nops(GRC(2, n, 7)):
 spb := SPB(2, n, 3):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:

############################
# ------------------------ #
# PART 4 - GRC and SPB (2) #
# ------------------------ #
############################

print(`PART 4`);

print(`For q = 3`);
print(`For d = 3`);
for n from 5 to 10 do
 grc := nops(GRC(3, n, 3)):
 spb := SPB(3, n, 1):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:
print(`For d = 5`);
for n from 5 to 10 do
 grc := nops(GRC(3, n, 5)):
 spb := SPB(3, n, 2):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:
print(`For d = 7`);
for n from 5 to 10 do
 grc := nops(GRC(3, n, 7)):
 spb := SPB(3, n, 3):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:

############################
# ------------------------ #
# PART 5 - GRC and SPB (3) #
# ------------------------ #
############################

print(`PART 5`);

print(`For q = 5`);
print(`For d = 3`);
for n from 5 to 7 do
 grc := nops(GRC(5, n, 3)):
 spb := SPB(5, n, 1):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:
print(`For d = 5`);
for n from 5 to 7 do
 grc := nops(GRC(5, n, 5)):
 spb := SPB(5, n, 2):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:
print(`For d = 7`);
for n from 5 to 7 do
 grc := nops(GRC(5, n, 7)):
 spb := SPB(5, n, 3):
 printf("GRC: %d SPB: %d Difference: %d\n", grc, spb, spb - grc)
od:

##########################
# ---------------------- #
# PART 7 - Plotkin Bound #
# ---------------------- #
##########################

print(`PART 7`);

PlotkinBound := proc(n, d) 2*floor(d/(2*d - n)) end:

for d from 2 to 20 do
 for n from 2 to 2*d - 1 do
  pb := PlotkinBound(n, d):
  spb := SPB(2, n, floor((d - 1)/2)):
  if pb > spb then
   print(`Plotkin Bound`);
  elif spb > pb then
   print(`Sphere-Packing Bound`);
  else
   print(`EQUAL`);
  fi:
 od:
od: