Upload to Canvas a PDF of your work for the following problems.

Assignment: due Wednesday 11/30, 11:59 pm

  1. Hamming codes have the following properties:
    • The nonzero syndromes are the columns of the parity check matrix \(H\).
    • For nearest neighbor decoding, the column of the syndrome is the location of the error.

The following commands compute the parity check matrix for the Hamming \([63,57]\) code.

m <- 6
powersOf2 <- 2^(0:(m-1))
ham63H <- sapply(c(setdiff(1:(2^m-1), powersOf2), powersOf2), 
                 function(x){as.numeric(intToBits(x)[1:m])})

The following message contains a single error. Decode it (without computing the entire coset and without a coset leader syndrome table). In which position was the error?

mess <- c(1,1,1,0,0,0,0,0,1,1,0,0,1,0,1,0,1,1,1,0,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,1,1,0,1,0,0,1,1,1,0,1,0,0)
  1. Let \(C\) be the (unique) \([15, 12]\) code residing in \(\mathbb{Z}_2/(x^{15} + 1)\).
    1. Use Macaulay2 to factor \(x^{15}+1\).
    2. Find the generating polynomial for \(C\).
    3. Find a parity check polynomial for \(C\).
    4. Determine whether \(x^{14} + x^{9} + x^5 + x^4 + x^2 + x + 1\) is a code word. Show how you can tell.
  2. Let \(C = \langle x^4+x^3+x^2+x+1 \rangle\) in \(\mathbb{Z}_2/(x^{2055} + 1)\).
    1. How many code words does \(C\) have?
    2. Show that the minimum distance of \(C\) is less than or equal to 2.
    3. Show that \(C\) contains a code word of weight \(20\). Find such a code word, and explain how you know it is a code word.