Your Name: _______________________________________Final Examination Page 1 of 10 CS 150 - Sp. 97BERKELEY • DAVIS • IRVINE • LOS ANGELES • RIVERSIDE • SAN DIEGO • SAN FRANCISCOUNIVERSITY OF CALIFORNIA AT BERKELEYSANTA BARBARA • SANTA CRUZDepartment of Electrical Engineeringand Computer SciencesCS 150 - Spring 1997Prof. A. R. NewtonFinal Examination(Open Katz, Calculators OK, 3 hours)Include all final answers in locations indicated on these pages. Use space provided for all working. If necessary, attachadditional sheets by staple at the end. State all assumptions made.BE SURE TO WRITE YOUR NAME ON EVERY SHEET.(1) (20pts)(a) Realize the following circuit using OR gates in the first stage and AND gates in the second stage.Do not use any other gates (no inverters) and assume complements are not available.(b) Write the output f of the circuit shown below in terms of A and B in as compact a form as possible.1(a) (5pts) Schematic diagram:1(b) (5pts)f = _______________________(1)/20(2) /20(3) /20(4) /20(5) /20TOTAL/100CS 150 - Sp. 97 Page 2 of 10 Final Examination1 (c) Reduce the following circuit to obtain the most compact (minimum number of gates+gate inputs)form. Use only simple gates (AND, NAND, NOR, OR, inverter, XOR, XNOR).(d) A four-bit binary number {A,B,C,D}, where A is the most significant digit and D the least significantdigit, appears on the input to a combinational logic circuit. Output X indicates whether the number isdivisible by 2 without any remainder and output Y indicates if the number is divisible by 3 withoutremainder. Obtain the sum-of-products logic equations for X and Y with the minimum number ofliterals.1(c) (5pts) Schematic:1(d) (5pts)X = _______________________Y = _______________________Additional Space for Problem 1ABCD0001111000011110 ABCD0001111000011110Your Name: _______________________________________Final Examination Page 3 of 10 CS 150 - Sp. 97(2) (20pts)(a) Consider the following state transition graph. Use an implication table to eliminate any redundantstates. List all equivalent states. Show your final result as a state transition graph.2(a) (10pts)Equivalent states: ______________________________________________________________________________________________________________________________________________________________Reduced STG:Additional space for problem 2(a)CS 150 - Sp. 97 Page 4 of 10 Final Examination(b) Consider the following reduced state table. For the state assignment A={00}, C={01}, D={11} and E= {10}, implement the machine using JK flip-flops and logic gates only. Show your flip-flopexcitation and output K-maps, the flip-flop input excitation equations, the output equation, and aschematic diagram for the final implementation using as few simple logic gates as possible.2(b) (10 pts)(i) Excitation and output K-maps:(ii) Flip-flop input excitation equations and output equation:_______________________________________ _________________________________________________________________________________ _________________________________________________________________________________ __________________________________________(iii) Schematic diagram:Your Name: _______________________________________Final Examination Page 5 of 10 CS 150 - Sp. 97 (3) (20pts)A one-bit shifter is defined as follows:======+−01,01,1 y 11sifxsdifxsdifx(a) Obtain an implementation of the one-bit shifter using a single 4-input, 2 select line MUX only.(b) Show how it would be possible to build an n-bit shifter (shift each bit of an n-bit word {x0, x1, …, xn-1}one bit position up or down) using a number of your one-bit shifters from part (a) above.3 (a) (5pts) One-bit shifter:3(b) (5pts) n-bit shifter:CS 150 - Sp. 97 Page 6 of 10 Final Examination(3) (continued) Consider the function: f(A,B,C,D) = Σm(3,4,8,9,10,13,14,15)(c) Implement this function using a single 4-input, 2 select line MUX and as few additional gates aspossible. Assume complements are not available.(d) Implement the function using a minimum number of 2-input, 1 select line MUX's and a single 4-input, 2select line MUX only (no additional logic gates). Assume complements are available.3(c) (5pts) Schematic:3(d) (5pts) Schematic:ABCD0001111000011110Your Name: _______________________________________Final Examination Page 7 of 10 CS 150 - Sp. 97(4) (20pts)(a) Show a merger diagram for the primitive flow table shown at right. Show themerged flow table for the design.4(a) (10pts) Merger Diagram:Merged flow table:Additional space for Problem 4(a)CS 150 - Sp. 97 Page 8 of 10 Final Examination(b) Obtain a race-free state assignment for the merged flow table shown below. You are to assign thecodes for the two unassigned states and you may not use any additional states to implement the race-free assignment. Show your solution by filling in all fields (including a glitch-free output assignment forZ) on the empty table shown below.4(b) (10pts) Final merged flow table and state assignment:Additional space for Problem 4(b)Your Name: _______________________________________Final Examination Page 9 of 10 CS 150 - Sp. 97(5) (a) Design a counter which produces the following binary sequence: 0, 1, 3, 7, 6, 4 and then repeats.Use three clocked T flip-flops and logic gates only. Use a minimum number of additional logic gates. (b) How would you use a ROM to perform the addition of two four-bit 2's-complement numbers?How many address lines would be required? How many data lines? Show the binary values thatwould be applied to the address lines and observed on the data lines of the ROM when performingthe following computations:(i) (+1) + (+2) (ii) (-1) + (+1) (iii) (+7) + (+6) (iv) (-6) + (-1)5(a) (14pts) T flip-flop input equations:T1 = ___________________ T2 = ______________________ T3 = ______________________5(b) (6pts)Address lines: ______________ Data lines: ______________ADDRESS BITS DATA OUTPUT(i) _________________ ________________(ii) _________________ ________________(iii) _________________ ________________(iv) _________________ ________________Additional Space for Problem 5CS 150 - Sp. 97 Page 10 of 10 Final ExaminationAdditional Space for Working
View Full Document
Unlocking...