1CS/ECE 252: INTRODUCTION TO COMPUTER ENGINEERINGCOMPUTER SCIENCES DEPARTMENTUNIVERSITY OF WISCONSIN-MADISONProf. Mark D. Hill & Prof. Mikko LipastiTAs Sanghamitra Roy, Eric Hill, Samuel Javner, Natalie Enright Jerger & Guoliang JinMidterm Examination 2In Class (50 minutes)Friday, October 26, 2007Weight: 15%CLOSED BOOK, NOTE, CALCULATOR, PHONE, & COMPUTER.The exam is two-sided and has 11pages, including two blank pages at the end.Plan your time carefully, since some problems are longer than others.NAME: __________________________________________________________SECTION: __________________________________________________________ID# ______________________________________________________________2ProblemNumberMaximumPointsActualPoints1 32 43 34 25 36 47 38 49 4Total 303Problem 1 (3 points)Write the Boolean expression corresponding to the following truth table. You need not simplify the expression. InputsOutputA B C Z0 0 0 10 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 11 1 1 0Problem 2 (4 points)Suppose a 32-bit instruction takes the following format:OPCODE DR SR1 SR2 UNUSEDIf there are 225 opcodes and 120 registers:a) What is the minimum number of bits required to represent the OPCODE?b) What is the minimum number of bits required to represent the destination register DR, and source registers SR1 and SR2? (Give the total number of bits.)c) What is the maximum number of UNUSED bits in the instruction encoding?4Problem 3 (3 points)The figure below shows a combinational logic circuit. Complete the truth table corresponding to this circuit. Inputs OutputA B C Z0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 15Problem 4 (2 points)You know a byte is 8 bits. A 4-bit quantity is called a nibble. If a byte-addressable memory has a 16-bit address, how many nibbles of storage are in this memory?Problem 5 (3 points)The circuit below has a major flaw. Can you identify it? Hint: Evaluate the circuit for all sets of inputs.6Problem 6 (4 points)Fill in the truth table for the following transistor level circuit. Note that two wires with the same name are assumed to be connected to each other.Inputs OutputA B C Z0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 17Problem 7 (3 points)The figure below shows a block diagram of the Von Neumann model. List the steps in writing a value x0002 to a location x3010 in the memory. Your steps should mention the MAR and MDR where applicable. 1) ______________________________________________________________2) ______________________________________________________________3) ______________________________________________________________8Problem 8 (4 points)A Vending machine delivers a package of gum after 15 cents are deposited. It has a single coin slot which accepts only dimes (10 cents) or nickels (5 cents). (No other types of coins areaccepted). The vending machine does not return back changes.I. Draw the finite state machine diagram for the vending machine. The machine takes one input every clock cycle which can be N, D or reset. The machine outputs a 1 when it opens to deliver a gum package, otherwise it outputs a 0. II. How many flip-flops (storage elements) will be needed to implement this finite state machine designed in your answer to part I?9Problem 9 (4 points)Circle the correct answer for the following questions:I. Circuit A is a 1-bit adder calculating the sum only and no carry; circuit B is a 1 bit multiplier. Both the circuits are implemented using AND, OR and NOT gates only. a. Circuit A has more gates than circuit B b. Circuit B has more gates than circuit A c. Circuit A has the same number of gates as circuit B (Hint: Construct the truth table for the adder and the multiplier)II. If the number of address bits in a memory is reduced by 2 and the addressability is doubled, the size of the memory (i.e., the number of bits stored in the memory) a. Doublesb. Remains unchangedc. Halvesd. Increases by 2^(address bits)/addressabilityIII. The minimum number of transistors required to implement a CMOS 3 input OR gate isa. 4b. 6c. 8d. 10IV. The Decode phase of the Instruction Cycle always examines which part of the instruction?a. Immediate (literal) valueb. Opcodec. Offsetd. Register10Scratch Sheet 1 (in case you need additional space for some of your answers)11Scratch Sheet 2 (in case you need additional space for some of your