Final Solution-1

UNIVERSITY OF MICHIGAN EECS 270: Intro to Logic Design Final Exam Prof. Karem A Sakallah Tuesday December 14, 2021 4:00-6:00 p.m. A - L: 2505 GGBL M - Z: 1571 GGBL 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. • Make sure your answers and meaningful work are on the pages with numbers at the bottom. We will be scanning and looking at only these pages: all work on the backs of pages will not be checked for determining partial credit. • The exam consists of 9 problems with the point distribution indicated here. Please keep this in mind as you work through the exam. Use your time wisely. • There are 10 pages in this exam. Make sure that you have all 10 pages and notify an instructor if you do not. 1. /10 2. /8 3. /12 4. /10 5. /15 6. /15 7. /5 8. /15 9. /10 Total: /100

EECS 270 University of Michigan Fall 2021 1 [Boolean Algebra Basics–10 points] a. An n -variable switching function with m distinct maxterms in its canonical POS form has 2 n - 2 m distinct minterms in its canonical SOP form. True False b. A NOR gate can be used to check the equivalence of two bits. True False c. a ⊕ b = a b 0 . True False d. xy + ( zx + zy ) = xy + ( zx ⊕ zy ) . True False e. The number of possible switching functions of 20 variables is 2 20 . True False f. m 0 7 ( a, b, c, d ) = a 0 + b + c + d . True False g. An n -variable OR function has 1 maxterm. True False A switching function is balanced if the number of its minterms is equal to the number of its maxterms. h. xy + zx + zy is balanced. True False i. a + b + c is balanced. True False j. a ⊕ b ⊕ c is balanced. True False a. False b. False c. True d. True e. False f. False g. True h. True i. False j. True Page 2

EECS 270 University of Michigan Fall 2021 3 [K-Map Minimization–12 points] 00 01 11 10 00 01 11 10 d d d 1 1 1 x y z 1 d d d w a. [1 point] w 0 x is a prime implicant Yes No b. [1 point] w 0 z 0 is a prime implicant Yes No c. [1 point] xz is a prime implicant Yes No d. [1 point] w 0 x is an essential prime implicant Yes No e. [1 point] w 0 z 0 is an essential prime implicant Yes No f. [1 point] xz is an essential prime implicant Yes No g. [1 point] w 0 yz is a prime implicant Yes No h. [1 point] xy is a prime implicant Yes No i. [1 point] xy is an essential prime implicant Yes No j. [3 points] A minimal POS form for this function is Use Kmap package to annotate kmap a. Yes b. No c. Yes d. No e. No f. Yes g. No h. Yes i. No j. z ( w 0 + x )( w + y ) or z ( w 0 + x )( x + y ) 00 01 11 10 00 01 11 10 d d d 1 1 1 x y z 1 d d d w Page 4

EECS 270 4 [Counters–10 points] This circuit below consists of two whose outputs are connected to an is used to conditionally clear both counters, i.e., set them to 0; the counters’ CLR inputs are synchronous with the clock. How long is the repeating counting sequence of either of the counters when: a. [2 points] b. [2 points] The counter circuit below has a single high clear. c. [2 points] Using operators from the set {AND · , OR + , NOT 0 , XOR ⊕ } write a symbolic expression for Q + 2 in terms of Q 2 , Q 1 , Q 0 , and mode ? Q + 2 = d. [2 points] Modulus when mode = 0 is e. [2 points] Modulus when mode = 1 is Page 5

EECS 270 University of Michigan Fall 2021 5 [RTL Design–15 points] The figure below shows the controller and datapath block diagram as well as the control state diagram for the laser measurer from homework # 8. Complete the transition lists for the controller and data path by entering in the boxes below Use + for integer addition, » for right-shifting. Note that “Cond” is the symbolic transition expression (i.e., arrow label), and that “DP PS” and “DP NS” denote, respectively, the datapath present and next state. Q Cond Q + L C.CLR C.UP D.LD DP PS Cond DP NS U C U C V C W D W D X Y Y Page 7

EECS 270 University of Michigan Fall 2021 Q Cond Q + L C.CLR C.UP D.LD DP PS Cond DP NS U B V 0 0 0 0 C C.CLR C < = ZERO U B 0 U 0 0 0 0 C C.UP C < = C + 1 V 1 W 1 0 0 0 C C.CLR 0 C.UP 0 C < = C W S X 0 0 1 0 D D.LD D < = C >> 1 W S 0 W 0 0 1 0 D D.LD 0 D < = D X 1 Y 0 0 0 1 Y B V 0 1 0 0 Y B 0 Y 0 1 0 0 Page 8

