Sequential Logic — D Flip-Flops & Finite State Machines

Sequential Logic — D Flip-Flops & Finite State Machines

1. D Flip-Flop — Timing Model

Key timing parameters for the D flip-flop:

• $t_{su}$ — Setup time: D must be stable for at least $t_{su}$ before the clock edge.
• $t_h$ — Hold time: D must remain stable for at least $t_h$ after the clock edge.
• $t_{clk-to-Q}$ — Propagation delay from clock edge to Q output.

Maximum clock frequency of a synchronous pipeline (flip-flop → combinational logic → flip-flop):

$$f_{max} = \frac{1}{t_{clk-to-Q} + t_{combo,max} + t_{su}}$$

Hold time violation: if $t_{clk-to-Q} + t_{combo,min} < t_h$, a hold violation occurs (independent of clock frequency — cannot be fixed by slowing the clock).

2. Moore and Mealy FSMs

A finite state machine is defined by the 5-tuple $(Q, \Sigma, \delta, q_0, \Lambda)$:

• $Q$ — finite set of states
• $\Sigma$ — input alphabet
• $\delta: Q \times \Sigma \to Q$ — next-state function
• $q_0$ — initial state
• $\Lambda$ — output function

Moore: outputs depend only on current state. Mealy: outputs depend on current state AND current input. Mealy machines typically require fewer states but their outputs can glitch asynchronously with the input — undesirable in many digital systems.

3. State Encoding & Synthesis

Binary encoding ($\lceil \log_2 |Q| \rceil$ bits) minimises flip-flops; one-hot encoding ($|Q|$ flip-flops, one per state) simplifies next-state logic. For a binary-encoded $n$-state FSM with $k = \lceil \log_2 n \rceil$ state bits, the next-state logic is a combinational circuit of $k$ outputs; each is expressed in terms of current state and input using K-maps.

D flip-flop excitation equation: $D_i = \delta_i(Q, X)$ — the next state bit equals the D input. For JK flip-flops: $J_i = \delta_i \cdot \bar{Q}_i + \delta_i Q_i$... actually $J_i = \delta_i$ when $Q_i = 0$; $K_i = \bar{\delta}_i$ when $Q_i = 1$ (use excitation table).

4. Metastability & Clock Domain Crossing

When a D flip-flop samples a signal that changes within the setup/hold window, the output may enter a metastable state that resolves to 0 or 1 with exponential probability:

$$P(\text{metastable at time } t) = \frac{T_w}{T_{clk}} e^{-t/\tau}$$

where $T_w$ is the metastability window, $T_{clk}$ is the clock period, and $\tau \approx 0.1{-}1$ ns for modern FPGAs. Mean time between failures:

$$\text{MTBF} = \frac{T_{clk}}{f_{data} T_w} e^{t_{resolve}/\tau}$$

Two-stage synchroniser (two cascaded D flip-flops) increases $t_{resolve}$ by one clock period, exponentially improving MTBF. Xilinx UG901 recommends registered synchronisers for all asynchronous inputs in FPGA designs.