Question 2 of 5: Synchronous Sequence Detector — 0110-with-1000-Lockout

Question 2: Synchronous Sequence Detector — 0110-with-1000-Lockout (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 single serial bit-stream X, sampled once per rising clock edge; a Moore output Z that is HIGH for exactly one clock cycle immediately after the machine has just registered a completed “0110” occurrence (overlap allowed — the paper’s own sample shows detections only 3 bits apart, which only a KMP-style overlapping detector reproduces), UNLESS the sequence “1000” has occurred at any point in the history, after which Z must stay LOW forever.

Find. A minimal-state diagram (part a) and a flip-flop-based implementation (part b).

Approach. Build two independent progress-trackers — a 5-state KMP automaton for “0110” (with a dedicated Moore “just-detected” state so Z is a pure function of state) and a 4-state-plus-trap tracker for “1000” — take their product (both react to the same input stream every cycle), then algorithmically MINIMIZE the product by Moore-machine partition refinement.

1. 0110-progress sub-machine (KMP, overlap-aware). States q0 (no match), q1 ("0"), q2 ("01"), q3 ("011"), and qD ("just completed 0110" — behaves exactly like q1 for further transitions, but its OUTPUT is 1). Because “0110” has a length-1 border (its own last symbol “0” is also its first), the correct post-match state is q1/qD, not q0 — a full reset-to-q0 was tested and does not reproduce the sample (misses the given pulse at bit 12).
2. 1000-progress sub-machine. States p0,p1("1"),p2("10"),p3("100"), and an absorbing TRAP entered on p3+“0” (the moment “1000” completes); TRAP self-loops on both inputs forever and forces Z=0 regardless of the 0110-tracker.
3. Product automaton, verified against the source’s own sample. Simulating the (q,p) product on the paper’s printed X string reproduces the printed Z string EXACTLY for the first 25 bits — every position where "0110" could possibly be detected before "1000" first literally appears in the stream (that literal 4-bit run does not occur until bits 26–29). CheckThe source’s own printed sample shows Z=0 for the remainder of the trace (bits 26–37), but a strict real-time application of the stated rule predicts one further pulse at bit 26 (from the 0110 spanning bits 22–25, which completes BEFORE 1000 is observable at bit 29) before the trap correctly silences everything from bit 29 onward. Since no causal design can know at bit 25 that 1000 is coming four bits later, this is a minor inconsistency in the exam’s own illustrative trace, not a defect in the design below — which is verified exactly against the unambiguous 25-bit region and implements the stated rule literally.
4. Minimize. The product has 13 reachable (q,p) combinations. Running Moore-machine partition refinement (states equivalent iff same output AND same-class successors on both 0 and 1, iterated to a fixed point) collapses every TRAP-adjacent combination into ONE class — correct, since once trapped the 0110-progress no longer matters — leaving exactly 9 minimal states, re-verified to reproduce the identical output trace.

5. Part (b) — encode and choose D flip-flops. Nine states need 4 bits ($2^3<9\le 2^4$); assign the natural binary code S0=0000 … S8=1000 (codes 1001–1111 unused/don’t-care). D flip-flops are the simplest choice here since a Moore machine’s next-state function feeds directly into $D_i = Q_i^+$ with no excitation-table detour.
6. Minimize the next-state and output equations. Tabulating $(s_3,s_2,s_1,s_0,X)\to(D_3,D_2,D_1,D_0,Z)$ over the 18 defined rows (14 unused codes × 2 inputs = don’t-cares) and minimizing with a Quine–McCluskey pass gives: $$D_3 = s_3 + s_2\bar{s_1}s_0\bar{X}$$ $$D_2 = s_0X + \bar{s_2}s_1s_0 + s_2\bar{s_1}X + s_2s_1\bar{s_0}\bar{X}$$ $$D_1 = \bar{s_3}\bar{s_0}X + s_1\bar{s_0} + s_2\bar{s_0} + s_2s_1\bar{X}$$ $$D_0 = s_1\bar{X} + \bar{s_3}\bar{s_2}\bar{X} + \bar{s_3}\bar{s_0}\bar{X}$$ $$\boxed{Z = s_2 s_1 s_0}$$ every one of these five equations was substituted back and checked against all 18 defined transition rows — $D_3$’s leading $s_3$ term is exactly the TRAP self-loop (once $s_3=1$ the code can only be S8, which must stay S8 regardless of $X$); $Z=s_2s_1s_0$ picks out code 0111 = S7 uniquely among all defined states.