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

Question 2 of 6: Flip-flop conversion by excitation table and K-map

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 2 (12 marks) — Flip-flop conversion by excitation table and K-map

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 standard excitation table supplied with the paper, reproduced below, and the two characteristic equations $Q^{+}=S+\overline{R}\,Q$ (with $RS=0$) for the RS flip-flop and $Q^{+}=D$ for the D flip-flop.

Given data — flip-flop excitation table (from page 7 of the paper)
$Q$	$Q^{+}$	$R$	$S$	$J$	$K$	$T$	$D$
0	0	X	0	0	X	0	0
0	1	0	1	1	X	1	1
1	0	1	0	X	1	1	0
1	1	0	X	X	0	0	1

Find. The combinational logic that must be placed in front of (a) an RS flip-flop so that it behaves as a T flip-flop, and (b) a D flip-flop so that it behaves as an RS flip-flop — each obtained from a K-map on the excitation entries and drawn as a complete circuit.

Approach. For each conversion, tabulate the required next state from the characteristic equation of the flip-flop being emulated, read the host flip-flop's excitation entries against that transition, plot those entries on a K-map in the emulated inputs plus the present state, and minimise.

(a) Required transitions for a T flip-flop. The T characteristic equation is $Q^{+}=T\oplus Q$, so the four rows are $(T,Q)=(0,0)\Rightarrow 0\to 0$; $(0,1)\Rightarrow 1\to 1$; $(1,0)\Rightarrow 0\to 1$; $(1,1)\Rightarrow 1\to 0$.
Read the RS excitation entries. From the table, $0\to0$ needs $R=\mathrm{X},S=0$; $1\to1$ needs $R=0,S=\mathrm{X}$; $0\to1$ needs $R=0,S=1$; $1\to0$ needs $R=1,S=0$. Plotting these on two 2-variable maps in $(T,Q)$ gives one 1-cell and one don't-care each.

Question 2(a) — K-map for the reset input. Taking the don't-care as 0 gives $R=TQ$.

Question 2(a) — K-map for the set input, giving $S=T\overline{Q}$.

Minimise and check the RS legality rule. Both don't-cares are assigned 0, which yields $\boxed{R=T\,Q\quad\text{and}\quad S=T\,\overline{Q}}$. The assignment is not arbitrary: setting either don't-care to 1 would make $R$ and $S$ true simultaneously for some input, and $RS=1$ is the forbidden RS condition. With the chosen pair, $R\cdot S=TQ\cdot T\overline{Q}=0$ identically. Substituting into $Q^{+}=S+\overline{R}Q$ gives $T\overline{Q}+\overline{TQ}\,Q=T\overline{Q}+\overline{T}Q=T\oplus Q$, which is exactly the T behaviour required.
Draw the (a) circuit. Two AND gates suffice: one gated by $Q$ driving $R$, one gated by $\overline{Q}$ driving $S$, both fed from $T$ and both taking their second input from the flip-flop's own outputs.

Question 2(a) — T flip-flop built from an RS flip-flop plus two AND gates.

(b) Required transitions for an RS flip-flop. The emulated device must give $Q^{+}=1$ when $S=1$, $Q^{+}=0$ when $R=1$, hold when $S=R=0$, and is undefined when $S=R=1$. Since $Q^{+}=D$ for a D flip-flop, the required D value is simply the required next state: $D=0$ for $(S,R,Q)=(0,0,0)$ and $(0,1,\cdot)$; $D=1$ for $(0,0,1)$ and $(1,0,\cdot)$; and $D$ is a don't-care for both $S=R=1$ cells.

Question 2(b) — three-variable K-map for $D$ over $(S,R,Q)$, with the two forbidden $SR=11$ cells taken as don't-cares.

Minimise. Using both don't-cares, the $S=1$ half of the map forms one four-cell group and the two cells with $R=0,Q=1$ form another, giving $\boxed{D=S+\overline{R}\,Q}$ — the RS characteristic equation itself, which is the expected answer and a useful check. One inverter, one 2-input AND and one 2-input OR are needed.
Verify against every legal input. With $S=1,R=0$: $D=1$, so $Q^{+}=1$ (set). With $S=0,R=1$: $D=0$, so $Q^{+}=0$ (reset). With $S=R=0$: $D=Q$, so the state holds. All three legal RS behaviours are reproduced.

Question 2(b) — RS flip-flop built from a D flip-flop plus an inverter, an AND and an OR.

Question 2 — final results
Conversion	Additional logic	Gate count	Check
(a) T from RS	$R=TQ$, $S=T\overline{Q}$	2 AND	$RS=0$ always; $Q^{+}=T\oplus Q$
(b) RS from D	$D=S+\overline{R}Q$	1 NOT, 1 AND, 1 OR	set / reset / hold all reproduced

Topic. Flip-flop conversion using excitation tables, and the role of don't-care assignment in preserving a device's legality constraint.

Key relations. Characteristic equations: $Q^{+}=S+\overline{R}Q$ (RS, with $RS=0$), $Q^{+}=D$, $Q^{+}=T\oplus Q$, $Q^{+}=J\overline{Q}+\overline{K}Q$ (JK). Conversion recipe: required $Q^{+}$ from the emulated equation, then host excitation entries, then K-map.

Why this works. An excitation table is the inverse of a characteristic table: instead of asking “what does this input do?” it asks “what input do I need for this transition?”. Because the transition is fully determined by the emulated flip-flop's own equation, the conversion logic is a purely combinational function of the emulated inputs and the present state — which is why a K-map over exactly those variables always produces it. The two conversions here illustrate the two extremes: converting to a simpler device (T from RS) needs steering logic on both inputs, while converting from the most primitive device (RS from D) reproduces the characteristic equation directly.

Common pitfall. Filling in the RS don't-cares to get the smallest expression without re-checking $R\cdot S=0$. Assigning the $(T,Q)=(0,1)$ don't-care in the $S$ map to 1 gives the tempting $S=T+Q$, but then $T=Q=1$ drives both $R$ and $S$ high, which is the illegal RS input. Always test the minimised pair for legality before drawing.

Source. Mano & Ciletti, Digital Design, 5th ed., §5.4 and §5.7 (flip-flop excitation tables, sequential-circuit design with different flip-flop types); Wakerly, Digital Design, 4th ed., §7.2 (latches and flip-flops, characteristic and excitation equations).

← Question 1 Next: Question 3 →