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.