Question 3 of 5: Sequence-Detector FSM — “1100” After ≥3 Zeros

Question 3: Sequence-Detector FSM — “1100” After ≥3 Zeros (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A serial input $A$, one bit per clock; output $X$ Moore-asserted for exactly one cycle after the FSM has seen “1100” (as four consecutive bits), provided that pattern occurs following a run of $\ge 3$ consecutive zeros since the last detection (or since reset).

Find. (a) A minimum-state state diagram. (b) A flip-flop + gate implementation (state equations, minimized).

Approach. Track two concerns with one state variable: while unarmed, count consecutive zeros (need $\ge 3$ to arm); once armed, run the standard KMP/failure-function automaton for the literal pattern “1100” (so a false start such as “111” correctly keeps 2 bits of credit, not 0); on a full match, output X for one cycle then drop back to unarmed (zero-count restarts from scratch) — consuming the arm on every detection, per the question’s wording.

1. Part (a) — state diagram. Eight states suffice and no fewer, since 3 distinct zero-counts (0,1,2) must be told apart while unarmed, 4 distinct match-progress levels (0,1,2,3 of “1100”) must be told apart while armed, and the just-detected condition needs its own state to hold $X=1$ for exactly one cycle: $S_0,S_1,S_2$ = unarmed, 0/1/2 zeros seen; $S_3,S_4,S_5,S_6$ = armed, matched 0/1/2/3 leading bits of “1100”; $S_7$ = just detected (outputs $X=1$). Every transition below follows the KMP automaton for “1100” and was simulated end-to-end against the paper’s sample (see the Verify note above).
   Fig. Q3(a) — 8-state Moore machine (double circle = $S_7$, the only state with $X=1$). Edge labels are the input bit $A$ that causes the transition.
2. Part (b), Step 1 — state assignment and D-equations. Encode $S_0\dots S_7$ as $Q_2Q_1Q_0=000\dots111$ in that order and use three positive-edge D flip-flops. Quine–McCluskey-minimizing each $D_i=f(Q_2,Q_1,Q_0,A)$ over the full 16-row transition table gives $$D_2 = Q_2Q_1'Q_0 + Q_2Q_1Q_0' + Q_2'Q_1Q_0A + Q_2Q_0'A$$ $$D_1 = Q_2Q_0'A' + Q_2'Q_1A' + Q_1'Q_0A'$$ $$\boxed{D_0 = Q_2Q_1'A + Q_0'A' + Q_1A'}$$ each equation guaranteed consistent with the Part (a) diagram because it was minimized directly from that same transition table, not re-derived by hand.
3. Part (b), Step 2 — output logic. $X=1$ only in state $S_7=111$, so $$X = Q_2\cdot Q_1\cdot Q_0$$ a single 3-input AND (or two cascaded 2-input ANDs) on the state bits — no separate output flip-flop is needed since $X$ is a pure (Moore) function of state.
4. Part (b), Step 3 — implementation. Three positive-edge-triggered D flip-flops hold $Q_2Q_1Q_0$; the combinational block realizing $D_2,D_1,D_0$ (from Step 1) feeds back into the D inputs each clock, exactly as in the Q1-style synchronous-counter template (K-map-derived next-state logic → D-FF bank → feedback), and a 3-input AND on $Q_2Q_1Q_0$ drives $X$.