Final Solution

UNIVERSITY OF MICHIGAN EECS 270: Intro to Logic Design Final Exam Prof. Karem A Sakallah Wednesday December 18, 2019 4:00-6:00 p.m. A - R: 220 CHRYSLER S - Z: 906G COOLEY Name: UMID: Honor Pledge: “I have neither given nor received aid on this exam, nor have I concealed any violation of the Honor Code.” Signature: Instructions: • The exam is closed book except for three 8.5"x11" sheets of notes. No electronics of any kind may be used. • Print your name and student ID number and sign the honor pledge. • The exam consists of 6 problems with the point distribution indicated here. Please keep this in mind as you work through the exam. Use your time wisely. • There are 11 sheets in this exam. Make sure that you have all 11 sheets and notify an instructor if you do not. 1. /15 2. /15 3. /20 4. /25 5. /15 6. /10 Total: /100

EECS 270 University of Michigan Fall 2019 1 [You ought to know this stuff :-)–15 points] a. [1.5 points] When adding two n -bit signed numbers, overflow can never occur if the sign bits of the addends are the same. TRUE FALSE FALSE b. [1.5 points] All minterms of a function are prime implicants. TRUE FALSE FALSE c. [1.5 points] A minterm that is a prime implicant must be essential. TRUE FALSE TRUE d. [1.5 points] If ab 0 is an implicant of a function f , then ab 0 d is too. TRUE FALSE TRUE e. [1.5 points] A positive level-sensitive D latch stores the value present on the D input on the falling edge of the clock. TRUE FALSE TRUE f. [1.5 points] The output of an SR latch will oscillate while S = 1 and R = 1. TRUE FALSE FALSE Page 2

EECS 270 University of Michigan Fall 2019 2 [And this stuff too!–15 points] a. [1.5 points] We wish to make a 64-way 1-bit multiplexor from several 4-way 1-bit multiplex- ors and no other components. What is the minimum number of 4-way multiplexors we need? Answer: # 1st-level Muxes = 64 / 4 = 16 # 2nd-level Muxes = 16 / 4 = 4 # 3rd-level Muxes = 4 / 4 = 1 ∴ minimum number of Muxes = 16 + 4 + 1 = 21 b. [2 points] Let m i ( x 1 , · · · , x n ) and M j ( x 1 , · · · , x n ) be, repectively, the i th minterm and j th maxterm for i, j ∈ [0 , 2 n - 1] . Assuming that i 6 = j , to what does each of the following expressions evaluate? m i + M i = m i + M j = m i · M i = m i · M j = m i + M i = 1 since M i = m 0 i . m i + M j = M j since m i = 0 except in “row” i and M j = 1 except “row” j , hence m i → M j (i.e., m i is covered by M j .) m i · M i = 0 m i · M j = m i c. [1.5 points] The decimal value of the 7-bit string 1011101 As a signed magnitude number is: As a two’s complement number is: As a ones’ complement number is: 1011101 SM = - (2 0 + 2 2 + 2 3 + 2 4 ) = - 29 10 1011101 2 C = - 0100011 2 C = - (2 5 + 2 1 + 2 0 ) = - 35 10 1011101 1 C = - 0100010 1 C = - (2 5 + 2 1 ) = - 34 10 d. [2.5 points] f ( a, b, c, d ) = Σ a,b,c,d (1 , 3 , 7 , 15) . The number of minterms f has in its canonical SOP representation is: The number of maxterms f has in its canonical POS representation is: The prime implicants of f are: Page 4

EECS 270 University of Michigan Fall 2019 The minimal SOP expression for f is: , and it is (circle one) NON-UNIQUE UNIQUE The number of minterms f has in its canonical SOP representation is: 4 The number of maxterms f has in its canonical POS representation is: 12 The prime implicants of f are: a 0 b 0 d, a 0 cd, and bcd The minimal SOP expression for f is: a 0 b 0 d + bcd and it is UNIQUE e. [1.5 points] A sequential circuit has four inputs x 3 , x 2 , x 1 , and x 0 , four outputs y 3 , y 2 , y 1 , and y 0 and just four D flip-flops. Input x i and output y i are connected, respectively, to the D input and Q output of flip-flop i . The number of states this circuit has is: The number of state transitions this circuit has is: This circuit is a (circle one) Moore Mealy Machine. The number of states this circuit has is: 2 4 = 16 The number of state transitions this circuit has is: 2 4 × 2 4 = 256 since each state can transition to every other state including itself. This circuit is a (circle one) Moore Machine. Page 5

