22-Elec-A4 Digital Systems and Computers · May 2015

Question 4 of 6: Analysis of a two-flip-flop sequential circuit

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Exams, May 2015 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book, one approved Casio or Sharp calculator. Six questions are printed and five constitute a complete exam; every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1. A flip-flop excitation table and a Boolean-identity sheet are attached to the paper. All six questions are solved below, so that the set works as a complete study resource.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design, 5th ed. — Ch. 2 (Boolean algebra and gate-level minimisation), Ch. 3 (K-maps, NAND/NOR implementation), Ch. 4 (combinational design: adders and subtractors), Ch. 5 (synchronous sequential logic, state tables and diagrams, Moore vs Mealy).
J. F. Wakerly, Digital Design: Principles and Practices, 4th ed. — Ch. 4 (combinational design practices, bubble-to-bubble logic), Ch. 7 (latches, flip-flops and their excitation tables).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — Ch. 2 (byte order, stacks), Ch. 3 (I/O, interrupt-driven serial transfer).
Freescale/Motorola, M68HC11 Reference Manual (rev. 6) — stack operation of PSHX/PSHY, big-endian storage of 16-bit operands, SCI registers.
TIA/EIA-232-F, Interface Between Data Terminal Equipment and Data Circuit-Terminating Equipment Employing Serial Binary Data Interchange — signal-level definitions used in Question 5(b).

Question 4 (12 marks) — Analysis of a two-flip-flop sequential circuit

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 circuit printed on page 4 of the paper: a single input $X$ passing through an inverter to make $\overline{X}$; an RS flip-flop $A$ and a T flip-flop $B$ sharing one clock; and the gate network redrawn below, read directly from the printed figure. Both flip-flops make $Q$ and $\overline{Q}$ available, so $A,\overline{A},B,\overline{B}$ are all present as feedback literals.

Find. (a) the four driving expressions; (b) the nine-column state transition table; (c) the state diagram; (d) the machine type, with justification.

[Figure not reproduced: Question 4 — the exam circuit redrawn for legibility, with every gate labelled by the term it produces. The layout is functionally identical to the printed schematic. See the official exam paper.]

Check: reading of the three-input gate. one from $\overline{A}$, one rising from the $\overline{X}$ rail and one dotted onto the $\overline{B}$ rail. Its output column and its centre input leg share the same $x$-coordinate on the drawing, which is why the gate can be misread as two-input. The three-input reading is the only electrically consistent one, because the $\overline{X}$ riser is drawn with a solid junction dot on the $\overline{X}$ rail and terminates nowhere else. Were the gate in fact two-input ($\overline{A}\,\overline{B}$ only), the single affected entry is the row $A=0$, $B=0$, $X=1$, whose $T_B$ would become 1 and whose $B^{+}$ would become 1 instead of 0; every other row and the Moore/Mealy conclusion are unchanged.

(a) Read the expressions off the gates. The AND gate feeding the reset input takes $A$ and $\overline{B}$; the OR gate takes $X$ and $\overline{B}$ and its output is ANDed with $\overline{A}$ to make the set input; the T input is the OR of a two-input AND on $X$ and $A$ with the three-input AND on $\overline{X}$, $\overline{A}$ and $\overline{B}$; and the output OR combines the reset term with an AND of $\overline{X}$ and $B$. Hence $$\boxed{R_A=A\overline{B},\qquad S_A=\overline{A}\,(X+\overline{B}),\qquad T_B=XA+\overline{X}\,\overline{A}\,\overline{B},\qquad Y=A\overline{B}+\overline{X}B.}$$
Check the RS legality constraint before going further. $R_A\cdot S_A=A\overline{B}\cdot\overline{A}(X+\overline{B})=0$ because the product contains $A\overline{A}$. The forbidden RS input can therefore never occur, which confirms the gate reading is self-consistent.
(b) Apply the characteristic equations. For the RS flip-flop, $A^{+}=S_A+\overline{R_A}A$; for the T flip-flop, $B^{+}=T_B\oplus B$. Evaluating both over the eight combinations of $(A,B,X)$ gives the transition table in the column order the question asks for.

Question 4(b) — state transition table, in the column order requested by the paper.
$A$	$B$	$X$	$R_A$	$S_A$	$T_B$	$A^{+}$	$B^{+}$	$Y$
0	0	0	0	1	1	1	1	0
0	0	1	0	1	0	1	0	0
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	1	1	0
1	0	0	1	0	0	0	0	1
1	0	1	1	0	1	0	1	1
1	1	0	0	0	0	1	1	1
1	1	1	0	0	1	1	0	0

