Level 5 — MasterySequential Circuits

Sequential Circuits

⏱ 90 minutes60 marksprintable — key stays hidden on paper

Subject: Hardware · Chapter: Sequential Circuits Time limit: 90 minutes · Total marks: 60 Instructions: Answer all questions. Show all derivations. Use $...$ / $...$ notation for mathematics. Justify every claim.

Question 1 — Timing Closure Across a Clock Domain (24 marks)

A synchronous pipeline stage uses edge-triggered D flip-flops. The following device and interconnect parameters are given:

Clock-to-Q delay: $t_{cq} \in [0.20, 0.45]$ ns (min, max)
Setup time: $t_{su} = 0.15$ ns
Hold time: $t_{h} = 0.10$ ns
Combinational logic delay between two registers: $t_{logic} \in [0.30, 1.10]$ ns (min, max)
Clock skew (launch clock relative to capture clock): $t_{skew}$ (signed; positive means the capture edge arrives later)
Clock period: $T$

(a) Derive, from first principles, the general setup constraint and hold constraint inequalities for a register-to-register path including a signed skew term $t_{skew}$ . State clearly which of $t_{cq,min}$ / $t_{cq,max}$ and $t_{logic,min}$ / $t_{logic,max}$ appears in each. (6 marks)

(b) With $t_{skew} = 0$ , compute the minimum clock period $T_{min}$ and the corresponding maximum frequency $f_{max}$ in GHz. (4 marks)

(c) The design must hit $f = 1.0$ GHz. Determine the range of skew $t_{skew}$ that simultaneously satisfies both setup and hold at this frequency. State the tightest bound and which constraint sets it. (6 marks)

(d) Peak-to-peak clock jitter of $t_{jitter} = 0.08$ ns is now added. Explain how jitter modifies the setup constraint (but not the hold constraint in the usual worst case), and recompute the allowable positive-skew margin for setup at $f = 1.0$ GHz. (4 marks)

(e) A colleague proposes deliberately introducing $+0.20$ ns of skew ("useful skew") to borrow time. Prove whether this is safe here, and explain the fundamental trade-off between the setup and hold budgets that useful skew exploits. (4 marks)

Question 2 — FSM Design, Minimization & Encoding (22 marks)

Design a Mealy finite state machine that outputs $z=1$ whenever the serial input bit-stream $x$ (MSB-first, one bit per clock) has matched the pattern 1011, with overlapping allowed.

(a) Draw the state diagram and construct the full state table (states, next-state, output on each input). Use symbolic state names. (7 marks)

(b) Apply a formal state-minimization technique (implication chart or partition refinement). Prove whether your machine is already minimal, or produce the reduced machine and justify each merge. (6 marks)

(c) Choose a state encoding and derive the next-state Boolean equations for each flip-flop using D flip-flops. Show the excitation logic for at least one state bit fully via a Karnaugh map. (6 marks)

(d) Convert the output logic to an equivalent Moore machine's requirement: explain precisely why the Moore version needs at least one extra state, and give the minimum state count for the Moore equivalent. (3 marks)

Question 3 — Metastability, Synchronizers & MTBF (14 marks)

A single asynchronous signal crosses into a domain clocked at $f_{clk} = 500$ MHz. The asynchronous event rate is $f_{data} = 2.0$ MHz. The flip-flop metastability parameters are $\tau = 20$ ps and $T_0 = 1.5$ ps.

(a) State the standard MTBF formula for a synchronizer with resolution time window $t_r$ , defining every symbol. (3 marks)

(b) For a single flip-flop synchronizer, the available resolution time is $t_r = T - t_{cq} - t_{su}$ with $t_{cq}=0.10$ ns and $t_{su}=0.05$ ns. Compute $t_r$ and the resulting MTBF (in seconds and years). (5 marks)

(c) A two-flip-flop synchronizer roughly adds a full clock period to the resolution time. Recompute the MTBF and comment quantitatively on the improvement factor. (4 marks)

(d) State one reason why simply adding more synchronizer stages does not scale MTBF indefinitely in practice. (2 marks)

Answer keyMark scheme & solutions

Question 1

(a) Constraint derivation (6 marks)

Let the launch edge occur at $t=0$ and the capture edge (of the next register) at $t = T + t_{skew}$ (positive skew ⇒ capture later). (1)

Data becomes valid at the capture FF's D input at, at latest, $t_{cq,max} + t_{logic,max}$ . For a valid setup it must be stable $t_{su}$ before the capture edge:

$t_{cq,max} + t_{logic,max} + t_{su} \le T + t_{skew} \quad\text{(Setup)}$ (2, uses max values)

Hold: data from the new launch must not race through and corrupt the capture FF before it has held the old value $t_h$ past its edge. Earliest new data arrival is $t_{cq,min} + t_{logic,min}$ , capture edge (same-index) at $t = t_{skew}$ :

