Question 4 of 5: Serial Sequence Detector (“1110”) on a PAL16R4

Question 4: Serial Sequence Detector (“1110”) on a PAL16R4 (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 bit stream $X$ (the LSB of each transmitted value arrives first — this only fixes bit order, the detector still processes one bit per clock exactly as any shift-based detector does). $det$ must go high for exactly one cycle, during the bit that completes a “1110” pattern, and the detector must keep working if more 1s follow (overlap-capable, since a run of 1s after a detection can itself be the start of the next “111”).

Find. (a) minimum-state state diagram + table; (b) D flip-flop next-state equations; (c) a PAL16R4 programming of that design.

Approach. Use one state per “how many consecutive 1s have I seen so far” (0,1,2,3), plus one extra state entered the instant a 0 arrives after 3 ones (this is where $det=1$, a Moore output). From that extra state, a further 1 must go back to the “1 consecutive one” state — not to the reset state — so overlapping patterns like 1110111 0 are still caught. Encode the 5 states in 3 bits, minimize the D-equations by Quine–McCluskey (using the 3 unused codes as don’t-cares), then map the result onto a PAL16R4’s registered outputs.

1. Part (a) — state diagram and table. $S_0$=no 1s pending, $S_1$=last 1 bit was “1”, $S_2$=last two bits “11”, $S_3$=last three bits “111”, $S_4$=just completed “1110” (the one cycle where $det=1$). From $S_3$ a further 1 STAYS at $S_3$ (a run of more than three 1s is still only three ones pending); from $S_4$ a 1 drops back to $S_1$, not $S_0$ — the bit that triggered the move to $S_4$ was a 0, so a following 1 is exactly one fresh “1” toward the next pattern, which is what makes overlapping detections work.
   Fig. Q4(a) — 5-state Moore machine (double circle = $S_4$, the only state with $det=1$). Edge labels are the input bit $X$.

   State table — sequence detector (present state, current det, next state for X=0/1)

   Present state	det (this state)	Next, X=0	Next, X=1
   S0 (000)	0	S0 (000)	S1 (001)
   S1 (001)	0	S0 (000)	S2 (010)
   S2 (010)	0	S0 (000)	S3 (011)
   S3 (011)	0	S4 (100)	S3 (011)
   S4 (100)	1	S0 (000)	S1 (001)

   Simulated end-to-end against three bit-streams, including the overlap case $1,1,1,1,0\to det=0,0,0,0,1$ (the extra leading 1 is absorbed by $S_3$’s self-loop) and back-to-back detections $1,1,1,0,1,1,1,0\to det=0,0,0,1,0,0,0,1$.
2. Part (b) — D flip-flop design. Encode $S_0\dots S_4$ as $Q_2Q_1Q_0=000,001,010,011,100$ (codes 101,110,111 unused, treated as don’t-cares) and use three edge-triggered D flip-flops on a common clock. Quine–McCluskey-minimizing $D_2,D_1,D_0=f(Q_2,Q_1,Q_0,X)$ directly from the Part (a) table (every must-be-1 row is covered and every must-be-0 row is not) gives the compact result $$D_2 = Q_1Q_0\overline{X}$$ $$D_1 = Q_0X + Q_1X$$ $$\boxed{D_0 = \overline{Q_0}X + Q_1X}$$ and the Moore output is simply the state decode for $S_4$: $$det = Q_2\overline{Q_1}\,\overline{Q_0}$$ (the don’t-care codes 101/110/111 are simply left uncovered by this smaller cover — since they are never reachable, what these equations do there is irrelevant).
3. Part (c) — PAL16R4 implementation. Assign the serial input $X$ to one dedicated PAL input pin (pin 2); the three state bits $Q_2,Q_1,Q_0$ do not need separate input pins at all — a PAL16R4’s registered outputs feed their own $Q$ (and, through the array’s true/complement input buffers, $\overline{Q}$) back into the AND array automatically, exactly as the Appendix diagram’s “I=0, 1D, C1, Q” registered-output blocks show. Program $D_2,D_1,D_0$ onto the three registered outputs pins 17, 16 and 15 respectively (each has up to 8 product-term rows available in the real device; this design needs only 1–2 of them per output), with the fuses at every literal listed in the Part (b) equations left intact (a dot in Fig. Q4(c) below) and every other fuse in that row blown open. $CLK$ (pin 1) drives every registered flip-flop’s clock; the complement taps $\overline{Q_2}$ etc. are simply the inverted feedback lines the array already provides, so $det$ can be taken off a fourth product-term row wired to a combinational I/O pin (e.g. pin 19) if a separate physical output is wanted, or read directly off the state bits by the downstream circuit.
   Fig. Q4(c) — PAL16R4 programming (relevant subset): AND-array fuses (dots) for the $D_2,D_1,D_0$ product terms of Part (b), OR-summed into the registered D inputs of pins 17/16/15. $Q_2,Q_1,Q_0$ arrive via the PAL’s own registered feedback, not a dedicated input pin.
   Check

   Assumes $X$ assigned to pin 2 and $D_2,D_1,D_0$ assigned to registered outputs 17,16,15 — an explicit but arbitrary pin choice, since the question does not fix one; any other free input/registered-output assignment realizes the identical logic.