Homework 15

General Comments

• Problem from the book are taken from the Chapter Review Problems sections.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).

Details

Do the following exercises.

Problem	Points
#1 below	6
#2 below	18
#3 below	6
#4 below	6

1. You must show all of your work for this problem to receive credit!
   1. Assume the following string was encoded with the Hamming Code discussed in class, and was transmitted over a noisy channel. Also assume that at most 1 error occurred in each 7-bit segment.

      Message: 1111100 1111010 1001111 1100001 0100010 0000011 1010001

      1. Try to decode the message (That is, give the hexadecimal characters that were encoded). If you are unable to decode one or more letters, explain why.
      2. Assuming you were able to decode some or all of the characters in the message, can you be certain that those were the characters that were sent? Explain.
      
      
   2. Assume the following string was encoded with the Hamming Code discussed in class, and was transmitted over a noisy channel, and that it is possible that at most 2 errors occurred in each 7-bit segment.

      Message: 1011010 1001001 1010110 1111100 0111110

      1. Try to decode the message (That is, give the hexadecimal characters that were encoded). If you are unable to decode one or more characters, explain why.
      2. Assuming you were able to decode some or all of the letters in the message, can you be certain that those were the characters that were sent? Explain.
   
   
2. Consider the string zip. This problem will explore the overhead associated with error-correcting codes.
   1. Encode the string using ASCII represented in binary.
   2. Encode the string using ASCII represented in hexadecimal.
   3. Encode the string from (a) with the Hamming Code discussed in class.
   4. Encode the string from (a) with the repetition code with k=3 discussed in class.
   5. How much larger is the binary string in (c) than the original in (a)? (Give your answer in the form of "x times larger".)
   6. How much larger is the binary string in (d) than the original in (a)? (Give your answer in the form of "x times larger".)
   7. Which code is more efficient in this case: The hamming code or the repetition code with k=3?
   8. Which code is able to correct more errors? Provide details.
   9. Which code is better? Why?
3. For this problem, assume that messages are written using the 26 characters from the English alphabet.
   1. Draw a chart that can be used to decrypt a string that was encrypted with the shift cipher with k=7. Use it to decode the string FVBNVAPAOHSMYPNOA.
   2. The string YBPROBQLAOFKHVLROLSXIQFKB was encrypted with a shift cipher with an unknown value of k.
      1. What was the original message?
      2. What value of k was used to encrypt the message?
      Hint: You need to try several values of k until you obtain a message that is readable. You may use an online tool to do this, but you should give the URL and provide all output in your homework.
4. There are times when people need to transmit data in such a way that it is secure, reliable, and efficient. Thus they may need to encrypt it, apply an error-correcting code, and compress it. Do you suppose it matters which order these operations are performed? In other words, should they apply an error-correcting code then compress it and then encrypt it, or do these three operations in some other order. Let's assume the data to be sent is a memo encoded in ASCII or Unicode. Suggest an order and clearly justify your ordering.
   Note: It is important to realize that these operations are performed in the reverse order at the receiving end. Also, think about the purpose of each of the three operations you are performing on the data. For instance, when you transmit the data, consider what happens if there are errors and/or someone intercepts the packet. Can you correct the errors using your order? Is the original message protected from an observer? You should also realize that if you encrypt it and then compress it or add error correction, the original data is still encrypted. In other words, encryption does not have to be the last thing you do. On the other hand, if you error-correct and then encrypt or compress, do you suppose you can still correct errors that occur?