60-265: Fall 2010 Computer Architecture I: Digital Design

Exercise 3 – Circuit Expressions & Karnaugh Maps

Question 1. [ 2 marks ]

Simplify each of the following expressions in both SOP form and POS form.

a.X’Z’ + Y’Z’ + YZ’ + XY

F(X,Y,Z) = X’Z’ + Y’Z’ + YZ’ + XY

= X’Z’ + (Y’ + Y)Z’ + XY

= X’Z’ + Z’ + XY

= (X’ + 1)Z’ + XY

= Z’ + XYSOP form

= (Z’ + X)(Z’ + Y)POS form

b.AC’ + B’D + A’CD + ABCD

G(A,B,C,D)= AC’ + B’D + A’CD + ABCD

= AC’ + B’D + (A’ + AB)CD

= AC’ + B’D + (A’ + B)CD

= AC’ + A’CD + B’D + BCD

= AC’ + A’CD + (B’ + BC)D

= AC’ + A’CD + (B’ + C)D

= AC’ + B’D + A’CD + CD

= AC’ + B’D + CDSOP form

= AC’ + (B’ + C)D

= (AC’ + B’ + C)(AC’ + D)

= (AC’+ C + B’)(AC’ + D)

= ((A + C)(C’+ C) + B’)(AC’ + D)

= (A + B’ + C)(A + D)(C’ + D)POS form

NOTE: In both (a) and (b) above, we started with a form that was already SOP in nature, then simplified and finally transformed to POS form. If the original expression was in POS form, we would have reversed the strategy.

Question 2. [ 1 mark ]

Draw the circuit diagram for the following Boolean expression, assuming x, y and z are the labels attached to the input wires to the circuit. Use the proper gate diagrams for each logic operation indicated. To avoid confusion, the operators xor and xnor are stated explicitly.

x’z’ + y xor z’ + yz’ + x xnor y

ANSWER:

Question 3. SOP Karnaugh Maps [ 4 marks ]

Karnaugh maps are often used to obtain simplified Sum of Product (SOP) expressions. Process each of the SOP expressions below, using Karnaugh maps. Each expression uses canonical minterm notation that may be used to fill in the K-map.

F(X,Y,Z) = SUM m(1,2,4,5,6)

ANSWER:

F(X,Y,Z) / YZ
00 / 01 / 11 / 10
X / 0 / 1 / 1
1 / 1 / 1 / 1

The blue and yellow boxes both are combined with the greenish box labelled XYZ=101 to form two 2-cubes, while the pinkish boxes form a third 2-cube.

F(X,Y,Z) = XY’ + Y’Z + YZ’ (also equivalent to: XY’ + Y xor Z)

Note that each term above is a prime implicant. All of the following are essential prime implicants: XY’Z’, X’Y’Z, XYZ’, X’YZ’.

G(A,B,C,D) = SUM m(1,2,5,6,7,9,11,12,13)

ANSWER:

G(A,B,C,D)) / CD
00 / 01 / 11 / 10
AB / 00 / 1 / 1
01 / / 1 / 1 / 1
11 / 1 / 1
10 / 1 / 1

G(A,B,C,D) = C’D + ABC’ + A’BD + AB’D + A’CD’

Note that this is not a unique answer. For instance, the purplish box can be pushed to the right, hence replacing the term A’BD with A’BC.

The essential prime implicants are: A’B’C’D, ABC’D’, A’BCD, AB’CD, A’B’CD’, A’BCD’.

Question 4. Karnaugh Maps [ 3 marks ]

Simplify the following Boolean function in bothsum-of-products (SOP) form and product-of-sums (POS) form by means of a four-variable K-map. Draw the logic diagram with (a) AND and OR gates in two two-level circuits, one for SOP and the other for POS, and (b) NAND gates only (you choose whichever form you wish to work with, SOP or POS)!

F(A,B,C,D) = SUM m(0,2,5,7,8,10,13,15)

ANSWER:

For SOP form, the K-map is:

F(A,B,C,D) / CD
00 / 01 / 11 / 10
AB / 00 / 1 / 0 / 0 / 1
01 / 0 / 1 / 1 / 0
11 / 0 / 1 / 1 / 0
10 / 1 / 0 / 0 / 1

F(A,B,C,D) = BD + B’D’ (which is also B xnor D)

The logic circuit is drawn as:

using Inverters (NOT gates), AND and OR. Note that the A and B inputs are not shown, but can be included as well – in both cases they are simply terminated lines, signifying that they are connected to an electrical sink.

The circuit diagram above can be converted directly into a circuit that uses only NAND gates. Start by inserting two circles on each line between the AND and OR gates above – this step is just performing double complementation (ie. x’’ = x). Move and attach one of the circles to each AND gate, immediately forming a NAND gate for each. Move and attach the two remaining circles to the left side of the OR gate. By deMorgan’s Theorem, the NOT-OR is equivalent to a NAND (ie. x’+y’ = (xy)’). The final step is to replace the two initial Inverters by NAND gates. We use the Idempotent Theorem, recognizing that x’ = (xx)’, so splitting the B and D inputs into two input lines and putting each pair through a NAND gate accomplishes the complementation of B and D respectively.

For POS form, the K-map is:

F(A,B,C,D) / CD
00 / 01 / 11 / 10
AB / 00 / 1 / 0 / 0 / 1
01 / 0 / 1 / 1 / 0
11 / 0 / 1 / 1 / 0
10 / 1 / 0 / 0 / 1

F(A,B,C,D) = (A + B + D’)(B’ + C + D)(A’ + B + D’)(B’ + C’ + D)

The logic circuit diagram is straightforward and left as an exercise for students. For each input A, B, C and D, split the incoming line and run one line through an Inverter gate to produce A’, B’, C’ and D’ respectively. Run the appropriate lines (ie. A or A’, etc) into four 3-input OR gates, and then run the outputs from these into a 4-input AND gate to complete the circuit. The last output is the value F.

Following similar diagrammatic manipulation as with the SOP case, it is straightforward to convert this circuit into one that uses NOR gates only. Similarly, NAND gates can also be used.