CS599: Alternative Computing Paradigms
Instructor: C. Diorio

Homework Set 3
DUE: April 19,1999, 6:30 pm

Collaboration Policy:
Unless noted otherwise, you may collaborate with other CSE599 students on the homework. You must spend at least 15 minutes working on a problem before seeking assistance. Collaboration means that you may discuss the problems and make notes during the discussion, but you may not look at other student’s work when writing up your homework. Your homework represents your own work—the homework must show that you understand the material and have worked as an individual on every problem. You may not divide up the task of doing the problem sets in the interpretation of collaboration.

Late Homework Policy:
The weekly assignments are due at the beginning of class. Assignments handed in after class will incur a 10% penalty; the penalty will increase by 10% for each additional day late.

Reading:
Feynman pgs. 137–184

Please show all of your work, and remember, your solutions must be legible. The points for each problem are noted on the problem statement.

1. (5 pts) You are given a 2-input AND gate, with inputs a and b. The input ensembles are independent and binary valued, with {P(a) = 1} = {P(a) = 0} = 1/2, and {P(b) = 1} = {P(b) = 0} = 1/2. Calculate the entropy of the gate’s input and output. How much information does the gate destroy? Repeat the analysis for a two-input OR gate and for a two-input XOR gate.
 

2. (10 pts) You are given an ensemble X = {a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈, a₉}, with Pr(a_k) = (k/45). Calculate the deterministic entropy H_o(X) and the entropy H(X) of the ensemble. Create a Huffman code for the ensemble, and evaluate the expected code length. How close did you get to the entropy H?
 

3. (15 pts) In a game of backgammon, we roll two fair dice and play according to the points we get. Let Z₁ and Z₂ be the two (independent) ensembles corresponding to the points on the dice, and let Z be the ensemble corresponding to the sum of these points.
    a) Show that H(Z|Z₁Z₂) = 0
    b) Evaluate H(Z|Z₁) and H(Z₁|Z)
    c) Suppose that it is our turn to roll the dice. We win if, and only if, we get exactly 8 points. Evaluate our uncertainty about winning (your answer should be in bits).
 

4. (10 pts) Construct a simple error-correcting code that can correct a single bit error in a codeword of length N = 7 (this is the total length of the code, including syndrome and data bits). Use binary symbols.
    a) What is the maximum number M of codewords in the code?
    b) With this M, what is the rate of the code (bits/symbol)?
    c) Construct the code.
 

5. (10 pts) Problem 4.3 on pg. 115 of Feynman.