Question 3 of 6: MUX-based finite state machine with T and D flip-flops

Question 3 (16 marks) — MUX-based finite state machine with T and D flip-flops

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. The schematic on page 4 of the paper, read directly from the printed figure: an 8:1 MUX whose data inputs $I_{0}\ldots I_{7}$ are hard-wired to 0, 1, 0, 0, 0, 0, 0, 1; select inputs $S_{2}=I$, $S_{1}=Q_{B}$ and $S_{0}$ tied to logic 1; the MUX output driving the T input of flip-flop A; $\overline{Q}_{A}$ driving the D input of flip-flop B; and $Z = \mathrm{AND}\big(Q_{A},\ \mathrm{NAND}(I,Q_{B})\big)$. Both flip-flops carry a bubble on the clock pin, so both are negative-edge triggered, and both have an active-low asynchronous clear.

Find. (a) the machine type, (b) the three logic expressions, (c) the full transition table, (d) the state diagram and (e) the completed timing waveforms.

[Figure not reproduced. See the official exam paper.]

Approach. Reduce the MUX to a Boolean expression first: with $S_{0}$ tied high only the odd-numbered data inputs can ever be selected, which collapses the eight-input MUX to a four-entry truth table in $I$ and $Q_{B}$. Everything else then follows mechanically.

1. (a) Classify the machine. The output network is $Z=\mathrm{AND}(Q_{A},\mathrm{NAND}(I,Q_{B}))$, which contains the primary input $I$ as well as state variables. A state that demonstrates the dependence is $Q_{A}Q_{B}=11$: there $Z=1$ when $I=0$ but $Z=0$ when $I=1$, so the output changes without any state change. $$\boxed{\text{Mealy machine — }Z=Z(Q_{A},Q_{B},I)\text{, not a function of the state alone}}$$ In a Moore machine $Z$ would be decoded from the flip-flop outputs only, and the $I$ input would reach the output network not at all.
2. (b) Reduce the multiplexer. An 8:1 MUX outputs $Y = I_{k}$ where $k = 4S_{2}+2S_{1}+S_{0}$. Here $S_{0}=1$ permanently, so $k = 4I + 2Q_{B} + 1$ and only $I_{1}$, $I_{3}$, $I_{5}$ and $I_{7}$ are ever addressed. Reading the hard-wired values 0, 1, 0, 0, 0, 0, 0, 1 at those four positions gives $I_{1}=1$, $I_{3}=0$, $I_{5}=0$ and $I_{7}=1$:

   MUX reduction with $S_{0}=1$

   $I$	$Q_{B}$	address $k$	data input	$T_{A}$
   0	0	1	$I_{1}=1$	1
   0	1	3	$I_{3}=0$	0
   1	0	5	$I_{5}=0$	0
   1	1	7	$I_{7}=1$	1

   That column is 1 exactly when $I$ and $Q_{B}$ agree, so the MUX is wired as an exclusive-NOR. With $\overline{Q}_{A}$ feeding the D input and the output gates read straight off the schematic, the three required expressions are$$\boxed{\;T_{A} = I\odot Q_{B} = \overline{I\oplus Q_{B}} = I\,Q_{B} + \overline{I}\,\overline{Q}_{B},\qquad D_{B} = \overline{Q}_{A},\qquad Z = Q_{A}\cdot\overline{I\,Q_{B}}\;}$$
3. (c) Build the state transition table. A T flip-flop obeys $Q_{A}^{+}=Q_{A}\oplus T_{A}$ and a D flip-flop obeys $Q_{B}^{+}=D_{B}$, so each row is filled by evaluating the three expressions above and then applying those two laws.

   Q3(c) state transition table

   $I$	$Q_{A}$	$Q_{B}$	$T_{A}$	$D_{B}$	$Q_{A}^{+}$	$Q_{B}^{+}$	$Z$
   0	0	0	1	1	1	1	0
   0	0	1	0	1	0	1	0
   0	1	0	1	0	0	0	1
   0	1	1	0	0	1	0	1
   1	0	0	0	1	0	1	0
   1	0	1	1	1	1	1	0
   1	1	0	0	0	1	0	1
   1	1	1	1	0	0	0	0

   Two features are worth noting. Every one of the four states appears in the $Q_{A}^{+}Q_{B}^{+}$ column, so no state is unreachable and there is no lock-out. And the single row where $Q_{A}Q_{B}=11$ flips its output with $I$ is the concrete evidence for the Mealy classification in part (a).
4. (d) Draw the state diagram. Plotting the eight rows as directed edges labelled $I/Z$ shows the structure clearly: holding $I=1$ walks the three-state ring $00 \to 01 \to 11 \to 00$ while state 10 sits on a self-loop, and holding $I=0$ walks the mirror-image ring $00 \to 11 \to 10 \to 00$ with state 01 as the self-loop.
   Q3(d) Mealy state diagram. Green edges are $I=1$, orange edges $I=0$; each label reads $I/Z$.
   So the input selects which of two three-state cycles the machine runs, and the state that is excluded from the active cycle parks itself until $I$ changes.
5. (e) Complete the timing diagram. Both flip-flops respond to the falling edge of CLK, and $\overline{CLR}$ is released before the first falling edge, so the machine starts from $Q_{A}Q_{B}=00$. Sampling the printed $I$ waveform at each of the seven complete falling edges gives $I = 1, 1, 0, 0, 1, 1, 0$, and stepping the transition table through those values yields the state walk $00 \to 01 \to 11 \to 10 \to 00 \to 01 \to 11 \to 10$.
   Q3(e) completed waveforms for $Q_{A}$, $Q_{B}$ and $Z$. Numbered dashed lines mark the seven negative clock edges.
   The subtlety in this part is $Z$. Because the machine is Mealy, $Z$ does not wait for a clock edge: it steps up as soon as $I$ falls while the machine sits in state 11 (between edges 2 and 3, and again just before edge 7), and it steps down at edge 4 when the state leaves $Q_{A}=1$. Drawing $Z$ as if it changed only on clock edges is the single most common error on this part.