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 10x8 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




































































































































































































































































学霸联盟