EECS 270 University of Michigan Fall 2019 h. [2 points] DFF D Q Q C The timing parameters for the inverter and D flip-flop in this circuit are: • Inverter delay = 20 ps • Clock-to- Q delay = 30 ps • Setup time = 50 ps. • Hold time = 5 ps Calculate the minimum clock period for which this circuit will operate without exhibiting metastable behavior. Answer: Minimum clock period = clock-to- Q delay + inverter delay + setup time = 30 + 20 + 50 = 100 ps. Page 7

EECS 270 University of Michigan Fall 2019 3 [Carry Lookahead Analysis–20 points] a. [3 points] Consider the following 3-bit range [ i + 2 , i ] starting at some bit position i : UM EECS 270 Fall 2019 8 7 8,6 8 c 9 c 0 6 8 c c c 7 c ( ) ( ) 3 2 2 2 2 2 1 1 1 2 2 1 2 1 1 2 2 1 2 1 2 2 1 2 1 2 1 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i c g p c g p g p c g p g p p c g p g p p g p c g p g p p g p p p c + + + + + + + + + + + + + + + + + + + + + + + + + + + = + = + + = + + = + + + = + + + 8 7 8,6 8 c 9 c 1 i c + 2 i c + i c 3 i c + Bit i +2 2 i a + 2 i b + Bit i +1 1 i a + 1 i b + i a i b Bit i 8,6 11,9 14,12 17,15 17,9 17 16 15 14 13 12 11 10 9 10 c 11 c 12 c 13 c 14 c 15 c 16 c 17 c 18 c 8 7 c 8 c 9 c 17,0 Derive the SOP expressions for the 3-bit group generate and propagate signals G i +2 ,i and P i +2 ,i in terms of the bit generate and propagate signals g i , g i +1 , g i +2 , p i , p i +1 and p i +2 . [2 Points] G i +2 ,i = [1 Point] P i +2 ,i = G i +2 ,i = g i +2 + p i +2 g i +1 + p i +2 p i +1 g i P i +2 ,i = p i +2 p i +1 p i b. [13 points] Using the following generate/propagate structure of a 9-bit CLA adder, let t i,j P be the propagation delay to c j given that it is computed from c i . Assume that all gates have unit delay and that all inputs are available at t = 0 . Enter these propagation delays in the following table and circle the entries that correspond to the minimum delays. If the carry in column j cannot be computed from the carry in row i , cell ( i, j ) should be blank. UM EECS 270 Fall 2019 2 8 7 6 5 4 3 2 1 0 2,0 5,3 8,6 8,0 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 0 c 1 c 0 6 8 c c c 7 c 6 c 3 5 c c 4 c 3 c 0 2 c c i c 8 7 6 5 4 3 2 1 0 2,0 5,3 8,6 8,0 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c i c Bit i i a i b Page 8

EECS 270 University of Michigan Fall 2019 c. [4 points] Now consider building an 18-bit CLA adder by introducing another level of generate/propagate logic as shown below: UM EECS 270 Fall 2019 2 0 c 1 c 0 6 8 c c 7 c 6 c 3 5 c 4 c 3 c 0 2 c 17 9 9,17 0,9 0,8 0,9 7,8 ,min ,min ,min ,min 6 11 P P P P P P P t t t t t t t = + = + = + = + ( ) ( ) 3 2 2 2 2 2 1 1 1 2 2 1 2 1 1 2 2 1 2 1 2 2 1 2 1 2 1 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i c g p c g p g p c g p g p p c g p g p p g p c g p g p p g p p p c + + + + + + + + + + + + + + + + + + + + + + + + + + + = + = + + = + + = + + + = + + + 8 7 6 5 4 3 2 1 0 2,0 5,3 8,6 8,0 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 9-Bit CLA 9-Bit CLA 0 c 9 c 18 17 c 2,0 5,3 8,6 11,9 14,12 17,15 17,9 8,0 17 16 15 14 13 12 11 10 9 10 c 11 c 12 c 13 c 14 c 15 c 16 c 17 c 18 c 8 7 6 5 4 3 2 1 0 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 17,0 Let t i,j P,min be the minimum delay from c i to c j . Compute t 0 , 17 P,min and t 0 , 18 P,min . [2 Points] t 0 , 17 P,min = [2 Points] t 0 , 18 P,min = t 0 , 17 P, min = t 0 , 9 P, min + t 9 , 17 P, min = t 0 , 9 P, min + t 0 , 8 P, min since the CLA structures from 0 to 8 and from 9 to 17 are identical = 6 + 10 = 16 To find t 0 , 18 P,min , we note that c 18 can be computed directly from c 0 according to: c 18 = G 17 , 0 + P 17 , 0 · c 0 G 17 , 0 = G 17 , 9 + P 17 , 9 G 8 , 0 P 17 , 0 = P 17 , 9 · P 8 , 0 From the GP structure the depth of G 17 , 0 and P 17 , 0 is, respectively 7 and 4. Thus, t 0 , 18 P, min = 1 + max [7 , 1 + max(4 , 0)] = 1 + max[7 , 5] = 8 Page 10

