First Name: Last Name: PID: Version A Solution Left Neighbor Right Neighbor Seat No. CSE 140 Midterm 2 Prof. Tajana Simunic Rosing Winter 2018 ● Do not start the exam until you are told. ● The examination will be graded out of 100, with 10 extra bonus points. ● Write your name and PID at the top of every page. Do not separate the pages. ● Turn off and put away all your electronics. ● This is a closed-book, closed-notes, no calculator exam. You may only refer to one 8 x 11” page of your handwritten notes. ● Do not look at anyone else’s exam. ● Do not talk to anyone but an exam proctor during the exam. If you have a question, raise your hand and an exam proctor will come to you. ● You have 80 minutes to finish the exam. When the time is finished, you must stop. ● Write your answers in the space provided. ● To get the most partial credit, clearly and neatly show all steps of your work. Problem 1 15 points Problem 2 10 points Problem 3 15 points Problem 4 25 points Problem 5 25 points Problem 6 20 points Total points 100 points + 10 bonus 1 First Name: Last Name: PID: 1. Design a pattern recognizer that outputs a 1 when it detects among 4 input bits zero or more 0s followed by zero or more 1s – 0011, 0000, and 1111 are some examples. Here is sample output of the pattern recognizer. Time -> Input: 0110001011001110100101111 Output: XXX0001000000110000000011 a. (5pts) Use a shift register to recognize the pattern. Complete the circuit using a minimum number of inverters and two-input logic gates, connected only to the Q outputs of the FFs. Assume there are no setup or hold violations. Note that values flow from left to right. 2 First Name: Last Name: PID: b. (10pts) Draw the state diagram for a Mealy FSM that recognizes the same pattern. Use as few states as possible. Or with clever trick: 3 First Name: Last Name: PID: 2. Consider the following sequential circuit with input and output. a. (8pts) Fill in the excitation table. You can assume initial state is encoded as 00. Excitation Table Q1(t) Q0(t) Input Q1(t + 1) Q0(t + 1) M 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 b. (2pts) Is this design Mealy or Moore FSM Moore 4 First Name: Last Name: PID: 3. (15pts) Complete the timing diagram for the circuit below. Assume near zero delay for all elements. Initial state of the flip flop is 0. Initial value of Y is 1 and of Z is 0. Setup, hold times and clock skew can be neglected. CLK A B E
F Y 5 First Name: Last Name: PID: 4. (25pts) Consider the following FSM diagram. a. (10pts) Assuming the following state encoding: S0 = 00, S1 = 01, S2 = 10, S3 = 11, draw the combinational circuit for the LSB of the next state, Q0(t+1), using minimal number of gates. 6 First Name: Last Name: PID: b. (6pts) Assuming the same state encoding as part (a), find the number of bit changes of transitions between the states. Complete the table below. Transition Number of bit change S0 → S1 1 S0 → S2 1 S0 → S3 2 S1 → S3 1 S2 → S0 1 S3 → S0 2 Total 8 c. (3pts) Using minimum bit change heuristics, assign the state values so that the number of bit changes is minimized during the state transitions. Complete the table below. State Encoding Encoding S0 11 11 S1 00 00 S2 10 01 S3 01 10 d. (6 pts) Assuming the state encoding in part (c), find the number of bit changes of transitions between the states. Complete the table below. Transition Number of bit changes S0 → S1 2 S0 → S2 1 S0 → S3 1 S1 → S3 1 S2 → S0 1 S3 → S0 1 Total 7 7 First Name: Last Name: PID: 5. (25pts) The following HLSM reads two eight-bit numbers, A and B, from two 10×8 register files and increments a counter if either of them is zero when a start signal is given. This process is done ten times, one time for each word in the register. The final output is provided in ResultReg. a. (9pts) There are nine missing components (states/controls) in the HLSM below. Fix what is needed so that the HLSM works correctly. 8 First Name: Last Name: PID: b. (7pts) Design the datapath for this system. c. (9pts) Connect datapath to control and show all input/outputs for both datapath and control. 9 First Name: Last Name: PID: 5. (20 pts) Answer the following questions using the data given below: Logic gate tpd tcd NOT 10ns 10ns AND 30ns 20ns OR 30ns 20ns XOR 40ns 30ns tsetup 20ns thold 35ns tccq 10ns tpcq 60ns a. Assuming tskew = 0 i. (5pts) Find the maximum clock frequency. 10 First Name: Last Name: PID: ii. (5pts) Does the circuit have a hold time violation Show your work. b. Assuming tskew = 10ns i. (5pts) What is the maximum clock frequency How does it compare to the one calculated in part a-i Show your work. ii. (5pts) Consider the modified circuit shown in figure 2, does the modified circuit have a hold time violation Show your work 11 First Name: Last Name: PID: This page is intentionally left blank. 12