CSE 370, Spring 2000

Homework 4 Solutions

NOTE: Leaving a question worth 0 points blank resulted in a 1 point deduction from your homework score.

1. Implicants (4 points)

• a) (1 point)  What is the maximum number of implicants? Give a minimized Boolean expression for a function that achieves this maximum.

  Since an implicant is any circle we can draw in a K-map, this question is almost trivial because the function F (A, B, C, D) = 1 will give us the most number of implicants (I can count 81 distinct implicants in this function... can you find more?  Can you prove there are no more?)

• b) (1 point)  What is the maximum number of prime implicants? Give a minimized Boolean expression for a function that achieves this maximum.

• c) (1 point)  What is the maximum number of essential prime implicants? Give a minimized Boolean expression for a function that achieves this maximum.

• d) (1 point)  What is the minimum number of essential prime implicants? Give a minimized Boolean expression for a function that achieves this minimum.

2. Boolean Equations (4 points)

Exactly as one can define a real variable by an equation which needs to be solved for the given variable (for example 2x 2 + 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. Also give the truth table for this Boolean function, with the variables from left to right being A, B, C, D. How many distinct solutions for f are there in this case? Explain.

• We are given the function S, and the result of (S AND f) is T.  Let's look at the truth tables for these functions, and make their K-maps:

• By looking at these K-maps, we can now write out the K-map for f.  Because S and f are "ANDed" together, we know that whenever T is 1, we'll want (S AND f) to equal to 1.  Similarly, when T is 0 we'll want to make f such that (S AND f) evaluates to 0.  Furthermore, because S is 1 in all the K-map slots where T is 1, we will only have to design f to eliminate the 1's in S that we don't want.  (Notice that a solution for f would be impossible if S were 0 at any location where T is 1.)  It is interesting to note that f = T is a solution to this problem!
• Let's design the K-map for f (the truth table is easily derived from this):

• To solve for f, all we need to do now is draw circles on f's K-map, and write out the corresponding boolean equation:

• Hopefully it is clear that there are several functions that will give the same result.  As for just how many distinct functions f exist such that (S AND f) = T, we need to figure out how to make distinct solutions.  Assuming that distinct solutions require different K-maps, we can look at the K-map for f above, and see that there are 4 don't care cases that effect the final function depending on whether we circle them or not (i.e. whether we take that "don't care" to mean a "1" or "0").  So, since we have an option to either include or ignore 4 elements in the K-map, this means that we have 2⁴ possible K-maps and therefore 16 different solutions to this problem.

3. Comparator (design problem, 12 points)

• a) (0 points)  The 2-bit comparator is described by the following truth table, K-maps, and circuit:

A1 A0 B1 B0 G E L 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 0	G = A1B1' + A0B1'B0' + A1A0B0' E = A1'A0'B1'B0' + A1'A0B1'B0 + A1A0B1B0 + A1A0'B1B0' L =A1'B1 + A0'B1B0 + A1'A0'B0
G A1'A0' A1'A0 A1A0 A1A0' B1'B0' 0 1 1 1 B1'B0 0 0 1 1 B1B0 0 0 0 0 B1B0' 0 0 1 0	E A1'A0' A1'A0 A1A0 A1A0' B1'B0' 1 0 0 0 B1'B0 0 1 0 0 B1B0 0 0 1 0 B1B0' 0 0 0 1	L A1'A0' A1'A0 A1A0 A1A0' B1'B0' 0 0 0 0 B1'B0 1 0 0 0 B1B0 1 1 0 1 B1B0' 1 1 0 0

• b) (2 points)  Here is a diagram of the 4-bit comparator:

The 4 bit numbers are both split into high order and low order bit pairs, and then each of these pairs is compared separately.  The outputs from both blocks are then routed directly to the 6 inputs of the new block in the diagram.  This new block should behave as described by the following C++ style code segment:

if ( G1 || ( E1 && G0 ) )  { G = 1;  E = 0;  L = 0; }
if ( E1 && E0 )            { G = 0;  E = 1;  L = 0; }
if ( L1 || ( E1 && L0 ) )  { G = 0;  E = 0;  L = 1; }

