Question 2 of 5: Sequence Detector with Lockout Condition (0101, disabled by 1100)

Question 2: Sequence Detector with Lockout Condition (0101, disabled by 1100) (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. Serial input A, output X asserted for one clock cycle each time the 4-bit pattern 0101 has just been received, PROVIDED the 4-bit pattern 1100 has never occurred anywhere earlier in the stream (once 1100 occurs, X is disabled permanently). The paper's own 38-bit sample is reproduced above.

Find. A minimum-state state diagram, and a D-flip-flop-based synchronous realization (next-state and output equations).

Approach. Build the machine as two co-operating trackers combined into one product machine, then minimize: (i) a “how much of 0101 have I just seen” tracker with four progress states plus a one-cycle “just matched” output state, restarting cleanly after every match; (ii) a “how much of the lockout 1100 have I just seen” tracker that falls into a permanent trap state the instant 1100 completes. The two run in parallel on the same input; X is the first tracker's match output ANDed with “lockout trap not yet entered.” Every reachable combined state is then checked for output/next-state equivalence and merged.

1. Part (a) — 0101-progress tracker (states q0–q3, qD). q0 = nothing useful matched; q1 = last bit seen extends a “0” prefix; q2 = matched “01”; q3 = matched “010”; qD = just matched “0101” (X=1 for this one cycle). Each state's transition on the next bit either extends the match or falls back to the best-fitting shorter prefix (standard sequence-detector construction — e.g. from q2 (“01”) a further ‘1’ gives “011”, which contains no usable prefix of 0101, so it falls all the way back to q0). After a match (qD), the exam's own sample shows detection resets cleanly to q0 rather than reusing the 2-bit overlap a textbook KMP-style automaton would credit — only the clean-reset version reproduces the paper's 38-bit sample exactly, position for position.
2. 1100-lockout tracker (states p0–p3, TRAP). p0 = nothing matched; p1 = matched “1”; p2 = matched “11” (self-loops on further 1’s, since “111” still ends in the useful “11” prefix); p3 = matched “110”; on the next bit p3 either completes the lockout (bit=0, → TRAP, permanent) or falls back to p1 (bit=1, since the tail “1” of “1101” is itself a fresh 1-match).
3. Product machine, prune, minimize. Pairing every reachable (q,p) combination and collapsing every state with p=TRAP into one absorbing state (output is 0 there regardless of q, and the machine can never leave it) leaves 9 reachable states. A partition-refinement check (grouping first by output, then by where each state's 0/1 transitions land, iterated to a fixed point) confirms none of the 9 can be merged further — this is already minimum.

4. Verify against the paper's own sample. Simulating the 9-state machine bit-by-bit against the printed 38-bit A sequence reproduces the printed X sequence exactly, with two genuine matches (positions 4 and 10, before the lockout ever triggers) and the lockout itself completing partway through the stream — after which X stays 0 for the remainder of the sample even though the underlying bits would otherwise re-trigger a 0101 match, correctly demonstrating the “as long as 1100 has never been observed” clause.
5. Part (b) — D flip-flop realization. Code the 9 states in 4 bits (S0=0000…S8=1000; codes 1001–1111 unused, taken as don’t-cares) and derive each flip-flop's next-state equation D_i = f(s₃,s₂,s₁,s₀,A) by K-map, using the unused codes as don’t-cares. The four equations plus the output equation, each independently brute-force verified against every one of the 18 defined (state, input) transitions: $$D_3 = s_3 + s_2\bar{s_1}\bar{s_0}\bar{A}$$ $$D_2 = As_2\bar{s_0} + As_0s_1\bar{s_2} + s_0s_2\bar{A}\bar{s_1} + s_1\bar{A}\bar{s_0}\bar{s_2}$$ $$D_1 = s_1s_2 + s_0\bar{A} + s_0\bar{s_1} + As_1\bar{s_0} + \bar{A}\bar{s_1}\bar{s_2}\bar{s_3}$$ $$D_0 = As_2\bar{s_0} + s_0s_1\bar{s_2} + s_1s_2\bar{A} + A\bar{s_0}\bar{s_1}\bar{s_3} + \bar{A}\bar{s_1}\bar{s_2}\bar{s_3}$$ $$\boxed{X = s_0 s_1 s_2}$$ Each D_i feeds a D flip-flop clocked by the shared system clock; X is a plain 3-input AND of the state bits — no separate output logic beyond that one gate, since exactly one reachable state (S7) has all three of s₀,s₁,s₂ set.