CPSC 330 - Fall 2008 Homework 2 Due - Wednesday, September 24 [updated Sept. 17 to change due date and fix typo in #3] Each student must turn in a separate set of homework solutions, but you may work together in study groups with other students from the class. Include their names in parentheses under your name on the solution set you submit. Purposes: (1) work with combinational logic; (2) work with sequential logic. Example: Consider A*( (~A) + B ) = A*B. Show by truth table that this is true. A B | ~A | ~A + B | A*(~A+B) | A*B -----+----+--------+----------+----- 0 0 | 1 | 1 | 0 | 0 0 1 | 1 | 1 | 0 | 0 1 0 | 0 | 0 | 0 | 0 1 1 | 0 | 1 | 1 | 1 true because the table is an ^ ^ exhaustive enumeration and the \______/ last two columns are the same Show by algebraic manipulation that this is true. A*( (~A) + B ) = A*(~A) + A*B by distributive postulate = 0 + A*B by inverse postulate = A*B by identity postulate 1. (a) Show by truth table the 3-variable version of de Morgan's Law for and-ing: ~(A*B*C) = (~A) + (~B) + (~C) (b) Show by algebraic manipulation the 3-variable version of de Morgan's Law for or-ing: ~(A+B+C) = (~A)*(~B)*(~C) (You will use the 2-variable version in proving this.) Example: Determine the simplest logic expression for the values in this Kmap: \BC A\ 00 01 11 10 +----+----+----+----+ _ _ _ _ _ _ _ _ 0 | 1 | 1 | 0 | 0 | sum of products = A*B*C + A*B*C + A*B*C + A*B*C +----+----+----+----+ _ 1 | 1 | d | d | 1 | don't cares = A*B*C + A*B*C +----+----+----+----+ _ simplified expression = A + B (treat both don't cares as true) 2. Simplify the following Karnaugh maps of function F. (4 pts. each) \ BC A \ 00 01 11 10 +----+----+----+----+ 0 | 1 | 0 | 0 | 1 | F = fn(A,B,C) = _________________________ +----+----+----+----+ 1 | 0 | 0 | 1 | 1 | +----+----+----+----+ \ BC A \ 00 01 11 10 +----+----+----+----+ 0 | 1 | d | 0 | d | F = fn(A,B,C) = _________________________ +----+----+----+----+ 1 | d | 1 | 0 | 1 | +----+----+----+----+ Examples [see lecture notes and pdf handout] 3. Consider the clocked JK latch given in the following diagram: http://www.asic-world.com/images/digital/jk_latch.gif We will for the moment ignore the clock (or enable) signal E. Let the next state of this latch be called Q_next. Fill in the intermediate columns of the table and verify that the R and S inputs do indeed lead to Q_next values as shown. J K | Q Q' | R=K*Q S=J*Q' | Q_next ----+------+--------------+------- | | | 0 0 | 0 1 | | 0 \ | | | | retain previous value (same as Q) 0 0 | 1 0 | | 1 / | | | ----+------+--------------+------- | | | 0 1 | 0 1 | | 0 \ | | | | reset 0 1 | 1 0 | | 0 / | | | ----+------+--------------+------- | | | 1 0 | 0 1 | | 1 \ | | | | set 1 0 | 1 0 | | 1 / | | | ----+------+--------------+------- | | | 1 1 | 0 1 | | 1 \ | | | | toggle (changes to Q`) 1 1 | 1 0 | | 0 / | | | ----+------+--------------+------- 4. 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 set/reset 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, current state Q(t), next state Q(t+1), and output S. (b) Give the state diagram. 5. Consider a state machine with two inputs, R and I (reset and in), that, after a reset R, outputs a 1 on each second 1 that it receives on input I. Reset causes any count of previous and current I=1 inputs to be lost, and the counting of I=1 inputs starts in the subsequent clock cycle after the reset signal goes back to 0. That is, the state machine behaves like this input R: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 input I: 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 output S: 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 (a) Give the state diagram. (There should only be two states.) (b) Give the state transition table with inputs R, I, current state Q(t), next state Q(t+1), and output S. (c) Give the simplified logic expressions for Q(t+1) and S. (d) Extend the state transition table with Jand K columns and, using the JK excitation table, fill in the appropriate values for causing the required state transitions. (e) Give the simplified logic expressions for J and K.