Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Sequential Logic Theory

Field: Logic Design

Sequence of Expressions

Let SS be the finite set of states, S=QS = Q. Define the input alphabet Σ\Sigma. The system behavior is defined by the transition function δ:Q×Σ→Q\delta: Q \times \Sigma \to Q. A transition from state qiq_i to qjq_j upon input xx is represented by the tuple (qi,x,qj)(q_i, x, q_j), such that qj=δ(qi,x)q_j = \delta(q_i, x). The system state at time t+1t+1 is Q(t+1)=δ(Q(t),X(t))Q(t+1) = \delta(Q(t), X(t)).
Let Q(t)Q(t) be the current state vector and X(t)X(t) be the input vector. The next state Q(t+1)Q(t+1) is determined by the Boolean function ff: Q(t+1)=f(Q(t),X(t))Q(t+1) = f(Q(t), X(t)) where f:Bn×Bm→Bnf: B^n \times B^m \to B^n. For a specific flip-flop type (e.g., JK), the characteristic equation defines the next state QnextQ_{next} based on the current state QQ and inputs XX: Qnext=f(Q,X)Q_{next} = f(Q, X).
The JK flip-flop uses two cascaded latches (Master and Slave) controlled by a clock signal CLK\text{CLK}. The Master latch captures the input JJ and KK when CLK=1\text{CLK}=1. The Slave latch updates the output QnextQ_{next} when CLK\text{CLK} transitions from 1 to 0. The next state QnextQ_{next} is governed by the input JJ and KK and the current state QQ: Qnext=JQ‾+K‾QQ_{next} = J \overline{Q} + \overline{K} Q This structure ensures that the output only changes on the active edge of the clock signal.
A Mealy machine is defined by a tuple (Q,Σ,Q′,δ,λ)(Q, \Sigma, Q', \delta, \lambda), where QQ is the state set, Σ\Sigma is the input alphabet, Q′Q' is the output alphabet, δ:Q×Σ→Q\delta: Q \times \Sigma \to Q is the state transition function, and λ:Q×Σ→Q′\lambda: Q \times \Sigma \to Q' is the output function. The output YY depends on both the current state QQ and the current input XX: Y(t)=λ(Q(t),X(t))Y(t) = \lambda(Q(t), X(t))
A Moore machine is defined by a tuple (Q,Σ,Q′,δ,λ)(Q, \Sigma, Q', \delta, \lambda), where QQ is the state set, Σ\Sigma is the input alphabet, Q′Q' is the output alphabet, δ:Q×Σ→Q\delta: Q \times \Sigma \to Q is the state transition function, and λ:Q→Q′\lambda: Q \to Q' is the output function. The output YY depends solely on the current state QQ: Y(t)=λ(Q(t))Y(t) = \lambda(Q(t))
Given a current state QQ and a desired next state QnextQ_{next}, the required input excitation XX must satisfy the Boolean equations derived from the state transition logic. The excitation table determines XX such that Qnext=f(Q,X)Q_{next} = f(Q, X). For a specific flip-flop, the required input XX is derived by solving the characteristic equation for XX: X=f−1(Qnext,Q)X = f^{-1}(Q_{next}, Q) This process systematically maps (Q,Qnext)→X(Q, Q_{next}) \to X.
When a signal SS crosses from a domain clocked by CLK1\text{CLK}_1 to a domain clocked by CLK2\text{CLK}_2, a synchronizer is required. The standard two-flip-flop synchronizer uses the following structure: Ssync,1=D (on CLK2 edge)S_{sync, 1} = D \text{ (on } \text{CLK}_2 \text{ edge)} and Ssync,2=D (on CLK2 edge)S_{sync, 2} = D \text{ (on } \text{CLK}_2 \text{ edge)}. The output SoutS_{out} is taken from Ssync,2S_{sync, 2}. This structure mitigates metastability by allowing the signal to settle over two clock cycles.
A race condition occurs when the circuit output depends on the non-deterministic order of signal arrival. Formally, if the circuit behavior OO is modeled by a set of differential equations V˙=g(V,t)\dot{\mathbf{V}} = g(\mathbf{V}, t), a race condition implies that the solution V(t)\mathbf{V}(t) is not unique or stable with respect to the timing delays τi\tau_i. Mitigation requires ensuring that all state updates are synchronized to a common clock edge, enforcing a deterministic transition function δ\delta.
Synchronous circuits operate under a global clock signal CLK\text{CLK}, where all state updates occur simultaneously at the clock edge: Q(t+1)=f(Q(t),X(t),CLK)Q(t+1) = f(Q(t), X(t), \text{CLK}). Asynchronous circuits rely on handshaking protocols, where state transitions are triggered by local completion signals (e.g., Request\text{Request} and Acknowledge\text{Acknowledge}). The transition is governed by the logical AND of completion signals, Q(t+1)=f(Q(t),X(t))⋅(Req∧Ack)Q(t+1) = f(Q(t), X(t)) \cdot (\text{Req} \land \text{Ack}).
Circuit minimization aims to find the minimal Boolean function fminf_{min} equivalent to the original function ff. For sequential logic, this involves minimizing both the next-state function fnext(Q,X)f_{next}(Q, X) and the output function Y(Q,X)Y(Q, X). Methods like the Quine-McCluskey algorithm systematically identify prime implicants (PIs) that cover the required minterms, ensuring that the resulting simplified expression fminf_{min} maintains logical equivalence: fmin=⋁iMif_{min} = \bigvee_{i} M_i where MiM_i are the selected prime implicants.