Finite State Machine Design with D Flip-Flops: 04-BS-8, December 2014, Q3

Question 3: Finite State Machine Design with D 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 Moore-type FSM with 4 states $\{A,B,C,D\}$, two inputs $x,y$, one output $Z$ that depends only on present state ($Z_A{=}1,Z_B{=}1,Z_C{=}0,Z_D{=}1$), and the transition table above.

Find. (a) The state diagram and the minimum number of flip-flops needed; (b) a complete D-flip-flop realization: state assignment, excitation ($D$) equations and output ($Z$) equation.

Approach. Assign a 2-bit binary code to each of the 4 states, rewrite the transition table as a 16-row truth table over $(Q_1,Q_0,x,y)$, minimize $D_1$, $D_0$ and $Z$ by K-map (Quine–McCluskey), and verify every row reproduces the given state table exactly.

Part (a) — flip-flop count. The machine has 4 distinct states, and an $n$-flip-flop register distinguishes at most $2^n$ states, so the minimum is $n=\lceil\log_2 4\rceil=\boxed{2}$ flip-flops (1 flip-flop would distinguish only 2 states, too few).

Part (a): Moore state diagram (edge labels = present input $xy$; $Z$ shown inside each state since the output depends on present state only). Four distinct states $\Rightarrow \lceil\log_2 4\rceil = 2$ flip-flops are required (a single flip-flop distinguishes only 2 states).

Part (b) — state assignment. Assign the natural binary codes $A{=}00,\ B{=}01,\ C{=}10,\ D{=}11$ on $(Q_1,Q_0)$. Rewriting every present-state/input row of the given table in this code produces the full 16-row transition table (present $Q_1Q_0xy$ → next $Q_1^+Q_0^+$, output $Z$).
Part (b) — minimize the excitation equations by K-map. Grouping $D_1=Q_1^+$ and $D_0=Q_0^+$ each over the 16-row table (Quine–McCluskey minimization) gives $$D_1 = Q_1y\overline x + xy\overline{Q_0} + Q_0\overline{Q_1}\,\overline x + Q_0Q_1x\overline y,$$ $$D_0 = Q_0\overline y + \overline{Q_1}\,\overline y + \overline x\,\overline y + Q_1xy\overline{Q_0}.$$
Part (b) — minimize the output equation. $Z$ is 1 for states $A,B,D$ and 0 only for state $C$ ($Q_1Q_0{=}10$), independent of the inputs, so $$Z = \boxed{\overline{Q_1} + Q_0}$$ (a 2-gate realization: one inverter on $Q_1$ feeding a 2-input OR with $Q_0$), confirmed equal to the Quine–McCluskey result for all 4 state codes.

Part (b): the two D flip-flops hold the state code ($A{=}00,B{=}01,C{=}10,D{=}11$); a combinational block realizes $D_1=Q_1y\bar x+xy\bar Q_0+Q_0\bar Q_1\bar x+Q_0Q_1x\bar y$ and $D_0=Q_0\bar y+\bar Q_1\bar y+\bar x\bar y+Q_1xy\bar Q_0$ (each minimized from the 16-row transition table by K-map), and a 2-gate block realizes $Z=\overline{Q_1}+Q_0$.

Check

State assignment $A{=}00,B{=}01,C{=}10,D{=}11$ is an engineering choice (any bijection to $\{00,01,10,11\}$ realizes the same machine); the $D_1,D_0,Z$ equations above are specific to this assignment and were checked to reproduce every row of the given state table exactly.

Quantity	Result
(a) Flip-flops required	2 (4 states, $\lceil\log_2 4\rceil=2$)
(b) State assignment	$A{=}00,\ B{=}01,\ C{=}10,\ D{=}11$ on $(Q_1,Q_0)$
(b) $D_1$	$Q_1y\overline x+xy\overline{Q_0}+Q_0\overline{Q_1}\overline x+Q_0Q_1x\overline y$
(b) $D_0$	$Q_0\overline y+\overline{Q_1}\,\overline y+\overline x\,\overline y+Q_1xy\overline{Q_0}$
(b) $Z$	$\overline{Q_1}+Q_0$

Concept & Theory

Topic. Synchronous sequential circuit design: state assignment and D-flip-flop excitation equations.

Key relations. Minimum flip-flop count $n=\lceil\log_2(\text{states})\rceil$; D-flip-flop characteristic equation $Q^+=D$, so the excitation equation for each state bit is literally its next-state function $Q_i^+(Q,x,y)$ read straight off the transition table; Moore-machine output $Z(Q)$ depends on present state only, never on the inputs directly.

Why this works. A D flip-flop's next output equals whatever is presented at $D$ one clock edge earlier, so designing with D flip-flops reduces exactly to writing down the next-state function for each state bit — no excitation-table translation (as JK or T flip-flops would need) is required, which is why D-based synchronous design is the most direct of the classical methods.

Common pitfall. Forgetting that a different state assignment gives algebraically different (though functionally equivalent) $D_1,D_0$ equations — there is no unique "correct" excitation equation, only a correct behaviour; and conflating a Moore output (function of state only) with a Mealy output (function of state and input), which would change how $Z$ is derived.

Source. Mano & Ciletti, Digital Design, Ch. 5 (synchronous sequential logic, state assignment and flip-flop excitation).

Question 3 of 5: Finite State Machine Design with D Flip-Flops

Question 3: Finite State Machine Design with D Flip-Flops (25 marks)