Upload to Canvas a PDF of your work for the following problems. You will definitely want to type this one. A text listing of your R commands and output will suffice.

Assignment: due Wednesday, 11:59 pm

The Golay code \(G_{24}\) is a linear \([24,12]\) code that can correct \(t=3\) errors. The following lines of code will load the generating matrix golay24 and coset leader syndrome table gT into your local R environment.

golay24 <- matrix(c(1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,1,1,0,0,0,1,0,
                    0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,
                    0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,0,0,0,
                    0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,1,1,1,0,0,
                    0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,1,1,1,0,
                    0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,1,
                    0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1,
                    0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,1,0,1,1,0,1,
                    0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,
                    0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1,0,0,0,1,0,1,1,
                    0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,0,1,
                    0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1),
                  byrow=TRUE, nrow=12)
load(url("http://math.westmont.edu/data/golay24table.RData"))
gT[["001101011010"]] # example: use a syndrome to look up the coset leader

  1. Use the functions randInvMatrix and randPermMatrix to make Bob’s choice of appropriately-sized \(S\) and \(P\), respectively. Use at least 200 operations when you randomize. Tip: Set the random number seed using set.seed so you will be able to reproduce your work. Give \(S\), \(P\), and also the public key \(G_1\) that Bob publishes.

  2. Alice wishes to send the 12-bit message 101010101010. Use the randBinVector function to create an appropriately-sized and weighted random error vector \(e\), and compute the binary vector \(y\) that Alice sends.

  3. Show how Bob can decrypt the message by computing \(y_1\), computing its syndrome, using the coset leader syndrome table gT to obtain the code word \(x_1\), and then applying \(S^{-1}\) to the information bits to recover Alice’s original 12-bit message.

Helper Functions

randInvMatrix <- function(k, numops = 500) {
  M <- diag(k) # the k by k identity matrix
  Minv <- diag(k)
  rowOps <- replicate(numops, sample(1:k, 2))
  for(i in 1:numops) {
    M[rowOps[1,i],] <- (M[rowOps[1,i],] + M[rowOps[2,i],]) %% 2
    Minv[rowOps[1,numops-i+1],] <- (Minv[rowOps[1,numops-i+1],] + Minv[rowOps[2,numops-i+1],]) %% 2
  }
  return(list(M = M, Minv = Minv))
}
randPermMatrix <- function(n, numswaps = 500) {
  M <- diag(n)
  rowSwaps <- replicate(numswaps, sample(1:n, 2))
  for(i in 1:numswaps) {
    M[rowSwaps[,i],] <- M[c(rowSwaps[2,i],rowSwaps[1,i]),]
  }
  return(M)
}
randBinVector <- function(length, weight) {
  v <- numeric(length)
  oneLocs <- sample(1:length, weight)
  v[oneLocs] <- 1
  return(v)
}