Assignment 2, due Jan 31

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

1. Take the truth table given for a full adder in the notes for lecture 4 (in the section on Arithmetic, subsection on adders), and apply the methodology for the systematic implementation of combinational functions from the notes for lecture 2.

   a) Draw out the finished circuit, with no optimization, without abbreviation and without optimization.

   b) Redraw the circuit, ommiting any gates with unused outputs and combining any rows that can be combined under the rules for optimization of combinational circuits for lecture 2. Draw the result using the abbreviated notation used in that section of the notes.

2. A vending machine control unit can be modeled by a finite state machine. The machine undergoes a state transition whenver a customer inserts a coin or presses a product selection button. Only one coin may be inserted at a time. Our example machine accepts nickels, dimes and quarters, and has a single product. The product has a cost of 35 cents. The control unit has outputs that cause the return of one nickel, one dime and one quarter, that cause the dispensing of a product, for a total of 4 independent outputs.

   a) Give the state diagram for a Moore machine that implements this control unit.

   b) Give a state table specification of this machine.

   c) How many bits are there in the state register of this machine? How many nand gates and not gates (add them up) will be required, in the worst case, for a brute force reduction of the state table to digital logic. (optimization can improve this, so it's a worst-case bound.)

3. Lecture 4 gives details for several combinational elements, but it fails to cover others. Here, we'll assume that x and y are inputs to combinational elements, and that f is the output. Give the details for the implementation of the following combinational elements (these are specified using C notation, and your answer should use the notation of the notes for section 4):

   a) f = (x << 1)

   b) f = (x == 1)

   c) f = (x == y)

4. A more interesting omission from the notes in lecture 4 is comparison. Consider two binary numbers a and b. A comparator has a 2-bit output, one bit indicating if a = b, and another bit indicating if a > b. Combinations of these give all the classic comparisons, < < = > > and inequality. To compute these, we'll use a tree:

   a) Give the truth table for a 1-bit comparitor (the a and b inputs are 1-bit binary numbers). We'll use these as the leaves of our binary tree of logic circuitry that compares n-bit numbers.

   b) Give the truth table for an internal node in the tree. It takes, as inputs, reports on the comparison of the most significant halves of the numbers being compared, and reports on the comparison of the least significant halves. The output reports on the full number represented by the combination of those two halves.