EECS 270 University of Michigan Fall 2019 4 [Sequential Multiplication–25 points] Consider the following datapath and controller for an unsigned 4-bit sequential multiplier. Its basic structure is similar to design V1.0 that was discussed in lecture but has been augmented to allow for the multiplication of a sequence of unsigned 4-bit numbers. To use it, the START “button” must be pressed after the numbers to be multiplied are applied to inputs X and Y . The result is displayed on the 8-bit output Z when the DONE indicator turns on. At that point the multiplier returns to its initial state and is ready for another multiplication operation. Unsigned Sequential Multiplier Datapath 7 m 0 4-bit Reg Q 4-bit Adder 4-bit Reg M 5-bit Reg P X Y 2 -bit CTR EQ_ZERO START CTR = 0 DONE Q_LOAD P_LOAD M_LOAD P_SHIFT-RIGHT M_SHIFT-RIGHT P_CLEAR CTR_CLEAR CTR_DOWN Data Path Controller Z = X * Y a. [9 points] Complete the multiplier’s control state diagram, shown below, by: • Writing the required transition conditions inside the indicated boxes. • Selecting the outputs that must be set to 1 in each of the controller’s six states by completely filling the appropriate “bubbles”. Unsigned Sequential Multiplier Controller _ _ _ - _ _ _ - _ _ P CLEAR P LOAD P SHIFT RIGHT Q LOAD M LOAD M SHIFT RIGHT CTR CLEAR CTR DOWN DONE                                                       CTR ≠ 0 S0 S1 S2 S3 S4 S5 m 0 1 1 1 CTR = 0 Page 11

EECS 270 University of Michigan Fall 2019 Unsigned Sequential Multiplier Timing Diag CLK State S3 S4 S1 S1 S3 S4 S1 S3 S4 S2 S3 S4 S5 S0 S1 0 0 3 3 3 2 2 1 2 1 1 1 0 0 0 CTR 0 Q 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 7 P 0 0 0 0 0 0 0 0 0 0 0 15 7 7 7 0 M 8 8 4 4 4 2 2 1 2 1 1 1 8 8 8 9 S1 8 4 4 4 2 2 1 2 1 1 1 8 8 8 9 S0 Cycle # 1 2 3 4 5 6 7 10 8 9 11 12 13 14 15 16 0 17 8 0 0 0 0 Unsigned Sequential Multiplier Timing Diag Solution: Decimal Q 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 P 0 0 0 0 0 0 0 0 0 0 0 15 7 7 7 M 8 8 4 4 4 2 2 1 2 1 1 1 8 8 8 CLK 0 0 3 3 3 2 2 1 2 1 1 1 0 0 0 CTR State S0 S1 S3 S4 S1 S1 S3 S4 S1 S3 S4 S2 S3 S4 S5 S0 DONE INIT P_LD NEXT S1 0 7 0 9 S2 0 7 0 9 Cycle # 1 2 3 4 5 6 7 10 8 9 11 12 13 14 15 16 0 17 Page 13