$t_{cq,min} + t_{logic,min} \ge t_h + t_{skew} \quad\text{(Hold)}$ (2, uses min values; note hold is period-independent)

Setup uses max $t_{cq}$ and max $t_{logic}$ ; hold uses min $t_{cq}$ and min $t_{logic}$ . (1)

(b) $T_{min}$ , $f_{max}$ (4 marks)

With $t_{skew}=0$ : $T_{min} = t_{cq,max} + t_{logic,max} + t_{su} = 0.45 + 1.10 + 0.15 = 1.70\text{ ns}$ (3) $f_{max} = 1/1.70\text{ ns} = 0.588\text{ GHz}$ (1)

(c) Skew range at $f = 1.0$ GHz (6 marks)

Here $T = 1.0$ ns.

Setup: $t_{skew} \ge t_{cq,max}+t_{logic,max}+t_{su} - T = 1.70 - 1.00 = 0.70$ ns. So setup requires $t_{skew} \ge +0.70$ ns. (2)

Hold: $t_{skew} \le t_{cq,min}+t_{logic,min}-t_h = 0.20+0.30-0.10 = 0.40$ ns. (2)

Combined requirement: $0.70 \le t_{skew} \le 0.40$ — infeasible (empty set). (1) The setup constraint is the binding one; at 1.0 GHz the path is impossible to close for any skew because the logic is simply too slow ( $T_{min}=1.70$ ns $> 1.0$ ns). (1)

(d) Jitter (4 marks)

Jitter shortens the effective period seen by setup in the worst case (launch edge late, capture edge early), so subtract jitter from the RHS: $t_{cq,max}+t_{logic,max}+t_{su} \le T - t_{jitter} + t_{skew}$ (2) Hold compares two edges of the same clock event region and in the standard worst-case model is not degraded by cycle-to-cycle jitter (it is intra-cycle), so it is left unchanged. (1) Setup margin at 1.0 GHz: needed $t_{skew} \ge 1.70 - 1.00 + 0.08 = 0.78$ ns — even worse than (c). (1)

(e) Useful skew (4 marks)

Useful skew of $+0.20$ ns: check hold — need $t_{skew} \le 0.40$ ns, and $0.20 \le 0.40$ ✓ hold still safe. (2) Setup gains $0.20$ ns of borrowed time. Fundamental trade-off: every unit of positive skew added to help setup is subtracted from the hold budget (positive skew appears with $+$ in setup RHS but as a tightening $+t_{skew}$ term in the hold RHS). Skew borrows from the hold margin to fund the setup margin; the total is conserved. Here hold has $0.40$ ns slack, so up to $+0.40$ ns skew is hold-safe, but even max skew cannot close setup at 1.0 GHz. (2)

Question 2

(a) State diagram / table (7 marks)

Pattern 1011, overlapping. Mealy states track the longest matched prefix:

$S_0$ : no useful prefix
$S_1$ : matched 1
$S_2$ : matched 10
$S_3$ : matched 101

Match completes on the 4th bit while in $S_3$ receiving 1 ⇒ $z=1$ ; then overlap keeps us in $S_1$ (the last 1 starts a new 1). (2 for correct prefix analysis)

State table (next state / output for input 0, input 1): (4)

State	x=0 → next / z	x=1 → next / z
$S_0$	$S_0$ / 0	$S_1$ / 0
$S_1$	$S_2$ / 0	$S_1$ / 0
$S_2$	$S_0$ / 0	$S_3$ / 0
$S_3$	$S_2$ / 0	$S_1$ / 1

Rationale on key transitions: from $S_2$ (10) on 0 → prefix 100, longest suffix that is a prefix of pattern is empty → $S_0$ ; on 1 → 101 → $S_3$ . From $S_3$ (101) on 1 → 1011 match, output 1, remaining suffix 1 → $S_1$ ; on 0 → 1010, longest matching suffix 10 → $S_2$ . (1)

(b) Minimization (6 marks)

Partition refinement. Initial partition by output behavior. Only $S_3$ produces $z=1$ (on input 1). So group $P_0=\{S_3\}$ , $P_1=\{S_0,S_1,S_2\}$ (never output 1). (1)

Refine $P_1$ by next-state groupings:

$S_0$ : (x0→ $S_0\in P_1$ , x1→ $S_1\in P_1$ )
$S_1$ : (x0→ $S_2\in P_1$ , x1→ $S_1\in P_1$ )
$S_2$ : (x0→ $S_0\in P_1$ , x1→ $S_3\in P_0$ )

$S_2$ differs (goes to $P_0$ on x=1) → split $\{S_2\}$ out. $S_0,S_1$ both map into $P_1$ on both inputs but must check destination sub-groups. (2)

