Question 1 of 5: Serial Sequence Detector (11010) with JK Flip-Flops

Question 1: Serial Sequence Detector (11010) with JK Flip-Flops (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-bit serial input $X$ is sampled once per clock; the circuit must raise a Mealy output $Z$ to HIGH during the clock period in which the 5th bit completes a valid 11010 sequence (overlapping sequences allowed, MSB-first).

Find. (a) The state diagram and state table; (b) the next-state and output Boolean equations, the JK excitation equations, and the flip-flop count.

Approach. Build a Mealy machine whose states track "longest prefix of 11010 matched so far," using the standard failure-function (KMP-style) rule for the next state on a mismatch so overlapping detections are never missed; encode the 5 states in 3 bits, derive $Q^+$ and $Z$ by Boolean minimization, then convert each next-state equation into JK excitation equations via the JK excitation table.

1. Define the states. $S_0$ = no bits of the pattern matched, $S_1$ = "1" matched, $S_2$ = "11" matched, $S_3$ = "110" matched, $S_4$ = "1101" matched. Encode $Q_2Q_1Q_0$: $S_0{=}000,\ S_1{=}001,\ S_2{=}010,\ S_3{=}011,\ S_4{=}100$ (codes 101/110/111 unused, don't-care).
2. Derive every transition with the overlap (failure-function) rule. On a mismatch, the next state is the longest prefix of 11010 that is also a suffix of the bits just seen — found by trying candidate re-matches rather than always resetting to $S_0$. Working through every (state, input) pair gives the table below; only $S_4\xrightarrow{0}S_0$ produces $Z=1$ (the 5th bit, "0", completing 11010, output HIGH during that bit), and $S_4\xrightarrow{1}S_2$ (not back to $S_0$) because the last two bits received, "11", are themselves the longest re-usable prefix of the pattern.

3. Part (b) — minimize the next-state and output equations. Tabulating $Q_2^+,Q_1^+,Q_0^+,Z$ over all 10 valid (state,$X$) rows (with codes 101/110/111 as don't-cares) and minimizing by K-map gives $$Q_2^+ = Q_1Q_0X,\qquad Q_1^+ = Q_2X + Q_1\overline{Q_0} + Q_0X\overline{Q_1},$$ $$Q_0^+ = Q_1\overline{Q_0}\,\overline{X} + X\overline{Q_0}\,\overline{Q_1}\,\overline{Q_2}, \qquad \boxed{Z = Q_2\overline{X}}$$
4. Part (b) — convert to JK excitation equations. Using the JK excitation table ($Q{\to}Q^+{=}0{\to}0\Rightarrow J{=}0,K{=}d$; $0{\to}1\Rightarrow J{=}1,K{=}d$; $1{\to}0\Rightarrow J{=}d,K{=}1$; $1{\to}1\Rightarrow J{=}d,K{=}0$) on each flip-flop and minimizing with the same don't-cares gives $$J_2 = Q_1Q_0X,\quad K_2 = 1,\qquad J_1 = X(Q_0+Q_2),\quad K_1 = Q_0,$$ $$\boxed{J_0 = Q_1\overline{X} + X\overline{Q_1}\,\overline{Q_2}, \quad K_0 = 1}$$ — every one of these six equations was substituted back and checked to reproduce all 10 transitions exactly.