EECE 320 Midterm, Fall 2004

Page 1 of 11 A. CHEHAB DEPARTMENT OF ELECTRICAL AND COMPUTER EGINEERING M. MANSOUR AMERICAN UNIVERSITY OF BEIRUT FALL TERM 2004-2005 MIDTERM II EE/CCE 2007 EECE320 - DIGITAL SYTEMS DESIGN January 4, 2005 NAME: _____________________ ID: _____________________ COURSE SECTION: SECTION 1 (PROF. CHEHAB) SECTION 2 (PROF. MANSOUR) INSTRUCTIONS: Problem Total Points Earned Points 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 10 Total 100 o THE EXAM IS CLOSED BOOK/CLOSED NOTES. THE DURATION IS TWO HOURS. o CALCULATORS ARE NOT ALLOWED. o WRITE YOUR NAME AND ID NUMBER IN THE SPACE PROVIDED ABOVE. o INDICATE THE SECTION YOU ARE REGISTERED IN. o PROVIDE YOUR ANSWERS IN THE SPACE PROVIDED ON THE QUESTION SHEET. o THE SCRATCH BOOKLET WILL NOT BE CONSIDERED IN GRADING. o BE AS NEAT AND CLEAR AS POSSIBLE. o ALL QUESTIONS ARE EQUALLY WEIGHTED Page 2 of 11 Problem 1: [10 points] Using a Moore machine with D Flip-Flops, design a sequence detector that would output a Z=1 only after detecting the sequence 11001 on its single input X. Call the states S0, S1 etc. (use don’t cares for illegal states and use simplest state assignment) A. Draw the state diagram in the space below. [7 points] B. Fill as much as needed in the corresponding state and transition tables shown below. X S 0 1 Z S* C. The excitation equations are given by: [3 points] D1 = ____________________ D2 = __________________ D3 = _____________ ____________________ __________________ _____________ X Q1Q2Q3 0 1 Z Q3X Q1Q2 00 01 11 10 00 01 11 10 Q3X Q1Q2 00 01 11 10 00 01 11 10 Q3X Q1Q2 00 01 11 10 00 01 11 10 Page 3 of 11 Problem 2: [10 points] Consider the function: F = ΣA,B,C,D(0, 2, 3, 5, 7, 8, 10, 11, 14, 15) a) What are the prime implicants of F? [2 points] _______________________________________________ b) What are the essential prime implicants of F? [2 points] _______________________________________________ c) What is a minimum SOP expression for F? [3 points] _______________________________________________ d) What is a minimum POS expression for F? [3 points] _________________________________________________ Problem 3: [10 points] Consider the Boolean function F = ΣA,B,C,D(1, 3, 4, 11, 12, 13, 14, 15) a) Implement F using a 4-input multiplexer and external gates. Connect A and B to the select lines. [5 points] b) Implement F using two 3-to-8 decoders with enables, an inverter and OR gates with maximum inputs of 4. [5 points] CD AB 00 01 11 10 00 01 11 10 Page 4 of 11 Problem 4: [10 points] Design an Excess-3 to BCD code converter that gives output code of don’t-cares for all invalid input combinations. Complete the table to include for every integer the corresponding BCD code representation. EXCESS-3 BCD b3 b2 b1 b0 g3 g2 g1 g0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 We want to design a circuit that performs the above conversion. Write the expressions of g3, g2, g1, and g0 in terms of b3, b2, b1 and b0. g3 = ____________________________ g2 = ____________________________ g1 = ____________________________ g0 = ____________________________ Page 5 of 11 Problem 5: [10 points] A sequential circuit has 2 flip-flops A and B, one input X and one output Y. Its state diagram is shown below. Design the circuit using D flip-flops and draw the corresponding logic diagram. 1 0 0 1 1 1 0 0 00 1 01 0 11 0 10 0 Page 6 of 11 Problem 6: [10 points] We would like to analyze the following clocked synchronous state machine. A. Write the next state equations for A and B. [4 points] A* = ____________________________________ B* = ____________________________________ B. Complete the excitation/transition table, and the state table (use the following state names A = 00, B = 01, C = 11, D = 10) [4 points] X AB 0 1 0 0 0 1 1 1 1 0 A*B*, Y C. Draw the state diagram. [2 points] X S 0 1 A B C D S*, Y Page 7 of 11 S R Q Q C J K S R Q Q C Q QN QM QM_L C J K C QM QM_L Q QN SM RM SM RM Problem 7 [10 points] Consider the following Master-Slave JK flip-flop built using SR latches. The S input in the SR latches corresponds to a SET, the R input corresponds to a RESET, and the C input corresponds to ENABLE. (a) Complete the timing diagram below. [8 points] (b) Do you see a potential problem in this JK flip-flop? [2 points] Page 8 of 11 Problem 8: [10 points] An MN flip-flop has four operations: clear to 0, no change, toggle, and set to 1, when inputs M and N are 00, 01, 10, and 11, respectively. a) Determine the characteristic equation of an MN flip-flop. [2 points] b) Design an MN flip-flop using a T flip-flop with enable and extra logic gates. [4 points] c) Design a JK flip-flop using an MN flip-flop and extra logic gates. [4 points] Page 9 of 11 Problem 9: [10 points] Design a 4-bit Johnson counter using D flip-flops. Answer: Page 10 of 11 001 010 100 011 110 111 101 State = Q 3Q2Q1 D Q D Q CLK D Q Q3 Q2 Q1 001 010 100 011 110 111 101 State = Q 3Q2Q1 000 Problem 10: [10 points] In this problem, we want to design a 3-bit counter using a shift register. a) Assume the shift register below initially stores Q3Q2Q1=001. Modify the shift register by adding extra logic gates so that it implements the state diagram shown on the right. (Hint: write next-state equations for Q3, Q2, Q1). Solution: b) Modify your design in part (a) to include the 000 state. Solution: Page 11 of 11 counter from part (b) Q3 Q2 Q1 CLK c) The counter you designed in part (b) is shown below as a black box that produces the sequence 000, 001, 010, 100, 011, 110, 111, 101 and then repeats. Describe what you would add to your counter so that it produces the sequence 000, 001, 010, 011, 100, 101, 110, 111 and then repeats.