EECS 270 University of Michigan Fall 2021 Page 10

EECS 270 University of Michigan Fall 2021 7 [Carry Look Ahead–5 points] Let G j,i and P j,i denote the group generate and propagate signals, respectively, for the bit range [ j, i ] ( j ≥ i ) in a carry look ahead adder. Note that the bit generate and bit propagate signals can be viewed as group signals over the single-bit range [ i, i ] , i.e., g i = G i,i and p i = P i,i . Using this notation, which of the following is not equal to G 9 , 2 ? a. G 9 , 6 + P 9 , 6 · G 5 , 2 b. G 9 , 5 + P 9 , 5 · G 4 , 2 c. G 9 , 8 + P 9 , 8 · G 7 , 2 d. G 9 , 7 + P 9 , 7 · ( G 6 , 3 + P 6 , 3 · G 2 , 2 ) e. They are all equal to G 9 , 2 The answer is E; they are all equal to G 9 , 2 . The basic template is G H,L = G H + P H G L where H and L are a partition of a given range R . For this problem R = [9 , 2] . In choice a, H = [9 , 6] and L = [5 , 2] so this is correct. In choice b, H = [9 , 5] and L = [4 , 2] so this is also correct. In choice c, H = [9 , 8] and L = [7 , 2] , again correct. In choice d, H = [9 , 7] and L = [6 , 2] , i.e., G 9 , 2 = G 9 , 7 + P 9 , 7 · G 6 , 2 . But G 6 , 2 = G 6 , 3 + P 6 , 3 · G 2 , 2 so this is correct as well. Page 11

EECS 270 University of Michigan Fall 2021 9 [Lab Experience–10 points] Complete the following Verilog for a simple traffic signal with the following rules. The highway light should be green for a minimum of 10 timer counts. The highway light should remain green as long as traffic is not detected on the side road. The side road light should remain green as long as the sensor is active, but not to exceed a timer count of 5. A yellow light transition occurs between green lights and lasts for just one FSM clock. Sensor is active high. HEX LEDS are active low. DZUV U`RU +ZXYZR\ +/ +/ D/ D/ D D D VV_V`U module traffic1( input clk , sensor , reset , output reg [6:0] HL , SL); // Highway and side street lights reg [1:0] ; reg [31:0] ; timer_reset; always@* begin case(s) 0: if ns = 1; else ns = 0; // highway green state 1: ns = 2; // highway to side yellow state 2: if ns = 3; else ns = 2; // side street green state 3: ns = 0; // side to highway yellow state endcase end always@(posedge clk) begin if( ) begin s <= 0; timer <= 0; end else ; if(timer_reset) timer <= 0; else ; end always@* begin case(s) 0: begin HL = 7’b0010000; SL = 7’b0101111; timer_reset = 0; end 1: begin HL = ; SL = 7’b0101111; timer_reset = 1; end 2: begin HL = 7’b0101111; SL = 7’b0010000; timer_reset = 0; end 3: begin HL = ; SL = 7’b0010001; timer_reset = 1; end endcase end endmodule Page 13

EECS 270 University of Michigan Fall 2021 module traffic1( input clk , sensor , reset , output reg [6:0] HL , SL); // Highway and side street lights reg [1:0] s, ns ; reg [31:0] timer ; reg timer_reset; always@* begin case(s) 0: if ((timer>10) & sensor) ns = 1; else ns = 0; // highway green state 1: ns = 2; // highway to side yellow state 2: if ((timer>5) | -sensor) ns = 3; else ns = 2; // side street green state 3: ns = 0; // side to highway yellow state endcase end always@(posedge clk) begin if( reset ) begin s <= 0; timer <= 0; end else s <= ns ; if(timer_reset) timer <= 0; else timer <= timer + 1 ; end always@* begin case(s) 0: begin HL = 7’b0010000; SL = 7’b0101111; timer_reset = 0; end 1: begin HL = 7’b0010001 ; SL = 7’b0101111; timer_reset = 1; end 2: begin HL = 7’b0101111; SL = 7’b0010000; timer_reset = 0; end 3: begin HL = 7’b0101111 ; SL = 7’b0010001; timer_reset = 1; end endcase end endmodule Page 14