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 = {a1,
a2, a3, a4, a5,
a6, a7, a8, a9},
with Pr(ak) = (k/45). Calculate the deterministic
entropy Ho(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 Z1 and Z2
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|Z1Z2)
= 0
b) Evaluate H(Z|Z1)
and H(Z1|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.