Sequential Circuit Design and Finite State Machines

A synchronous sequential circuit combines combinational logic with edge-triggered flip-flops sharing a common clock. Its behaviour is a finite state machine (FSM): present state and inputs determine outputs and next state. Mealy machines let outputs depend on inputs and state; Moore machines let outputs depend on state only.

GATE asks you to analyse a given circuit into a state table, design sequence detectors (overlapping or not), count the states and flip-flops a machine needs, reduce a state table, and derive flip-flop input equations.

Classic: detect overlapping or non-overlapping patterns such as $1101$ on a serial input. Each state records the longest prefix of the pattern that is also a suffix of the input seen so far.

State counts for a pattern of length $n$. A minimal Mealy detector has $n$ states (prefix lengths $0$ to $n-1$); the output 1 sits on the arc that completes the pattern. A minimal Moore detector has $n+1$ states, because "just matched" must be a state of its own with output 1. For $1101$: 4 Mealy states (2 FFs) and 5 Moore states (3 FFs).

Timing difference. In this detector example, the unregistered Mealy output uses the pre-update state and current input and may assert on the final input symbol; the current-state Moore output appears after the edge entering the matching state. Calling this a one-cycle shift depends on the sampling convention. Equivalent Mealy/Moore realizations do not have a universal one-clock lag from their definitions alone.

From a schematic: write FF excitation equations, apply characteristics to get next-state maps, build the state table, draw the diagram. With D flip-flops the next state equals the D inputs; with JK or T, substitute into $Q^+ = JQ' + K'Q$ or $Q^+ = T \oplus Q$ first.

Two states are equivalent if they produce the same output sequences for every input sequence. Equivalent states can be merged without changing the behaviour seen from outside.

Partition refinement. Start with blocks of states that have the same output row. Repeatedly split a block when two of its states move, on some input, to different blocks. Stop when nothing splits; each block is one state of the minimal machine. Identical rows (same outputs and same next states) are only the easy case: two states can be equivalent even when their next states differ, as long as those next states are themselves equivalent. The implication-chart method finds the same result.

Binary encoding uses the fewest FFs. Gray-adjacent codes for states that transition into each other can reduce logic and avoid some simultaneous bit flips. One-hot encoding uses one FF per state: the next-state logic is simple, but the FF count equals the state count. Unused codes (for example 1 of 4 codes when 3 states use 2 FFs) may be treated as don't-cares in the excitation maps, or given a transition back into the used states so that the machine cannot stay stuck there after a glitch.

Arrays and states are 0-indexed; <- is assignment.

REDUCE does $O(s \cdot |\Sigma|)$ work per round with hashing, for $s$ states.

A deterministic FSM is $(Q,\Sigma,\delta,q_0,\Lambda)$ with output function $\Lambda$ either $Q\to\Gamma$ (Moore) or $Q\times\Sigma\to\Gamma$ (Mealy). Encoding injects $Q$ into $\{0,1\}^k$, so $k \ge \lceil \lg |Q| \rceil$. Related TOC view: Deterministic Finite Automata omits binary encoding and gates.

Why the Mealy detector needs exactly $n$ states. The prefix states $0, 1, \ldots, n-1$ are pairwise distinguishable. For $i < j$, feed the $n - j$ bits $P[j..n-1]$. From state $j$ the last of them completes a match. From state $i$ the matched prefix can reach at most $i + n - j < n$, so there is no match. Fewer than $n$ states would merge two of them.

States $A$ (no progress), $B$ (last bit 1). From $A$: input 0 to $A$ out 0; input 1 to $B$ out 0. From $B$: input 1 to $B$ out 1; input 0 to $A$ out 0.

The Moore version needs three states: $S_0$ with output 0 (no progress), $S_1$ with output 0 (last bit 1), $S_2$ with output 1 (last two bits 11). Input 1 moves $S_0 \to S_1 \to S_2 \to S_2$; input 0 returns every state to $S_0$. During the four cycles of input $0111$, the Mealy output is $0011$. The Moore output (the label of the present state) is $0001$ and stays 1 in the fifth cycle: the same response one cycle later.

Encode $S_0 = 00$, $S_1 = 01$, $S_2 = 10$ as $Q_1Q_0$; code 11 is unused (don't-care). Next state: input $x = 0$ gives 00 from every state; $x = 1$ gives $01$ from $S_0$ and $10$ from $S_1$ and $S_2$. Using the don't-cares,

Neither equation can shrink: $D_0$ has a single on-set row (001), and the don't-cares 110 and 111 are not adjacent to it.

$D_A = Ax + Bx$, $D_B = A'x$, output $y = (A + B)x'$. Evaluating every row:

The rows for 10 and 11 are identical, so those two states merge. After that merge, state 01 also matches: it goes to 00 on $x = 0$ and to 11, now the same state as 10, on $x = 1$, with the same outputs. The minimal machine has only two states: 00 (last input 0, or reset) and $\{01, 10, 11\}$ (last input 1), with $y = 1$ exactly on a 1 followed by 0. Stopping after the first merge, at three states, is the usual mistake. It is a Mealy machine because $y$ depends on $x$.

By outputs: $\{A, B, D\}$ and $\{C, E\}$. Refining: on $x = 0$, $A$ goes to $A$ (first block) while $B$ and $D$ go to $C$ and $E$ (second block), so $A$ splits off. Now $\{A\}, \{B, D\}, \{C, E\}$: $B$ and $D$ go to $\{C, E\}$ and to $\{B, D\}$; $C$ and $E$ go to $A$ and to $\{B, D\}$. Nothing splits, so the minimal machine has 3 states, even though no two rows of the original table are identical. The input $01$ separates $A$ from $B$: $A$ outputs $00$, $B$ outputs $01$.

Mealy states $S_0$ to $S_3$ hold the matched prefix length.

$S_2$ on 1 stays in $S_2$ (the input $111$ still ends in $11$). The overlapping detector goes from $S_3$ on 1 to $S_1$, keeping the final 1; the non-overlapping one goes to $S_0$. On $1101101$, the outputs are $0001001$ (overlapping) and $0001000$ (non-overlapping).

States: $S_0$ (start), $S_1$ (got 1), $S_2$ (got 10). Mealy outputs 1 on the transition that completes $101$. From $S_2$, input 1 goes to $S_1$ (the last 1 begins a new pattern); from $S_2$, input 0 goes to $S_0$; from $S_1$, input 1 stays in $S_1$. On $10101$ the output is $00101$.

With 3 states in 2 FFs, one code is unused; treat as don't-care next state or force a recovery transition as the question requires.

Common misconceptions.