Assignment 8, due Oct 24

Remember to write your name on what you turn in! Homework must be turned in on paper and in class!

Homework

1. Background: Consider the problem of designing a logic circuit to compare two two-bit words. This circuit has 4 inputs, 2 groups of 2, call them a₀, a₁, b₀, and b₁, and 1 output c. The output is true when the 2-bit value a equals the 2-bit value b.

   a) Draw out the truth table for this logic circuit. (0.2 points)

   b) Design a circuit that performs this comparison using two exclusive-or gates to perform the comparison and just one more gate to combine their outputs. (0.2 points)

   c) Evaluate the speed of the above circuit, in terms of the number of gates a change in the input must pass through to make a change in the output. The longest path from input to output determines the answer, and in speed evaluations, it is safe to assume that the exclusive or gates are made of and, or, nand, nor, and not gates. (0.2 points)

   d) Present a design for a circuit that implements the desired function with only 3 levels of delay. Do this by examining the circuit you constructed in order to answer part c above and optimize it by performing some algebraic simplifications that result in a 3-level circuit. (0.2 points)

   e) Suppose you used the brute force approach to converting the truth table into a 3-level circuit, with an and array and an or array. How many inverters, and gates and or gates does this circuit require. The answer can be determined by examination of the truth table. (0.2 points)

2. A question: Give the truth table for one bit position of a subtractor, where each bit position has a subtrahend input, a minuend input and a borrow input, and each bit postion has a difference output and a borrow output. The borrow output from each stage goes to the borrow input of the next most significant stage. Borrow equals true implies that this stage needs to borrow one from the next more significant stage. (1.0 points)

3. A problem: Look at the multiplication algorithms given at the start of Chapter 9. What is the minimum set of operations that the arithmetic logic unit must support in order to allow these algorithms to be implemented? The very first SMAL Hawk example multiply algorithm may be the most useful starting place for thinking about this. (0.5 points)

4. A problem: Write the fastest possible Hawk code to multiply by 53. (0.5 points)