CPSC 330 - Spring 2006
Study Guide for Exam 2
Coverage: combinational and sequential logic
1. Be able to define or match these terms.
combinational logic
sequential logic
minterm (product term)
sum of products form
DeMorgan's theorems
Karnaugh maps
asserted signal
don't care
gate
glitch
race hazard (race condition)
number of gate levels (circuit depth)
fan-in
fan-out
propagation delay
programmable logic array (PLA)
decoder
multiplexer (mux)
half-adder
full-adder
ripple-carry adder
ALU
latch
flip-flop
master-slave
edge-triggered
RS latch
JK flip-flop
D flip-flop
T flip-flop
Mealy machine (output is a function of both the state and the input)
Moore machine (output is a function of the state)
register
shift register
binary counter
ring counter
clock
2. Be able to:
A. Construct a truth table for a given logical function. This could
be for a simple gate (and, or, not, nand, nor, ...) or for a given
combinational circuit or logic expression.
B. Prove that one logic expression is idential to another by use of
a truth table or by algebraic transformations.
C. Simplify a four-variable (or less) logic function or truth
table using a Karnaugh map.
D. Construct a truth table for a given latch or flip-flop
(from among RS, JK, D, T).
E. Given one of the following:
- textual description
- state transtion and output table
- circuit diagram
- state diagram
derive the others.
3. Thought questions:
A. Why are clocks used in many sequential logic designs?
B. Consider a computer as a sequential logic circuit. What is
the state memory?
Be prepared to work problems as given in homework 2.
Example questions
_
1. Give a truth table to prove that A = AB + AB. That is, A by itself is
equal to the expression (A AND B) OR (A AND not-B). [Show three
intermediate value columns for not-B, (A AND B) and (A AND not-B).]
2. Consider the following circuit diagram
[figure given]
(a) Give the logic expression in sum of products form for F.
(b) Give the logic expression in sum of products form for G and the
truth table for G.
3. Give the truth table (characteristic table) for the JK flip-flop.
4. Can you easily make a JK flip-flop into a D flip-flop? If so, show a
circuit diagram in which the the JK flip-flop is represented as a single
component (that is, as a box with J, K, and CLK inputs and Q and not-Q
outputs).
5. Draw a block diagram of the generic model of a sequential circuit (that
is, a finite state machine). Be sure to identify the following component
parts or signals: combinational circuit, memory element, input, output,
current state, and next state.
6. A sequential circuit has one D flip-flop "D", two inputs X and Y, one
output Z, and is specified by the following logic equations:
_ _
Z = D xor X = DX + DX Note: D == Q(t)
_ _ of the
D (input to D flip-flop) = D xor Y = DY + DY flip-flop
(a) Give the circuit implementation.
(b) Give the truth table.
(c) Give the state diagram.
7. Consider a four-state ring counter. The circuit is initialized to
outputs (o0,o1,o2,o3) of 1000 whenever the single input (R) is 1.
Otherwise, the outputs advance on each clock cycle from 1000 to 0100
to 0010 to 0001 and then back to 1000, in that order.
(a) Give the state diagram.
(b) Give the truth table.
(c) Give a circuit implementation.
8. A bit-serial adder has one D flip-flop, two inputs X and Y, and one
output S. The combinational logic consists of a full adder with the
carry out being used as the next state. (Ignore the initial clear/set
of the carry.)
+---------+
X ----->| | sum
| full |-----------------------> S
Y ----->| |
| adder | carry = D_in +---+ Q
.---->| |------------->| |---.
| +---------+ | D | |
| CLK->| | |
| +---+ |
`--------------------------------------'
(a) Give the state transition table with inputs X, Y, and Q(t), and
outputs S and Q(t+1).
(b) Give the state diagram as a Mealy machine.
9. Consider extending the serial adder circuit to a two-bit-serial binary
adder (that is, a circuit in which X, Y, and S will each be two-bit
signals).
2 +---------+
X --/-->| | sum 2
2 | |---------------------/-> S
Y --/-->| adder |
| | carry +---+
.---->| |------------->| |---.
| +---------+ | | |
| +---+ |
`--------------------------------------'
(a) How many flip-flops will be needed? Explain your answer.
(b) How many rows would there be in the state transition table?
Explain your answer.
10. Consider a two-bit saturating up-down counter.
(a) Draw the state transition diagram. Label the up transitions
with '1' and the down transitions with '0'.
(b) Give the state transition table.
(c) Give a circuit implementation for this counter.