CPSC 330 - Spring 2007 Homework 2 Due - Monday, Feb. 12, at class time 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 true because the last 1 1 | 0 | 1 | 1 | 1 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. Problem A.2(b) on page 724 of your text. 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. Problem A.3 on page 725 of your text -- use Karnaugh maps. Example Design a 2-input circuit that gives an output of 1 only when the two inputs are equal. First, show the truth table; and, second, show the gate implementation. (This is the equality function or inverse-xor.) A B | F in SOP form, A----*-----. ----+-- _ _ | AND-. 0 0 | 1 F = A*B + A*B B-*--------' | _ _ 0 1 | 0 | | OR = A*B + A*B 1 0 | 0 | `-NOT-. | 1 1 | 1 | AND-' `----NOT-' 3. A majority function is implemented by a combinational circuit when the output is one if and only if the input variables have more ones than zeros. Otherwise, the output is zero. Design a 3-input majority function. First, show the truth table. Second, show the gate implementation using AND, OR, and NOT gates. Example Consider again the equality function F= A*B + (~A)*(~B). Implement this expression using one OR gate and two NAND gates. A. check: __________ NAND-. _____________ __ ____ ____ B' | _____ A B | AB AB A+B | (AB)*(A+B) (AB)*(A+B) NAND = (A*B) * (A+B) ----+-----------+---------------------- A. | 0 0 | 0 1 0 | 0 1 OR---' 0 1 | 0 1 1 | 1 0 B' 1 0 | 0 1 1 | 1 0 1 1 | 1 0 1 | 0 1 4. Problem A.13 on page 726 of your text. Example Show that the "JK" circuit given in the Wikipedia entry "SR_latch" (http://en.wikipedia.org/wiki/Image:JK_latch_%28AND-NOR%29.png, accessed Feb. 1, 2007), is incorrectly labeled. First, note that the circuit is built from an inner RS nor-nor latch (cf. http://en.wikipedia.org/wiki/Image:SR-NOR-latch.png). In the "JK" circuit depicted, R = J and Q, and S = K and not-Q. _ _ J K | Q Q | R=JQ S=KQ | Q_next ----+-----+-----------+------- 0 0 | 0 1 | 0 0 | 0 Q_previous 0 0 | 1 0 | 0 0 | 1 ----+-----+-----------+------- 0 1 | 0 1 | 0 1 | 1 1 0 1 | 1 0 | 0 0 | 1 ----+-----+-----------+------- 1 0 | 0 1 | 0 0 | 0 0 1 0 | 1 0 | 1 0 | 0 ----+-----+-----------+------- _ 1 1 | 0 1 | 0 1 | 1 Q_previous 1 1 | 1 0 | 1 0 | 0 5. Show that a circuit diagram in which R = K and Q, and S = J and not-Q, (e.g., http://www.shef.ac.uk/physics/teaching/phy107/jkff.html), conforms to the characteristic table for a JK circuit. (Note that JK should be implemented as a flip-flop rather than as a mere latch so that J=K=1 will not cause multiple state changes.) (Extra credit: does the nand-nand circuit shown on the Univ. Sheffield web page conform to the JK characteristic table or to the SR table? -- cf. Figure A.26 on p. 693 in your textbook. Explain your answer fully for full extra credit.) Example A sequential circuit has one D flip-flop, two inputs X and Y, and one output A. The combinational logic consists of two cascaded xor gates with the output of the second gate being used as the next state. A = Q(t) D_in = Q(t) xor (X xor Y) .--------------------------. | | | +-----+ | +-----+ `-->| | D_in +---+ Q | X--->| | | xor |------->| |---*-----> A | xor |------>| | | D | Y--->| | +-----+ CLK->| | +-----+ +---+ The truth table for this circuit is current next inputs state output state X Y Q(t) | X xor Y | A D_in == Q(t+1) ---------------+-----------+----------------------- 0 0 0 | 0 | 0 0 0 0 0 1 | 0 | 1 1 1 0 1 0 | 1 | 0 1 1 0 1 1 | 1 | 1 0 0 1 0 0 | 1 | 0 1 1 1 0 1 | 1 | 1 0 0 1 1 0 | 0 | 0 0 0 1 1 1 | 0 | 1 1 1 or you may find it easier to order the table with the current state listed first (the tables are equivalent) current next state inputs output state Q(t) X Y | X xor Y | A D_in == Q(t+1) ----------------+-----------+----------------------- 0 0 0 | 0 | 0 0 0 0 0 1 | 1 | 0 1 1 0 1 0 | 1 | 0 1 1 0 1 1 | 0 | 0 0 0 1 0 0 | 0 | 1 1 1 1 0 1 | 1 | 1 0 0 1 1 0 | 1 | 1 0 0 1 1 1 | 0 | 1 1 1 The state diagram for this circuit as a Moore machine (where the outputs are associated with the states) is: 01,10 .---. .-----------. .---. / v.===./ v.===./ \ 00,11 | |0/0| |1/1| | 00,11 \ /`==='^ /`==='^ / `---' `-----------' `---' 01,10 (Note that a part of this circuit is essentially a T flip-flop.) 6. Problem A.38 on page 731 of your text.