Shift Registers, FSMs (Mealy/Moore) & Setup/Hold Time Timing Analysis
“Mealy vs Moore machines, setup and hold slack inequalities, clock skew hazards, and metastabiliy.”
1.State Machines and Dynamic Timing Closures
§ 5.1.Finite State Machines (FSM): Every synchronous sequential system can be formalized as an FSM characterized by present states, inputs, next states, and outputs.
- Moore Model: Output is associated exclusively with the state node. In state transition graphs, outputs are written inside the state circle (S_0 / 0). Outputs change strictly synchronously with clock edges.
- Mealy Model: Output is associated with the transition edge (a / 0: input a produces output 0). An input transition can immediately perturb the output combinationally between clock edges.
Static Timing Analysis (STA):
Real digital gates do not switch instantaneously. Reliable data transfer between two communicating flip-flops (launching flip-flop FF_1 and capturing flip-flop FF_2) requires satisfying two independent timing inequalities:
1. Setup Time (t_{setup}): Data launched by FF_1 on clock edge 1 must propagate through clock-to-Q delay t_{cq} and combinational logic t_{comb} and settle at FF_2's input at least t_{setup} nanoseconds before clock edge 2 arrives: T_{clk} ≥ t_{cq} + t_{comb} + t_{setup} - t_{skew}.
2. Hold Time (t_{hold}): New data launched by FF_1 on clock edge 2 must not arrive at FF_2 too quickly before FF_2 has finished capturing the old data: t_{cq(min)} + t_{comb(min)} ≥ t_{hold} + t_{skew}.
2. Worked Analysis: Maximum Clock Frequency and Hold Slack Calculation
Pay close attention to whether clock skew is positive (destination clock arrives later) or negative (destination clock arrives earlier).
Problem Statement (Modeled on GATE Pattern):
A digital synchronous datapath has two flip-flops communicating through a combinational multiplier.
Given parameters:
- Clock-to-Q delay: t_cq(max) = 2.5 ns, t_cq(min) = 1.2 ns
- Combinational path delay: t_comb(max) = 8.0 ns, t_comb(min) = 2.0 ns
- Setup time: t_setup = 1.5 ns
- Hold time: t_hold = 1.0 ns
- Clock skew: t_skew = 0.5 ns (destination clock delayed)
Calculate: (a) The minimum clock period T_clk and maximum clock frequency f_max, and (b) The hold slack.
Step 1: Apply Setup Time Inequality for T_clk:
Formula: T_clk >= t_cq(max) + t_comb(max) + t_setup - t_skew
T_clk >= 2.5 ns + 8.0 ns + 1.5 ns - 0.5 ns
T_clk >= 11.5 ns.
Minimum clock period T_clk(min) = 11.5 ns.
Maximum frequency f_max = 1 / 11.5 ns = 1 / (11.5 * 10^-9 s) ≈ 86.96 MHz.
Step 2: Check Hold Time Constraint:
Formula: t_{data_arrival(min)} >= t_{data_required}
t_cq(min) + t_comb(min) >= t_hold + t_skew
LHS = 1.2 ns + 2.0 ns = 3.2 ns.
RHS = 1.0 ns + 0.5 ns = 1.5 ns.
Hold Slack = LHS - RHS = 3.2 ns - 1.5 ns = +1.7 ns.
Conclusion: Hold slack is positive (+1.7 ns), meaning no hold violation exists. Maximum clock frequency is 86.96 MHz.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
The most thorough digital logic series — textbook quality at no cost.
GATE-focused digital logic with exam-style numericals.