CSE370 Assignment 4

Distributed: 14 April 2000
Due: 21 April 2000

Reading:

  1. Katz, Chapter 3 (pp. 137-147).
  2. Katz, Chapter 4 (pp. 160-194, 202-205).

Exercises:

  1. Given a 4 variable K-map, and considering sum-of-products expressions:

    2. a) What is the maximum number of implicants? Give a minimized boolean expression for a function that achieves this maximum.
    b) What is the maximum number of prime implicants? Give a minimized boolean expression for a function that achieves this maximum.
    c) What is the maximum number of essential prime implicants? Give a minimized boolean expression for a function that achieves this maximum.
    d) What is the minimum number of essential prime implicants? Give a minimized boolean expression for a function that achieves this minimum.
     
  2. Exactly as one can define a real variable by an equation which needs to be solved for the given variable (for example 2x2 + x - 2 = 0), one can also define a boolean function by giving an equation which needs to be solved for the unknown boolean function. For example, if S and T are given boolean expressions, one might define the boolean function f by requiring that S * f = T. Note that, exactly as in the real number case, there might be more than one distinct boolean function f that solves the equation (two solutions are said to be distinct if one cannot be derived from the other using Boolean algebra)

    Let S = (A' + C + D)(A + B + C' + D')(A' + B' + C' + D') and T = A'C' + BC'D. Give an expression for one possible boolean function f that satisfies the equation S * f = T. How many distinct solutions for f are there in this case? Explain.

    3.  
  3. You have just been hired by RFC Inc. (Really Fast Chips) as an engineer in a top secret group: the one responsible for the next generation of RFC processors, the Zentium VII ™. One of your tasks is to design a 4-bit unsigned number comparator, called UComp. This block is an essential part of the new processor since it is used in one the most critical components, RFC’s new Allervassen branch prediction algorithm. So, it is important that you get this design really well done.


    4. The block you need to design looks like this:



    It will take two 4-bit unsigned numbers, and compare them. There are 8 inputs, which are the bits of the two numbers to compare: A3..0 is one number and B3..0 is another (A0 is the lsb, A3 is the msb). There are three outputs: G is asserted iff A > B, E is asserted iff A=B and L is asserted iff A < B (there is never more than one output asserted at once)

    You start writing the truth table for this, but you quickly realize that there are 8 variables, so that’s 256 rows in the truth tables. And on top of that, those K-maps that were advocated so much in CSE370 back when you were in school don’t make it easy to work on 8 variables!!!  So, you decide to start with a smaller more manageable problem, say that of comparing two 2-bit numbers.

    a) Design the following 2-bit UComp component, which has the exact same specification as above, except that A and B are only 2-bit numbers (design here means do a truth table, use K-maps to minimize, and draw the resulting circuit)


    b) Show how you would construct the 4-bit UComp block using two 2-bit UComp blocks, and a third block with 6 inputs and 3 outputs (you do not need to design the 6 input block, just say what it does)

    All you need to do now is design the block with 6 inputs! This is doable with K-maps, you say… But real designers like you don’t waste their time doing 6 variable K-maps! They find better solutions. Thus:

    c) Design a new 2-bit UComp block which has only 2 outputs (hint: let your outputs be Y1 and Y0, and have Y0Y1 = 00 mean smaller, Y0Y1 = 01 mean equal and Y0Y1 = 10 mean greater).

    d) Do b) again, but this time use two 2-bit UComp blocks and a third block with 4 inputs, and 3 outputs. Design this third block using truth tables and K-maps.

    Great! Now, you’ve done the design for this new comparator. Your boss really likes the design, but isn’t impressed enough to give you a bonus. So you keep on thinking about the problem, in the hope of finding something better (something, shall we say, bonus-enducing?). Finally, you come up with this incredible idea: the Bit Slice UComp, or BSUComp for short (show below).


    The BSUComp compares two n-bit numbers, of which the least significant bits are A0 and B0. What, you say? How can we compare two n-bit numbers according to only the lsb? Well, notice that there are two additional inputs. These two inputs (encoded according to part d) will give you the result of comparing all the bits in A and B that are more significant than the lsb.

    e) Design the BSUComp block (using, you’ve guessed it, truth tables and K-maps. Hope you’re seeing a pattern here about what the design process is…)

    f) Show how you would construct a 4-bit UComp block using four BSUComp blocks and a block with 2 inputs and 3 outputs. Design this 2 input, 3 output block (using what?… you’ve guessed it, truth tables and K-maps, of course)

    g) What is the gate count and the propagation delay of the 4-bit UComp blocks that you have designed so far (the one in part d and in part f)

    h) Given the results from part g, you decide not to show the Bit Slice design to your boss. One of your colleagues though, comes up with the same exact idea (BSUComp, etc.), and decides to pompously present it at the group meeting. The next day, this colleague of yours is fired! BUT, as luck would have it, the day after getting fired, your colleague gets a job at SFEC inc. (Slow but Flexible and Extensible Chips). What happened? (Hint: What happens when the Zentium ™ branch prediction engine makes the fantastic leap to 6 bits? What about 8 bits?)

Rationale:

Comments to: cse370-webmaster@cs.washington.edu (Last Update: )