You are to turn in this sheet as a cover page for your assignment. The rest of the assignment should be stapled to this page. See the website for details about where to turn in your assignment. This is an individual assignment, all of the work should be your own. Assignments that are unstapled, lack a cover sheet, or are difficult to read will lose at least 50% of the possible points and we may not grade them at all. If you use references other than the text and class notes, be sure to cite them!

The function P(x) returns the even parity of the bit string x.

1. Using even-one's parity find the parity of the following strings [3]
   1. 100101
   2. 101001
   3. 101111

2. What is the Hamming distance of the following sets?[4]
   1. {111,001}
   2. {1000,0000,1111}
   3. {1111,0000,1001}
   4. {110,101,011,000}

3. Using the 1-bit error correction scheme described in class,
   1. Find the parity bits for the following code:[6]

                    1       0   1   1       1   0   0            
         ---  ---  --- --- --- --- --- --- --- --- ---
          1    2    3   4   5   6   7   8   9   10  11
      

   2. Now, if bits 3 and 4 flip, what will the error correction scheme do?

   3. Consider the following error detection/correction scheme which covers the data bits A, B, C and D:
      X=P(A,B,C), Y=P(A,C,D), Z-P(A,C,D) This scheme does not provide 1 bit of error correction (that is the Hamming distance is less than 3). Do the following:[6]
      1. Show an example of a pair of legal codes which have a Hamming distance less than 3. (Hint: there are easier ways than just searching all 16 posibilties!)
      2. Find an illegal code which is just one bit flip away from two legal codes.

   4. Consider the following data stream: 101001.[11]
      1. Using the parity scheme described in class for the Veterbi algorithm, show what the parity bits would be.
      2. Say the 2nd data bit and the 4th parity bit went bad. Show how the Veterbi algorithm would attempt to correct the error. Draw the trellis.
      3. Does it correct the error?