Question 1 of 5: Combination-Lock Sequence Detector

Question 1: Combination-Lock Sequence Detector (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 $X$ (one bit per clock), output $Y$ that must equal 1 exactly when the last four bits received on $X$ were $1,0,1,1$ (overlapping occurrences allowed — e.g. input stream $\ldots101101011\ldots$ raises $Y$ at every position where a 1011 window just closed). Clock is a common synchronous clock; flip-flops are positive-edge D-type for parts (b)–(c).

Find. Part (a) — the Moore state diagram. Part (b) — minimal next-state equations $D_2,D_1,D_0$ and output equation $Y$ using 3 D flip-flops. Part (c) — the same equations mapped onto a PAL16R4's programmable AND array (fuse map).

Approach. Encode the 5 states in 3 bits, read the next-state map directly off the diagram, minimize $D_2,D_1,D_0$ with the two unused codes (101, 110, 111) as don't-cares, then re-express those same SOP equations as PAL16R4 product terms.

1. Part (b) — state assignment. $S0{=}000,\ S1{=}001,\ S2{=}010,\ S3{=}011,\ S4{=}100$ (codes 101/110/111 unused → don't-cares). The transition table read from the diagram: $000\xrightarrow{0}000,\ 000\xrightarrow{1}001,\ 001\xrightarrow{0}010,\ 001\xrightarrow{1}001,\ 010\xrightarrow{0}000,\ 010\xrightarrow{1}011,\ 011\xrightarrow{0}010,\ 011\xrightarrow{1}100,\ 100\xrightarrow{0}010,\ 100\xrightarrow{1}001$ (the last row is the easiest to get wrong: after a full "1011" match, one more 0 gives trailing window "0110", whose longest suffix matching a prefix of 1011 is "10" — length 2, i.e. S2 — not a hard reset to S0).
2. Minimize $D_2$. $D_2=1$ only for $(Q_2Q_1Q_0,X)=(011,1)$. Grouping that single minterm with the adjacent don't-care $(111,1)$ drops $Q_2$ entirely: $$D_2 = Q_1 Q_0 X$$ — true only when the machine is in S3 (or the unused 111) and $X=1$, exactly the S3→S4 edge.
3. Minimize $D_1$. $D_1=1$ at $(001,0),(010,1),(011,0),(100,0)$ — the S4→S2 edge (on $X{=}0$) also sets $Q_1$, since S2's code is 010. Grouping each minterm with the don't-cares that share its literals: $(010,1)$ joins don't-care $(110,1)$ to drop $Q_2$, giving $Q_1Q_0'X$; $(100,0)$ joins all three don't-cares with $X{=}0$ to drop both $Q_1$ and $Q_0$, giving the 2-literal term $Q_2X'$; $(001,0)$ and $(011,0)$ combine with each other (dropping $Q_1$) and with the remaining $X{=}0$ don't-cares (dropping $Q_2$), giving $Q_0X'$: $$D_1 = Q_1 Q_0' X + Q_2 X' + Q_0 X'$$.
4. Minimize $D_0$. $D_0=1$ at every $X{=}1$ row except $(011,1)$ (which needs $D_0{=}0$ since S4$=100$). Excluding exactly $Q_1Q_0{=}11$ (and its don't-care twin 111) gives $$D_0 = X\,Q_1' + X\,Q_0'$$
5. Output. Moore output is 1 only in S4 (code 100); since none of the unused codes 101/110/111 can occur, $Q_2$ alone already distinguishes S4 from every reachable state (S0–S3 all have $Q_2{=}0$), so the don't-cares let the output collapse all the way to a single literal: $$Y = Q_2$$

6. Part (c) — PAL16R4 mapping. A PAL16R4 provides a programmable AND (product-term) array feeding a fixed OR into each of 4 registered D-type outputs, with every input pin (and each registered output's feedback) available in both true and complemented form to the array — exactly the AND-OR structure the equations above are already in, so no re-derivation is needed, only a fuse-map transcription. $D_2$ needs 1 product term, $D_1$ needs 3, $D_0$ needs 2 — 6 terms total, well inside the device's 8-terms-per-output limit. $Y=Q_2$ needs no PAL term at all: it is wired straight from the $Q_2$ register's output pin.