CS ECE 252 INTRODUCTION TO COMPUTER ENGINEERING COMPUTER SCIENCES DEPARTMENT UNIVERSITY OF WISCONSIN MADISON Prof Mark D Hill Prof Mikko Lipasti TAs Sanghamitra Roy Eric Hill Samuel Javner Natalie Enright Jerger Guoliang Jin Midterm Examination 2 In Class 50 minutes Friday October 26 2007 Weight 15 CLOSED BOOK NOTE CALCULATOR PHONE COMPUTER The exam is two sided and has 11 pages including two blank pages at the end Plan your time carefully since some problems are longer than others NAME SECTION ID 1 2 Problem Number Maximum Points 1 3 2 3 4 5 6 4 3 2 3 4 7 3 8 4 9 4 Total 30 Actual Points Problem 1 3 points Write the Boolean expression corresponding to the following truth table You need not simplify the expression Inputs Output A B C Z 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 Problem 2 4 points Suppose a 32 bit instruction takes the following format OPCODE DR SR1 SR2 UNUSED If 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 3 Problem 3 3 points The figure below shows a combinational logic circuit Complete the truth table corresponding to this circuit Inputs 4 Output A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Z Problem 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 5 Problem 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 6 Output A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Z Problem 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 7 Problem 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 are accepted 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 8 Problem 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 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 a 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 Doubles b Remains unchanged c Halves d Increases by 2 address bits addressability III The minimum number of transistors required to implement a CMOS 3 input OR gate is 4 b 6 c 8 d 10 a IV The Decode phase of the Instruction Cycle always examines which part of the instruction Immediate literal value b Opcode c Offset d Register a 9 Scratch Sheet 1 in case you need additional space for some of your answers 10 Scratch Sheet 2 in case you need additional space for some of your answers 11