EGRE 254

Final Exam

Open book / open notes

5/4/09

Print your name neatly:

__SOLUTIONS_

  1. For the Karnaugh map shown below, circle all prime implicants.

/ / W / F(W,X,Y,Z)
/ 1 / / 1 / 1
1 / 1 / 1 / Z
Y / / 1
1 / 1 / 1
X
  1. For the Karnaugh map shown below, circle all essential prime implicants.

/ W / F(W,X,Y,Z)
1 / / 1 / 1
1 / 1 / 1 / Z
Y / 1
1 / 1 / 1
X
  1. For the Karnaugh map shown below, write F as a minimal sum of products.

/ W / F(W,X,Y,Z)
1 / / 1 / 1
1 / 1 / 1 / Z
Y / 1
1 / 1 / 1
X

ANS:

  1. For the Karnaugh map shown below, write F as a minimal sum of products, but include any terms necessary to eliminate all static-1 hazards.

/ W / F(W,X,Y,Z)
1 / / 1 / 1
1 / 1 / 1 / Z
Y / 1
1 / 1 / 1
X

ANS:

  1. For the circuit shown below, plot y on the Karnaugh map.

y(a, b)
1
1 / b
a

ANS:

  1. Plot the function on the Karnaugh map shown below.

X / F(X,Y,Z)
1 / 1
1 / 1 / Z
Y

ANS:

  1. Plot the function on the six variable Karnaugh map shown below. Enter only 1’s on the map. Leave blank those cells where F = 0. Note the small numbers in each cell are the minterm values for that cell.

V = 0 / V = 1
W / W
1 / 1 / 1 / 1 / 1 / 1 / U = 0
Z / 1 / 1 / Z
Y / 1 / 1 / 1 / 1 / Y / 1 / 1 / 1 / 1
1 / 1 / 1 / 1 / 1 / 1
X / X
W / W
1 / 1 / 1 / 1 / U = 1
Z / Z
Y / 1 / 1 / 1 / 1 / Y / 1 / 1 / 1 / 1
1 / 1 / 1 / 1
X / X


The truth tables to define the simple decoder and multiplexer used in the problems are shown below.

A / B / Y0 / Y1 / Y2 / Y3 / A / B / W
0 / 0 / 1 / 0 / 0 / 0 / 0 / 0 / D0
0 / 1 / 0 / 1 / 0 / 0 / 0 / 1 / D1
1 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / D2
1 / 1 / 0 / 0 / 0 / 1 / 1 / 1 / D3

Truth table for the decoder. Truth table for the multiplexer.

  1. Show how to connect the decoder and NOR gate to produce the output F=XÅY..
  1. Show how to use the multiplexer to implement a two input XOR gate. Do this by connecting either “0”, or “1”to the D inputs so that .


The truth tables to define the simple decoder and multiplexer used in this problem are shown below.

A / B / Y0 / Y1 / Y2 / Y3 / A / B / W
0 / 0 / 1 / 0 / 0 / 0 / 0 / 0 / D0
0 / 1 / 0 / 1 / 0 / 0 / 0 / 1 / D1
1 / 0 / 0 / 0 / 1 / 0 / 1 / 0 / D2
1 / 1 / 0 / 0 / 0 / 1 / 1 / 1 / D3

Truth table for the decoder. Truth table for the multiplexer.

  1. Plot the function F on the Karnaugh map.

The inputs to the multiplexer are given by:

Using these values gives

W / F
1 / 1 / 1 / 1
1 / 1 / Z
Y / 1
1 / 1
X
  1. Write the minimal sum of product form for the F of the five variable Karnaugh map shown below.

V = 0 / V = 1
W / W / F
1 / 1 / 1 / 1 / 1
1 / 1 / 1 / Z / 1 / 1 / 1 / Z
Y / 1 / Y / 1 / 1 / 1 / 1
1 / 1 / 1 / 1
X / X
  1. I decided to invent a new type of flip-flop, which I call the JT flip-flop. The dQ map for the JT flip-flop is shown below. Complete the schematic to show the simplest way to build a JT flip-flop using one D flip-flop, one XOR gate, one OR gate, and one AND gate.

J / dQ
0 / D / D / D /
Q / 1 / Ñ / Ñ / 1
T

Using the term, the circuit can be implemented without an inverter.


For the next problems refer to the dQ maps shown below. The dQ maps describe a counter, and CLK is the system clock. Assume JK flip-flops are clocked by the falling edge of the clock.

There are several equally correct answers for some of the J and K inputs. Some of these are shown below. Note: See next page.

Q1

/

dQ3

/ Q1 /

dQ2

/ /
Q1
/

dQ1

0 / d / d / 1 / D / d / d / D / D / d / d / D
d / D / 1 / Ñ /

Q3

/ d / Ñ / Ñ / 0 /

Q3

/ d / Ñ / 1 / Ñ /

Q3

Q2
/
Q2
/
Q2
  1. If C1 = CLK, write the equations for J1 and K1.
  1. If C2 = CLK, write the equations for J2 and K2.
  1. If C3 = CLK, write the equations for J3 and K3.
  1. Suppose C3 is connected to Q2 would the counter work if both J3 and K3 are connected to a logic “1”?

Yes No

Q2 can’t be used as clock since it does not provide a transition for the Ñ on the dQ3 map.

  1. Suppose C3 is connected to Q2 would the counter work if both J3 and K3 are connected to a logic “1”?

Yes No


The above maps should have been labeled as shown below. The actual equations should have Q3 and Q1 interchanged as shown below.

Q3

/

dQ3

/ Q3 /

dQ2

/ /
Q3
/

dQ1

0 / d / d / 1 / D / d / d / D / D / d / d / D
d / D / 1 / Ñ /

Q1

/ d / Ñ / Ñ / 0 /

Q1

/ d / Ñ / 1 / Ñ /

Q1

Q2
/
Q2
/
Q2

If C1 = CLK, write the equations for J1 and K1.

If C2 = CLK, write the equations for J2 and K2.

If C3 = CLK, write the equations for J3 and K3.

  1. The state diagram for a certain asynchronous finite state machine is shown below. The state assignment is shown for two states. Enter a valid state assignment for the other states. ANS: One possible solution is shown below. Any solution is correct provided only one state variable changes at a time. This is necessary to prevent a possible race condition.

8