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 224-226.
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₀, 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₀, 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 left-hand 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 n-bit 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 225-226. The three options you are to compare can be restated as follows:
1. Sixteen one-bit adders hooked together in ripple-carry fashion.
2. Four four-bit adders hooked together in ripple-carry fashion. Inside each of the four-bit adders, however, the carry lookahead is used.
3. Four four-bit adders hooked together in carry lookahead fashion. As in the previous option, carry lookahead is used within each of the four-bit adders as well.
Do exercise 4.35 from page 308. The four options to compare can be restated as follows:
1. Sixty-four one-bit adders hooked together in ripple-carry fashion.
2. Sixteen four-bit adders hooked together in ripple-carry fashion. Inside each of the four-bit adders, however, the carry lookahead is used.
3. Four sixteen-bit adders hooked together in ripple-carry fashion. Each of the sixteen-bit adders is built as in option 3 of the prior exercise.
4. Four sixteen-bit adders hooked together in carry lookahead fashion. As in the previous option, the sixteen-bit adders are built as in option 3 of the prior exercise.

Instructor: Max Hailperin