Q1: Answer the following questions for the circuit given below and timing parameters
provided in the table

(a) [30 Points] Does the circuit have any setup violations ? If yes, what is the magnitude
and explain where.
(b) [20 Points] What is the minimum clock period to ensure that there are no setup violations
in the circuit ?
(c) [30 Points] Does the circuit have any hold violations ? If yes, what is the magnitude and
explain where.
(d) [20 Points] If there is a hold violation in the circuit, fix the hold violation.by minimally
modifying (least number of transistors) the above circuit while ensuring that the
functionality of the circuit is undisturbed. Show how you would modify the circuit.

CSE140 Winter 2021 Homework 5
Due Feb. 25 11:59PM PST - Gradescope submission
(Grade out of 100; each problem is worth 50pts, we grade 2)
D Flop-Flop , t 10ps, t 5ps setup = hold = 6 t 50pstpcq = ccq =
NAND Gate 0ps, t 60pstcd = 4 pd =
NOR Gate 0ps, t 60pstcd = 4 pd =
XNOR Gate 0ps, t 100pstcd = 8 pd =
NOT Gate 5ps, t 30pstcd = 1 pd =
Clock , 165psT clock = 0psT skew =
Solution for Problem 1:

a)
There are two setup time violations

First one is from ff1 to ff2, which goes through a NAND gate and a NOR gate:
= 60ps+60ps = 120pst comb

Set up constraints:
t = t clock t skew tpcq + comb + tsetup < −
50ps+160ps+10ps = 180ps >= 165ps ⇒ violate set up constraints
180-165 = 15ps

Second one is from ff2 to ff1, which goes through a NAND gate and a XNOR gate.
= 60ps+100ps = 160pst comb

Set up constraints:
t = t clock t skew tpcq + comb + tsetup < −
50ps+160ps+10ps = 220ps >= 165ps ⇒ violate set up constraints
220-165 = 55ps

b)

220ps

c)
hold time violation -> find the shortest path

= 0pst comb

t = t thold + skew < ccq + tcomb

65ps > 50ps +0ps

Yes, there is a hold time violation.

d)

For the minimal modifying, the tcomb will increase 15ps in order to fix the hold time violation. →
we need to add one inverter between flip flop 2 and flip flop 3 to fix the hold time violation and
another inverter to maintain the original functionality, so adding two inverters would be sufficient.

Q2: Use the given circuit and specifications to answer the following questions. Input (X) rise and
fall times are near zero. All flip flops start with a state of 0.

a) Fill out the following timing diagram for S1, S2, S3, and Y. Each bar represents 50ps.

Clock frequency 5GHz
Flip flop ,tccq tpcq 50ps
Flip flop ,tsetup thold 10ps
NOT gate ,tcd tpd 25ps
XOR gate ,tcd tpd 50ps
AND gate ,tcd tpd 50ps

b) Are there any setup time violations? If so, show where.
No there aren’t setup time violations.

c) Are there any hold time violations? If so, show where.
Yes there are hold time violations.

Q3: FSM shown below is a 4-state pattern recognizer with one input and two outputs andx y0
. The input comes in as a binary sequence over time.y1 x

a) [10 points] For the input sequence (read from left to right), trace the11110011x = 0
outputs and . What patterns do and recognize?y0 y1 y0 y1
b) [10 points] Write the excitation table for the given FSM. The states are assigned as
and .0, S 1, S 0S0 = 0 1 = 0 2 = 1 1S3 = 1
c) [15 points] Implement the given FSM using 2 D-Flip Flops to store the state and
minimum number of other gates. Draw K-Maps for both outputs and the stored states,
and obtain their minimized logic equations using SOP form.
d) [15 points] Draw the circuit for this FSM using a minimum number of transistors (use
NAND/NOR/NOT gates only).

Solution:

a) 000110000y0 =
001000001y1 =
detects the sequence y0 111’‘
detects the sequence . At the start of an input, it will also detect the sequencey1 011’‘
.11’‘

b) The current state is represented by: sS = s1 0
Let’s assume that the input for the next state bits is represented as and .d1 d0

c) The K-Maps for the 2 state variables and 2 outputs are:
s1 s0 x y0 y1 d1 d0
0 0 0 0 0 0 0
0 0 1 0 0 0 1
0 1 0 0 0 0 0
0 1 1 0 0 1 0
1 0 0 0 1 0 0
1 0 1 0 1 1 1
1 1 0 1 0 0 0
1 1 1 1 0 1 1

x x s )x (s ) )d1 = s1 + s0 = ( 0 + s1 = ( 0 + s1 ′ + x′ ′
x x s )x s ) )d0 = s1 + s0′ = ( 0′ + s1 = ( 0′ + s1 ′ + x′ ′
s s )y0 = s1 0 = ( 0′ + s1′ ′
s s )y1 = s1 0′ = ( 0 + s1′ ′
d) The circuit for the FSM is:

Q4. A car manufacturer wants to implement an automatic gear shifting system. The car has a
speedometer that operates in units of 1mph. The speedometer is provided as an output for the
driver. Assume that the speedometer is initialized to 0 at the start.
● If the speed is less than 75mph the gearbox moves to LOW gear. For speeds more than
75mph the gearbox shifts to HIGH gear.
● An indicator light is provided in the system which turns on if the gear is in high and off when
the gear is in low.
● When the brakes are applied, the speed needs to be decremented and when accelerating
the speed needs to be incremented. You may assume that there is 1 bit which is 1 for
acceleration and 0 for breaking.

Given the specification above, do the following:
a. Draw the HLSM for the above system
b. Draw and label all of the components, inputs and outputs of the datapath
c. Connect the datapath to control
d. Draw the FSM for the control using only binary signals.
e. Implement the FSM for the next states and the outputs of the control using minimum number
of flip-flops and minimum number of other gates

e)

Q1 Q0 s_lt_75 a Q1 Q0 L
0 0 x 1 0 1 0
0 0 x 0 1 1 0
0 1 1 x 0 0 0
0 1 0 x 1 0 1
1 0 x 1 0 1 1
1 0 x 0 1 1 1
1 1 1 x 0 0 0
1 1 0 x 1 0 1