EECS 270 University of Michigan Fall 2019 5 [State Minimization–15 points] The state table, shown below, is for a sequential circuit with one input x and one output z . Complete the state merger diagram for this circuit and answer the following questions. Current Input State x = 0 x = 0 A A, 1 E, 0 B C, 0 A, 1 C B, 0 C, 1 D B, 0 C, 1 E D, 0 F, 1 F A, 1 B, 0 Next State, z A B C D E B E C D F A B C D B E C D F BE AF CD AC AC BC BD CF  BD CF a. [2 points] States C and E are equivalent. TRUE FALSE b. [2 points] States A and F are equivalent. TRUE FALSE c. [2 points] State B is equivalent to: A: State F B: State C C: State A D: State D E: None of the choices d. [2 points] The minimum number of states is: A: 3 B: 4 C: 5 D: 2 E: 6 e. [2 points] Using suitable labels for the equivalent states, complete the following minimal state table. Current Input State x = 0 x = 1 Next State, z Page 14

EECS 270 University of Michigan Fall 2019 6 [Lab Experience–10 points] State Diagram Key Mxy Means move from floor x to floor y. i.e. M21 means moving from floor 2 to 1 OPx Means elevator is on floor x with doors open. i.e. OP1 means on floor 1 with door open. The adjacent state diagram represents the opera- tion of an elevator servicing 3 floors. The elevator normally rests on floor 2 with the doors open. The elevator will move to a requested floor if the respec- tive button is pushed and the doors have been open for at least 4 seconds. If the elevator is at any floor for 6 seconds, it will return to floor 2 and remain there until there is another request. Complete the following Verilog that implements the elevator FSM. You can assume that only one button is pushed at a time and the clock occurs once a second. Assume the state encoding is provided. Each blank is worth one point for a total of 10 points . No partial credit. module elevator ( clock , reset , B1 , B2 , B3 , HEX0, HEX1) ; input clock , reset , B1 , B2 , B3 ; output reg [ 6 : 0 ] HEX0; // f l o o r HEX0[ 0 ] = segment 0 , etc output reg [ 6 : 0 ] HEX1; //door parameter O = _____________________; //O parameter C = 7 ’ b1000110 ; //C parameter n1 = 7 ’ b1111001 ; //1 parameter n2 = 7 ’ b0100100 ; //2 parameter n3 = 7 ’ b0110000 ; //3 _________________________ s , ns , count ; reg TR; //Tgt3 i s count greater than 3 seconds //Teq6 i s count equal 6 seconds ______________ Tgt3 , Teq6 ; assign Tgt3 = ____________________________; assign Teq6 = ( count ==6) ? 1 : 0 ; Page 16

EECS 270 University of Michigan Fall 2019 always @ * begin case ( s ) OP1: i f (B2&T3 | T6) ns = MV12; else i f (B3&T3) ns = MV13; else ns = OP1; MV12: ns = OP2; MV13: ns = MV23; OP2: i f (B3&T3) ns = MV23; else i f (B1&T3) ns = MV21; else ns = OP2; MV21: ns = OP1; MV23: ns = OP3; OP3: ______________________________________________________________; ___________________________________________________________________; ___________________________________________________________________; default : ns = OP2; endcase end always @ ( posedge clock ) begin i f ( r e s e t == 1 ’ b1 ) s <= OP2; else ______________________; i f (TR | | r e s e t ) _________________________; else i f ( count < 6) count <= count + 1; end always @ * begin case ( s ) OP1: begin HEX1 = O; HEX0 = n1 ; TR = 0; end MV12: begin HEX1 = C; HEX0 = n1 ; TR = 1; end MV13: begin HEX1 = C; HEX0 = n1 ; TR = 1; end OP2: begin __________________________________________; end MV21: begin HEX1 = C; HEX0 = n2 ; TR = 1; end MV23: begin HEX1 = C; HEX0 = n2 ; TR = 1; end OP3: begin HEX1 = O; HEX0 = n3 ; TR = 0; end MV32: begin HEX1 = C; HEX0 = n3 ; TR = 1; end MV31: begin HEX1 = C; HEX0 = n3 ; TR = 1; end default : begin HEX1 = O; HEX0 = n2 ; TR = 0; end endcase end endmodule module elevator ( clock , reset , B1 , B2 , B3 , HEX0, HEX1) ; Page 17

EECS 270 University of Michigan Fall 2019 OP3: begin HEX1 = O; HEX0 = n3 ; TR = 0; end MV32: begin HEX1 = C; HEX0 = n3 ; TR = 1; end MV31: begin HEX1 = C; HEX0 = n3 ; TR = 1; end default : begin HEX1 = O; HEX0 = n2 ; TR = 0; end endcase end endmodule Page 19