(c) Draw the state diagram. Taking the state as the pair $AB$, the table gives eight directed edges. States 01 and 11 each hold themselves when $X=0$; state 00 splits to 11 or 10 depending on $X$; and state 10 leaves to 00 or 01. Every edge carries the label $X/Y$, because the output is not constant within a state.

Question 4(c) — state transition diagram. Each edge is labelled with the input that causes it and the output produced while it is taken.

(d) Classify the machine. $Y=A\overline{B}+\overline{X}B$ contains the input variable $X$ explicitly, so the output is a function of state and input, not of state alone. The table shows this concretely: in state $AB=01$ the output is $Y=1$ when $X=0$ but $Y=0$ when $X=1$, and in state $AB=11$ the same split occurs. A Moore machine would give one output value per state. This circuit is therefore a Mealy machine. Structurally, the tell-tale is the path from the primary input $X$ to the output $Y$ that does not pass through a flip-flop, which is exactly why a Mealy output can change between clock edges and can glitch when the input does.

Question 4 — final results
Item	Result
$R_A$	$A\overline{B}$
$S_A$	$\overline{A}(X+\overline{B})$
$T_B$	$XA+\overline{X}\,\overline{A}\,\overline{B}$
$Y$	$A\overline{B}+\overline{X}B$
Legality	$R_A S_A=0$ for every input, so the RS flip-flop is never driven illegally
States	All four states $AB\in\{00,01,10,11\}$ are reachable; 01 and 11 have self-loops at $X=0$
Machine type	Mealy — $Y$ depends on $X$ as well as on $AB$

Topic. Analysis of a synchronous sequential circuit: from schematic to excitation equations to state table to state diagram, and the Moore/Mealy distinction.

Key relations. Characteristic equations $A^{+}=S_A+\overline{R_A}A$ and $B^{+}=T_B\oplus B$; RS legality $R\cdot S=0$; Moore output $Y=f(\text{state})$ versus Mealy output $Y=f(\text{state},\text{input})$.

Why this works. Analysis is the exact reverse of design. The excitation equations are read straight from the combinational network; the characteristic equations then convert those excitations into next-state values without any further reasoning about the internal latch structure. Because the state variables are just the flip-flop outputs, the state table is a complete behavioural description — the schematic can be discarded once it is written. Checking $R\cdot S=0$ along the way is worth the thirty seconds it takes: on a hand-traced schematic it is the single most effective test that the wiring was read correctly, since a mis-traced feedback rail almost always produces a row where both RS inputs go high.

Common pitfall. Concluding “Moore” because the output gate is drawn after the flip-flops. Position in the drawing is irrelevant; what matters is whether a primary input reaches the output without passing through a register. Here $\overline{X}$ feeds the output AND directly, so the machine is Mealy however the page is laid out. A second pitfall is applying the T characteristic equation as $B^{+}=T_B$ rather than $B^{+}=T_B\oplus B$, which silently converts the T flip-flop into a D flip-flop and corrupts half the table.

Source. Mano & Ciletti, Digital Design, 5th ed., §5.4 (analysis of clocked sequential circuits; state table, state diagram, Moore and Mealy models) and §5.7 (design procedure using flip-flop excitation tables); Wakerly, Digital Design, 4th ed., §7.3 (clocked synchronous state-machine analysis).

← Question 3 Next: Question 5 →

$A$	$B$	$X$	$R_A$	$S_A$	$T_B$	$A^{+}$	$B^{+}$	$Y$
0	0	0	0	1	1	1	1	0
0	0	1	0	1	0	1	0	0
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	1	1	0
1	0	0	1	0	0	0	0	1
1	0	1	1	0	1	0	1	1
1	1	0	0	0	0	1	1	1
1	1	1	0	0	1	1	0	0

$A$	$B$	$X$	$R_A$	$S_A$	$T_B$	$A^{+}$	$B^{+}$	$Y$
0	0	0	0	1	1	1	1	0
0	0	1	0	1	0	1	0	0
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	1	1	0
1	0	0	1	0	0	0	0	1
1	0	1	1	0	1	0	1	1
1	1	0	0	0	0	1	1	1
1	1	1	0	0	1	1	0	0

$A$	$B$	$X$	$R_A$	$S_A$	$T_B$	$A^{+}$	$B^{+}$	$Y$
0	0	0	0	1	1	1	1	0
0	0	1	0	1	0	1	0	0
0	1	0	0	0	0	0	1	1
0	1	1	0	1	0	1	1	0
1	0	0	1	0	0	0	0	1
1	0	1	1	0	1	0	1	1
1	1	0	0	0	0	1	1	1
1	1	1	0	0	1	1	0	0