Department of Electrical & Computer Engineering ECE 152AUniversity of California, Santa Barb ara Summer 2011ShynkH.O. #21EXAMPLE FINAL EXAMINSTRUCTIONS1. This exam is open book and open notes.2. It consists of 4 problems and is worth a maximum of 100 p oints. The problems are not ofequal difficulty, so use discretion in allocating your time. Answer all questions in any order.3. Show your an s wers in the spaces and additional pages provided, and use the back side of theexam pages if you need additional work space. Show your reasoning and the essentialsteps clearly and concisely.Last Name, First Name:1ECE 152ASummer 20111. MULTIPLEXERS AND DECODERS (25 points)Consider the following function:f(x1, x2, x3, x4) =Xm(0, 4, 6, 7, 8, 11, 12, 14, 15) (1)(a) Find the minimum sum-of-products (SOP) implementation for f using a Karnaugh m ap.(b) Use Shannon’s expansion theorem to rewrite the result in part (a) by expanding it in terms ofx3. Sketch a circuit diagram th at implements f using a 2:1 multiplexer.(c) Starting with th e result in part (b), use Shannon’s expansion theorem to fur th er expand f interms of x4. Sketch a circuit diagram that implements f using a 4:1 multiplexer.(d) Show how to implement a 4:16 decod er with inputs {x1, x2, x3, x4} using two 3:8 decoders .Then, use this decoder along with six two-input OR gates and one three-input OR gate toimplement f in part (a).Solution:2ECE 152ASummer 20113ECE 152ASummer 20112. STATE MINIMIZATION AND MACHINE CONVERSION (30 points)Consider the following next-state table for a Mealy machine with input x and output z:present statex = 0 x = 1A E, 0 D, 0BA, 1 F, 0CC, 0 A, 1DB, 0 A, 0ED, 1 C, 0FC, 0 D, 1GH, 1 G, 1HC, 1 B, 1(a) Use partitioning to generate a reduced state m achine. (Hint: The minimal Mealy machine hasfive states. Use {A′, B′, C′, D′, E′} to label th e reduced set of states.)(b) Use an implication table to obtain the same set of reduced states. Clearly in dicate your steps.Give the state table for the reduced Mealy machine.(c) Convert the reduced Mealy machine to th e corresponding Moore machine. When you splita state into two states, label them numerically, for example, B′→ {B1′, B2′}. Sketch theMoore state diagram. (Hint: The minimal Moore machine has eight states.)Solution:4ECE 152ASummer 20115ECE 152ASummer 20113. SEQUENCE DETECTOR (30 points)Design a finite-state machine (FSM) with input x and output y that can recognize a sequence offour ones. It should be capable of recognizing overlapping patterns of four ones; thus, for in put010111111010, the output of the machine is 000000111000.(a) Sketch a Moore state diagram for this FSM and construct the corresponding s tate table. (Hint:There are five states in a minimal realization.)(b) Convert the Moore state table to a Mealy s tate table, and reduce the number of states to fourusing row matching. Sketch the corresponding Mealy state diagram.(c) Using consecutive bits for the state assignment (i.e., 00, 01, 10, 11), derive the logic for gener-ating the next state and the output from the present state and the input. Use Q1and Q2todenote the most-significant bit and least-significant bit, respectively, of the present state.(d) Implement the Mealy sequence detector using JK flip-flops and sketch the circuit.Solution:6ECE 152ASummer 20117ECE 152ASummer 20114. CMOS AND VERILOG (15 points)Consider the following circuit:X1X2X3f(a) Sketch a CMOS circuit implementation of this function using a pull-up/pull-down network.(b) Using an always block and case statements, write a Verilog m odule that implements thiscircuit.Solution:8ECE 152ASummer