Homework 6

22C:122, Fall 1999

Due Monday Oct 4, 1999, in class

Douglas W. Jones

  1. Background: Consider the general purpose ALU design developed in the notes on addition for Sept 27. This design has an XOR gate in it, and the natural implementation of XOR requires 4 nand gates and has 3 gate delays. This extra delay is added in series with the adder for the B input, and this could be unacceptable in a high performance system.

    The Problem: Suggest a design for an XOR/EQU gate using only and gates, nand gates and inverters that develops both XOR and EQU outputs in 3 or fewer gate delays. This can be substituted into the ALU design to reduce the number of delays on the B input.

  2. Background: Consider the problem of iteratively computing the reciprocal of a number. We know that 1/V * V = 1, and our initial approximation of 1/V is zero. If we develop the approximation for the reciprocal one bit at a time, we can, at the same time, compute the next successive partial product and add it to the sum representing the product 1/V * V. Therefore, if V is an N bit number, we can compute an N-bit approximation of the reciprocal with N addition operations.

    Part A: Modify the Russian Peasant algorithm to compute the 2*N-bit product of two N-bit numbers by summing the N partial-products starting with the most significant one instead of the least significant.

    Note useful in moving to part B: If you view the multiplier as being a fixed-point fraction with N places right of the point and the multiplicand as an integer (N places left of the point), you can view the product as having N places left of the point and N places right of the point.

    Part B: Using your answer to part A as a starting point, develop an algorithm to compute the N-bit fixed-point fraction that approximates the reciprocal of a given N-bit number V. In the case where V = 1, your algorithm should generate a reciprocal of .1111...

  3. Background: Consider the problem of division by 3. Using the methodology of http://homepage.cs.uiowa.edu/~dwjones/bcd/divide.html, find a good fixed point approximation of 1/3 for use in obtaining a 16 bit result. Does your multiplier give an exact quotient for all possible 16 bit dividends, or is it off by one for some, requiring a fixup step as used in the examples.