22-Elec-A4 Digital Systems and Computers · May 2017
Question 4 of 6: FSM built from an 8:1 MUX, a T and a D flip-flop
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
Paper format. National Exams, May 2017 — 16-Elec-A4 Digital Systems & Computers. Three hours, closed book, one approved Casio or Sharp calculator. Six questions, each worth 12 points; any five constitute a complete exam. A flip-flop excitation table and a list of Boolean identities are printed on the last page. Every one of the six questions is solved below, because the set is intended as a study resource rather than an exam script.
Reference texts. M. Morris Mano & M. D. Ciletti, Digital Design (6th ed.), ch. 3 (map simplification, prime implicants, hazards), ch. 4–5 (combinational and sequential design), ch. 6 (counters); J. F. Wakerly, Digital Design: Principles and Practices (5th ed.), §4.4 (timing hazards and consensus terms), ch. 7 (sequential-circuit design); C. Hamacher, Z. Vranesic, S. Zaky & N. Manjikian, Computer Organization and Embedded Systems (6th ed.), ch. 3 (memory-mapped I/O, program-controlled and interrupt I/O); F. M. Cady, Software and Hardware Engineering: Motorola M68HC11, ch. 8–9 (parallel I/O and handshaking).
Question 4: FSM built from an 8:1 MUX, a T and a D flip-flop (12 points)
Given. State variables QA (T flip-flop), QB (D flip-flop). An 8:1 MUX addressed by (S2,S1,S0) = (I, QA, QB) with data word 0,1,0,0,0,0,0,1 (only inputs 1 and 7 are high) drives TA. The D input of B is QA. The final AND gate produces $\bar Z = I\cdot\overline{Q_A Q_B}$.
Find. The combinational expressions TA, DB, Z; the full state-transition table; the I/Z state diagram; and the Moore/Mealy classification.
Fig Q4.1 — The MUX-based FSM: (I,QA,QB) select one of the eight data bits into TA; QA feeds DB; NAND(QA,QB) AND I gives Z̅.
Approach. Read TA as the addressed MUX bit and collapse it algebraically; note DB=QA and Z as the complement of the AND output; then apply the flip-flop laws $Q_A^+ = Q_A \oplus T_A$ and $Q_B^+ = D_B$ across all eight input/state combinations.
Part (a): expression for TA. The MUX data are 1 only at addresses 001 and 111, i.e. (I,QA,QB) = (0,0,1) and (1,1,1). Both have QB = 1 and I = QA, so
$$\boxed{T_A = Q_B\,(I \odot Q_A)}$$
where $\odot$ is XNOR. The remaining two are read directly off the schematic:
$$D_B = Q_A, \qquad \bar Z = I\cdot\overline{Q_A Q_B}\;\Rightarrow\; \boxed{Z = \bar I + Q_A Q_B}$$
(Z is the complement of the drawn AND output Z̅, per the question's single-output convention.)
Part (b): state-transition table. Applying $Q_A^+ = Q_A \oplus T_A$ (toggle) and $Q_B^+ = D_B = Q_A$:
State-transition table
I
QA
QB
TA
DB
QA+
QB+
Z
0
0
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
1
0
0
1
1
1
1
0
1
1
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
Part (c): state diagram. Labelling states by (QAQB) and edges by I/Z, the table gives self-loops on 00 (both inputs) and 11 (I=0), the forward walk 01→10→11 on I=0, and the returns 01→00, 11→01 on I=1. The diagram is drawn below.
Fig Q4.2 — State-transition diagram; each edge is labelled I / Z. Because Z varies with I inside a state, the labels carry distinct output values.
Part (d): Moore or Mealy? The output is $Z = \bar I + Q_A Q_B$, which depends on the present input I as well as the state. For a fixed state such as (QA,QB) = (0,0), Z = 1 when I = 0 but Z = 0 when I = 1 — the output changes without a state change. Therefore
$$\boxed{\text{this is a Mealy FSM}}$$
(a Moore machine's output would be a function of the state alone, and every I/Z edge leaving a state would carry the same Z).
