Question 4 of 5: Finite State Machine Design with D Flip-Flops
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2016 — 04-BS-8 Digital Logic Circuits. Three-hour, closed-book exam (Casio or Sharp approved calculator only; one hand-written 8.5"×11" aid sheet permitted). Format: five questions offered, each worth 25 marks (100 total); any four constitute a complete paper and only the first four appearing in the answer book are marked. All five are solved below for completeness.
Reference texts: Mano & Ciletti, Digital Design (6th ed., Pearson) — Boolean minimization, PAL/PLA architectures, flip-flop conversion, sequential design, arithmetic circuits, serial 2's-complement conversion; Floyd, Digital Fundamentals (11th ed., Pearson) — decoders, number systems, flip-flop characteristic tables, counters and shift registers.
Question 4: Finite State Machine Design with D Flip-Flops (25 marks)
Part (a) — state diagram and machine type. Each row of the state table lists exactly ONE output value (Z=1 for S1, S2, S4; Z=0 for S3), with output depending only on which state the machine is currently in — NOT on the current input (a,b). This is precisely the defining property of a Moore machine (output is a function of state alone, $Z=f(\text{state})$), as opposed to a Mealy machine, whose output would instead depend on both the present state AND the current input, and would therefore need to be tabulated once per (state, input) pair rather than once per state.
Fig. 4 — Moore state diagram: each state's output Z is written inside its bubble (state-only, not edge-labelled); edges are labelled with the input combination ab that causes the transition.
Part (b) — Given. The 4-state Moore machine above; D-type flip-flops available.
Find. A complete D-flip-flop-based realization: state assignment, next-state (excitation) equations, and output equation.
Approach. Assign a 2-bit binary code to each of the 4 states (2 flip-flops needed, since $2^2=4$), tabulate the required next-state code for every (state, a, b) combination, then minimize $D_1$, $D_0$ (the two flip-flops' D inputs, which for a D flip-flop simply equal the required next state) and $Z$ by K-map.
State assignment. $S1{=}00,\ S2{=}01,\ S3{=}10,\ S4{=}11$ (encoded as $Q_1Q_0$).
Next-state table. Re-expressing every row of the state table in binary and reading off $Q_1^+Q_0^+ = D_1D_0$ directly (a D flip-flop's next state always equals its D input, so $D_1=Q_1^+$, $D_0=Q_0^+$):
$Q_1Q_0$
ab=00
01
10
11
00 (S1)
01
00
01
10
01 (S2)
11
10
01
00
10 (S3)
01
10
00
11
11 (S4)
01
10
11
00
Minimize $D_1$ by K-map over $(Q_1,Q_0,a,b)$: minterms $\{3,4,5,9,11,13,14\}$ group as: $\{4,5\}\to Q_1'Q_0a'$; $\{3,11\}\to Q_0'ab$; $\{9,13\}\to Q_1a'b$; $\{14\}$ paired with $\{...\}$ wait — $\{14\}$ groups with the wxyz-style pair to give $Q_1Q_0ab'$. $$\boxed{D_1 = Q_1Q_0ab' + Q_0'ab + Q_1'Q_0a' + Q_1a'b}$$
Minimize $D_0$ by K-map over the same variables: minterms $\{0,2,4,6,8,11,12,14\}$ group as $Q_1'b'\ (\{0,2,4,6\})$, $Q_0b'\ (\{4,6,12,14\})$, $a'b'\ (\{0,4,8,12\})$, and the lone remaining minterm 11 as $Q_1Q_0'ab$: $$\boxed{D_0 = Q_1'b' + Q_0b' + a'b' + Q_1Q_0'ab}$$
Circuit. Two D flip-flops (clocked together) hold $Q_1,Q_0$; the combinational networks above drive $D_1$ and $D_0$ from $(Q_1,Q_0,a,b)$; $Z$ is combinational, taken directly from $Q_1,Q_0$ (Moore output, available immediately after each clock edge and stable for the whole following period — it does not glitch with $a,b$).
