Assignment 7, due Jul 5

Solutions

Part of the homework for CS:2630, Summer 2018
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (Tuesday or Thursday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

  1. Background: Toward the middle of Chapter 8, a general methodology for converting any truth table to a logic circuit is given. That methodology was used in class on July 3 to derive an implementation of the exclusive-or function using only and, or and not gates.

    a) Give the truth table for a two-input compare function that has a true output only when both inputs are equal. (0.5 points)

      a     b    a = b 
    0 0 1
    0 1 0
    1 0 0
    1 1 1

    b) Use the given methodology to derive the logic for a two-input compare function. Do not delete any unneeded gates. Present your result as a neatly drawn logic diagram. Do not use any shorthand notations. (0.5 points)

    schematic diagram

    Of course, there's no need to single out the and and and arrays as is done faintly in the above, and even the truth table values filled into the intersections and the row labels in the and gates are unneeded.

    If someone does delete rows 1 and 2 in their answer to part b), it wouldn't count as an error, although it does obscure the connection to the truth table from which the circuit was derived. In that case, part c) of this problem wouldn't involve deleting any gates, it would just involve redrawing for neatness.

    c) Redraw your solution from part b) without unneeded gates, aiming for maximum legibility. Again, present your result as a neatly drawn logic diagram. (0.5 points)

    schematic diagram

    Straightening out the diagram so the logic flows strictly from left to right or from top to bottom is optional, and the row labels could have been deleted from the and gates.

    d) Give a boolean expression in terms of the and, or and not operators that is exactly equivalent to the logic diagram you gave as your answer to part b. (0.5 points)

    a b + a b

  2. Background: In their conventional order, here are all of the 3-bit unsigned binary numbers
    000 001 010 011 100 101 110 111

    Here are the same numbers in their Gray code order:

    000 001 011 010 110 111 101 100

    a) Give the truth table for a binary-to-Gray-code converter. This will have 3 inputs and 3 outputs, so if the input is, for example, 010, the output will be 011, and if the input is 101, the output will be 111. (0.5 points)

    binary Gray
      b2    b1    b0    g2    g1    g0 
    0 0 0 0 0 0
    0 0 1 0 0 1
    0 1 0 0 1 1
    0 1 1 0 1 0
    1 0 0 1 1 0
    1 0 1 1 1 1
    1 1 0 1 0 1
    1 1 1 1 0 0

    The specific labels on the inputs and outputs are, of course, not determined by the problem statement, but some kind of labels are needed to connect this to the corresponding logic diagram.

    b) Use the methodology from Chapter 8 to convert that truth table to a logic diagram. Legibility counts! Again, do not abbreviate and do not delete any unneeded gates. (0.5 points)

    schematic diagram

    You could, of course, add the truth table entries to the intersections.

    It would not be wrong to omit row zero, although this obscures the connection to the underlying truth table.

    If you simply connect output g2 to input b2, deleting the or gate that drives that output and deleting row 7, the circuit would compute the same output, but this deletion is based on an ad-hoc observation about the relationship of g2 and b2, and it ignores the methodology we are demonstrating, so it should be subject to a small penalty.