New partition: $\{S_3\},\{S_2\},\{S_0,S_1\}$ ? Check $S_0$ vs $S_1$ : $S_0$ x0→ $S_0$ (same group), $S_1$ x0→ $S_2$ (different group). They differ ⇒ split. (2)

Final partition: $\{S_0\},\{S_1\},\{S_2\},\{S_3\}$ — all singletons ⇒ machine is already minimal (4 states). (1)

(c) Encoding & D equations (6 marks)

Encode: $S_0=00,\ S_1=01,\ S_2=10,\ S_3=11$ with state bits $(Q_1 Q_0)$ . (1)

Next-state $(D_1 D_0)$ table:

$Q_1Q_0$	x	next $Q_1Q_0$	z
00	0	00	0
00	1	01	0
01	0	10	0
01	1	01	0
10	0	00	0
10	1	11	0
11	0	10	0
11	1	01	1

$z = Q_1 Q_0 x$ . (1)

K-map for $D_0$ (=next $Q_0$ ), over $(Q_1,Q_0,x)$ : minterms where next $Q_0=1$ : rows 00/1(=001→ $D_0=1$ ), 01/1(011), 10/1(101), 11/1(111). All are $x=1$ rows except also 00/1 etc. Reading: $D_0=1$ exactly when $x=1$ for states 00,01,10,11 EXCEPT verify 10/1 gives next 11 ( $Q_0=1$ )✓, 11/1 gives 01 ( $Q_0=1$ )✓. And $x=0$ rows: 01/0→10 ( $Q_0=0$ ), 11/0→10 ( $Q_0=0$ ). So $D_0 = x$ . (3, full K-map shown)

$D_1$ : next $Q_1=1$ for rows 01/0(→10), 10/1(→11), 11/0(→10). ⇒ $D_1 = Q_0\bar{x} + Q_1 x$ … check 11/0: $Q_0\bar x =1$ ✓; 10/1: $Q_1 x=1$ ✓; 01/0: $Q_0\bar x=1$ ✓; ensure no false: 00 rows give 0 ✓, 01/1→01 ( $Q_1=0$ ): $Q_1x=0,Q_0\bar x=0$ ✓. So $D_1 = Q_0\bar{x} + Q_1 x,\quad D_0 = x,\quad z = Q_1 Q_0 x.$ (1)

(d) Moore equivalent (3 marks)

A Moore machine's output depends only on the current state, so the "match" cannot be signalled while reading the final 1 in $S_3$ ; instead a dedicated accepting state must be entered after the match, whose output is 1. This adds one extra state ( $S_4$ , output 1, behaving like $S_1$ for further transitions). (2) Minimum Moore state count = 5. (1)

Question 3

(a) MTBF formula (3 marks)

$\text{MTBF} = \frac{e^{\,t_r/\tau}}{T_0\, f_{clk}\, f_{data}}$ where $t_r$ = available resolution/settling time, $\tau$ = metastability regeneration time constant, $T_0$ = characteristic window constant, $f_{clk}$ = sampling clock rate, $f_{data}$ = asynchronous transition rate. (3)

(b) Single FF (5 marks)

$T = 1/500\text{ MHz} = 2.0$ ns. $t_r = 2.0 - 0.10 - 0.05 = 1.85$ ns. (2) $t_r/\tau = 1.85\text{ns}/0.020\text{ns} = 92.5$ . $e^{92.5} \approx 1.49\times10^{40}$ . (1) Denominator: $T_0 f_{clk} f_{data} = 1.5\times10^{-12}\times5\times10^{8}\times2\times10^{6} = 1.5\times10^{3}$ . (1) $\text{MTBF} = 1.49\times10^{40}/1.5\times10^{3} \approx 9.9\times10^{36}\text{ s} \approx 3.1\times10^{29}\text{ years}.$ (1)

(Note: even a single stage here is astronomically safe because $t_r/\tau$ is huge; graders accept the method with correct magnitude.)

(c) Two FF (4 marks)

Two-FF adds ~ $T = 2.0$ ns: $t_r \approx 1.85 + 2.0 = 3.85$ ns. $t_r/\tau = 192.5$ . (2) Improvement factor $= e^{(3.85-1.85)/0.020} = e^{100} \approx 2.7\times10^{43}$ . MTBF $\approx 9.9\times10^{36}\times2.7\times10^{43} \approx 2.7\times10^{80}$ s. (2) The improvement is multiplicative and enormous — each added clock period of resolution multiplies MTBF by $e^{T/\tau}$ .

(d) Scaling limit (2 marks)

Each added stage costs a full clock period of latency, and eventually routing/hold constraints, jitter, and finite $T_0$ /temperature variation dominate; also the marginal MTBF is already vastly beyond system lifetime