MC48 Homework 3 (Fall 1996)
Due: October 3, 1996
Note that I plan to do at least exercise 4.33, and probably also
exercise 4.31 and/or part or all of 4.34 in class. Their inclusion in
the homework assignment just means that you need to clearly write up
what we've done in a more casual oral style in class.

Do exercise 4.9 on page 304.

Do exercise 4.31 on page 308; the reference to page 202 should be to
pages 224226.

Do exercise 4.32 on page 308.

Do exercise 4.33 on page 308. Where the problem statement refers to
page 200, that should be page 223. In this and the following two
exercises, remember that as many equations as necessary can be
calculated simultaneously, so long as their inputs are all
available. For example, initially all the a_{i}
and b_{i} inputs are available at time 0, and so is
c_{0}, so during the first time unit (T), all of the p_{i} and g_{i}
can simultaneously be calculated, so that at time T, they are now
all available, and all the equations using them can simultaneously be
calculated. Here, in concise form, are the ground rules:

At time 0, all a_{i} and b_{i} inputs are
available. So is c_{0}, the carry in to the overall adder.

If
at any particular time, t, the last of the values used on the right
hand side of an equation becomes available, then the value of the
lefthand side will become available at time t+T if the equation
contains only AND or only OR, and at time t+2T if the equation
contains both AND and OR. It is irrelevant what else is going on
concurrently.

Whichever output bit becomes available last, whether it is one of the
sum bits or the carry out bit
(c_{n} in an nbit adder), signals the
end of the computation: when that last output is available, the
computation is over. The completion time is the total
elapsed time, since we started at time 0.

Do exercise 4.34 from page 263. The reference to page 202 should be
to pages 225226. The three options you are to compare
can be restated as follows:

Sixteen onebit adders hooked together in ripplecarry fashion.

Four fourbit adders hooked together in ripplecarry fashion. Inside
each of the fourbit adders, however, the carry lookahead is used.

Four fourbit adders hooked together in carry lookahead fashion. As in
the previous option, carry lookahead is used within each of the
fourbit adders as well.

Do exercise 4.35 from page 308. The four options to compare can be
restated as follows:

Sixtyfour onebit adders hooked together in ripplecarry fashion.

Sixteen fourbit adders hooked together in ripplecarry fashion. Inside
each of the fourbit adders, however, the carry lookahead is used.

Four sixteenbit adders hooked together in ripplecarry fashion. Each
of the sixteenbit adders is built as in
option 3 of the prior exercise.

Four sixteenbit adders hooked together in carry lookahead fashion. As in
the previous option, the sixteenbit adders are built as in
option 3 of the prior exercise.
Instructor: Max Hailperin