Due 1:30 PM, Wednesday, 21 February 2018


CPSC 101b  Homework #4  Redundancy: Error Detection and Correction

Note: The assignment is due IN CLASS on the date above.

REMINDER:  When discussing an assignment with other students, you may write on
a board or a piece of paper, but you may not retain any written or electronic
record of the discussion.  Moreover, you must engage in a full hour of mind-
numbing activity (e.g., watching back-to-back episodes of Gilligan's Island)
before you work on the assignment again.  This ensures that you can reconstruct
what you learned from the discussion, by yourself, using your own brain.  The
same rule applies to nonstudents and on-line sources.


1. a. (2 points) Compute the check digit for the credit card number
      4169-9732-9725-088? (where ? denotes the check digit).

   b. (2 points) Show that either ABCD-EFG9-0JKL-MNPQ and ABCD-EFG0-9JKL-MNPQ
      are both valid credit card numbers or neither is, where A, B, C, D, E,
      F, G, H, K, L, M, N, P, and Q are decimal digits.

   c. (2 points) Compute the check digit for the ISBN number 4-169-97329-?
      (where ? denotes the check digit).

   d. (2 points) Let A-BCD-EFGHI-J be a valid ISBN number.  Show that
      A-BCD-FEGHI-J is NOT a valid ISBN number unless the transposed digits
      E and F are equal.  Hint:  Express the difference in check sums as a
      function of E and F.


2. (6 points) Give a Hamming code

      B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15

   that uses 4 even parity bits (in positions B1, B2, B4, and B8) to protect
   the 11 data bits (in the remaining positions).  That is, specify which bit
   positions (i.e., which Bi's) each parity bit Pj "protects".  Compute the
   parity bits P1, P2, P3, and P4 in the following codes:

      P1 P2 1  P3 0  1  0  P4 1  0  1  0  1  0  1
      P1 P2 0  P3 1  0  1  P4 0  1  0  1  0  1  0

   Are the codes

      0  1  1  1  1  0  1  1  1  0  1  1  0  1  0
      0  1  0  1  1  0  1  1  1  0  1  1  1  1  0

   valid?  If not, which bit(s) are incorrect (assuming that there were at
   most single-bit errors)?


3. (1 point) How many hours did it take you complete the first two problems?


Reading:  Kernighan, Chapters 5 (programming and programming languages)
  [Section 5.4 (intellectual property) is optional] and 7 (learning to
  program); (optional) Harris, Chapters 1 (variables, input, and output)
  and 2 (conditional code).
							       CPSC-101-02/14/18