To put it in English, if G1 is high OR E1 AND G0 are high, then G should be 1; if E1 AND E0 are both high, then E should be 1; if L1 is high OR E1 AND L0 are high, then L should be 1.  We can actually map this directly to gates now:

• c) (2 points)  Here are the truth table, K-maps, and circuit diagram for the new 2-bit block:

A1 A0 B1 B0 Y0 Y1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1	Y0 = A1B1' + A0B1'B0' + A1A0B0' Y1 = A1'A0'B1'B0' + A1'A0B1'B0 + A1A0B1B0 + A1A0'B1B0'
Y0 A1'A0' A1'A0 A1A0 A1A0' B1'B0' 0 1 1 1 B1'B0 0 0 1 1 B1B0 0 0 0 0 B1B0' 0 0 1 0	Y1 A1'A0' A1'A0 A1A0 A1A0' B1'B0' 1 0 0 0 B1'B0 0 1 0 0 B1B0 0 0 1 0 B1B0' 0 0 0 1	Notice that Y0 and Y1 are analogous to G and E in the previous section of this problem.

• d) (2 points)  Here is the revised diagram for the 4-bit comparator:

Now that we've decreased the number of inputs to the new block to 4, we can easily do a truth table, K-maps, and derive a circuit for the block.  This is shown below:

H0 H1 L0 L1 G E L 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 X X X 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 X X X 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 X X X 1 1 0 0 X X X 1 1 0 1 X X X 1 1 1 0 X X X 1 1 1 1 X X X	G = H0 + H1L0 E = H1L1 L = H0'H1' + H0'L0'L1'
G H0'H1' H0'H1 H0H1 H0H1' L0'L1' 0 0 X 1 L0'L1 0 0 X 1 L0L1 X X X X L0L1' 0 1 X 1	E H0'H1' H0'H1 H0H1 H0H1' L0'L1' 0 0 X 0 L0'L1 0 1 X 0 L0L1 X X X X L0L1' 0 0 X 0	L H0'H1' H0'H1 H0H1 H0H1' L0'L1' 1 1 X 0 L0'L1 1 0 X 0 L0L1 X X X X L0L1' 1 0 X 0

• e) (2 points)  Here are the truth table, K-maps, and circuit diagram for the new BSU comparator:

A0 B0 I0 I1 Y0 Y1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 X X 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 1 X X 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 X X 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 X X
Y0 A0'B0' A0'B0 A0B0 A0B0' I0'I1' 0 0 0 0 I0'I1 0 0 0 1 I0I1 X X X X I0I1' 1 1 1 1	Y1 A0'B0' A0'B0 A0B0 A0B0' I0'I1' 0 0 0 0 I0'I1 1 0 1 0 I0I1 X X X X I0I1' 0 0 0 0	Y0 = I0 + A0B0'I1 Y1 = A0'B0'I1 + A0B0I1

• f) (2 points)  Here is the revised diagram for the 4-bit comparator made from 4 BSU comparators and a new final stage block:

Here are the truth table, K-maps, and circuit diagram for the final block:

I0 I1 G E L 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 X X X
G I0' I0 I1' 0 1 I1 0 X	E I0' I0 I1' 0 0 I1 1 X	L I0' I0 I1' 1 0 I1 0 X	G = I0I1' E = I0'I1 L = I0'I1'

• g) (0 points)  Gate count and propagation delay of 4-bit comparators:

* Propagation delays are calculated by assuming the delay through one gate is D, and then finding the worst case delay (i.e. longest path from input to output) for each circuit.

• h) (2 points)  The problem with the BSU comparator is that, while it is easily expanded to serve as many bits as needed, the propagation delay is linearly dependant on the number of bits being compared.  Because we have to have a block for every bit being compared, and then the results have to "trickle" through the structure before we get an answer, this block will take far too long when comparing a large number of bits.  

Created by: Valdis Riekstins

last updated: 4/25/00