22-Elec-A4 Digital Systems and Computers · December 2013

Question 4 of 6: Synchronous Up/Down Counter with T Flip-Flops

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

Notes on this paper

Paper format. National Exams, December 2013 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book (one approved Casio or Sharp calculator). Six questions are printed; any five constitute a complete exam and every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1 (Q1 and Q5 are 3+3+3+3; Q2 is 4+4+4; Q3 and Q6 are 6+6; Q4 is 8+2+2). An excitation table for the RS/JK/T/D flip-flops and a table of 22 basic Boolean identities are supplied on the last page. All six questions are solved below, because this set is a study resource rather than a timed sitting.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog, 6th ed. — Boolean algebra and K-maps (Ch. 2–3), combinational MSI design with multiplexers and decoders (Ch. 4), synchronous sequential logic and flip-flop excitation (Ch. 5), registers and counters (Ch. 6), memory and programmable logic (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms, minimisation and timing hazards (Ch. 3–4), PLD architectures (Ch. 5), counters (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and I/O (Ch. 3), polling versus interrupts (§3.2), serial interfaces (§3.5), memory system organisation and chip-select decoding (Ch. 8).

Notation used throughout. A prime and an overbar both denote complement: $\overline{A}$ in the mathematics, A′ in the figures, where SVG text cannot carry an overbar. The variable order in every K-map is the order printed in the question, with the leftmost variable as the most significant bit, so minterm and maxterm indices match the question's numbering exactly.

Question 4: Synchronous Up/Down Counter with T Flip-Flops (12 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. Three T flip-flops holding the state $ABC$ ($A$ most significant) and two inputs:

Inputs	Required behaviour	States used
$E=0$	hold the present state, whatever $X$ is	all eight
$E=1,\ X=1$	000 → 001 → 010 → 011 → 100 → 000 (modulo-5 up)	0, 1, 2, 3, 4
$E=1,\ X=0$	111 → 110 → 101 → 100 → 011 → 111 (modulo-5 down)	7, 6, 5, 4, 3

Find. Minimum two-level SoP excitation equations $T_A$, $T_B$, $T_C$, and a justified determination of whether each count direction recovers from the states its own sequence never visits.

Approach. Exploit the fact that a T flip-flop toggles exactly when its present and next state differ, so $T = Q \oplus Q^{+}$. Then notice the structural symmetry between the two sequences — the down sequence is the bit-by-bit complement of the up sequence — which collapses the design onto a single modulo-5 up counter and makes the algebra far shorter than a raw thirty-two-row excitation table.

(a) Excitation equations (8 marks)

Deal with the enable. When $E=0$ no flip-flop may change, and a T flip-flop holds precisely when its T input is 0. Every excitation equation therefore has $E$ as a common factor: $T_i = E \cdot g_i(X,A,B,C)$. This one observation removes $E$ from the K-mapping entirely.
Spot the complement symmetry. Write the two sequences one above the other: $$\begin{aligned} \text{up}\ (X{=}1):&\quad 000 \to 001 \to 010 \to 011 \to 100 \to 000 \\ \text{down}\ (X{=}0):&\quad 111 \to 110 \to 101 \to 100 \to 011 \to 111 \end{aligned}$$ Each down state is the bit-complement of the up state in the same position. Since $T = Q \oplus Q^{+}$ and complementing both $Q$ and $Q^{+}$ leaves their exclusive-OR unchanged, the T values for corresponding states are identical. Define the transformed state bits $$a = A \oplus \overline{X}, \qquad b = B \oplus \overline{X}, \qquad c = C \oplus \overline{X}$$ so that $abc$ equals $ABC$ when $X=1$ and its complement when $X=0$. Both required behaviours are now the single modulo-5 up count on $abc$.
Build the reduced excitation table. With $T = Q \oplus Q^{+}$ applied to the five used states (the other three are don't cares, to be exploited):

$abc$ next $T_a$ $T_b$ $T_c$

000 001 0 0 1

001 010 0 1 1

010 011 0 0 1

011 100 1 1 1

100 000 1 0 0

101, 110, 111 unused d d d
Minimise the three transformed excitations. $T_c$ is 1 on all four cells with $a=0$ and 0 at $abc=100$; assigning the three don't cares to 0 gives the single literal $T_c = \overline{a}$. $T_b$ is 1 exactly where $c=1$ among the used states and 0 wherever $c=0$, so assigning the don't cares to follow $c$ gives $T_b = c$. $T_a$ is 1 at 011 and 100 only; taking the don't cares as 1 merges 101, 110, 111 with 100 to give the single literal $a$, and 011 is picked up by $bc$: $$T_a = a + bc, \qquad T_b = c, \qquad T_c = \overline{a}$$
Substitute the transformation back. Note $a = A \oplus \overline{X} = AX + \overline{A}\,\overline{X}$ (the coincidence of $A$ and $X$) and correspondingly $\overline{a} = A \oplus X = A\overline{X} + \overline{A}X$. Expanding the products — every cross term contains $X\overline{X}=0$ and vanishes — gives the minimum two-level SoP forms: $$\boxed{\;\begin{aligned} T_A &= E\,(AX + \overline{A}\,\overline{X} + BCX + \overline{B}\,\overline{C}\,\overline{X}) \\ T_B &= E\,(CX + \overline{C}\,\overline{X}) \\ T_C &= E\,(A\overline{X} + \overline{A}X) \end{aligned}\;}$$ That is eight product terms in total (four, two and two), and $T_B$ and $T_C$ are just $E\!\cdot\!\overline{(C \oplus X)}$ and $E\!\cdot\!(A \oplus X)$ written out at two levels as the question demands.

\(abc\)	next	\(T_a\)	\(T_b\)	\(T_c\)
000	001	0	0	1
001	010	0	1	1
010	011	0	0	1
011	100	1	1	1
100	000	1	0	0
101, 110, 111	unused	d	d	d

Simulating these equations over all thirty-two combinations of $E$, $X$ and the eight states reproduces both required sequences exactly and holds the state for every state when $E=0$, which is the complete correctness check for part (a).

Figure 4.1 — the datapath: one shared block of two-level SoP logic drives the three T inputs, with the state fed back and the common clock omitted for clarity.

(b) Is the count-up self-starting? (2 marks)

A counter is self-starting if, from every state including those its intended sequence never uses, it reaches the main cycle in a finite number of clocks. Because part (a) resolved the don't cares in favour of minimal logic, the behaviour in the three unused states was decided implicitly and must now be read back out of the equations rather than assumed.

Reduce the equations for $X=1$. Substituting $X=1,\ E=1$ collapses them to $T_A = A + BC$, $T_B = C$, $T_C = \overline{A}$.
Evaluate the three unused states. Applying $Q^{+} = Q \oplus T$ bit by bit:

State $ABC$ $T_A$ $T_B$ $T_C$ Next state In the cycle?

101 1 1 0 011 yes

110 1 0 0 010 yes

111 1 1 0 001 yes
Conclude. All three unused states enter the main count within a single clock, and none of them forms a closed sub-cycle: $$\boxed{\text{the count-up is self-starting; worst-case recovery is one clock}}$$

State \(ABC\)	\(T_A\)	\(T_B\)	Next state	In the cycle?
101	1	1	011	yes
110	1	0	010	yes
111	1	1	001	yes

Figure 4.2 — count-up state diagram for $E=1,\ X=1$. Black: the required modulo-5 ring. Red: the three unused states, each of which drops straight into the ring.

(c) Is the count-down self-starting? (2 marks)

Reduce the equations for $X=0$. Substituting $X=0,\ E=1$ gives $T_A = \overline{A} + \overline{B}\,\overline{C}$, $T_B = \overline{C}$, $T_C = A$ — the exact complement-duals of the count-up forms, as the symmetry of part (a) guarantees.
Evaluate the three unused states (here 000, 001 and 010, since the down sequence uses 3 through 7):

State $ABC$ $T_A$ $T_B$ $T_C$ Next state In the cycle?

000 1 1 0 110 yes

001 1 0 0 101 yes

010 1 1 0 100 yes
Conclude. Again every unused state joins the ring on the next clock edge: $$\boxed{\text{the count-down is also self-starting; worst-case recovery is one clock}}$$ This is not a coincidence: the complement transformation maps the unused up-states $\{101,110,111\}$ onto the unused down-states $\{010,001,000\}$ and preserves the recovery behaviour, so proving part (b) proves part (c).

State \(ABC\)	\(T_A\)	\(T_B\)	Next state	In the cycle?
000	1	1	110	yes
001	1	0	101	yes
010	1	1	100	yes

Figure 4.3 — count-down state diagram for $E=1,\ X=0$. Compare with Figure 4.2: it is the same diagram with every state label complemented.

Quantity	Result
$T_A$	$E(AX + \overline{A}\,\overline{X} + BCX + \overline{B}\,\overline{C}\,\overline{X})$
$T_B$	$E(CX + \overline{C}\,\overline{X})$
$T_C$	$E(A\overline{X} + \overline{A}X)$
Total product terms	8 (4 + 2 + 2)
(b) count-up self-starting?	yes — 101→011, 110→010, 111→001 (one clock)
(c) count-down self-starting?	yes — 000→110, 001→101, 010→100 (one clock)

Check: the don't-care assignment is a design decision, and it is the one being graded in parts (b) and (c). The three unused states were assigned in part (a) purely to minimise the logic, exactly as the question's "minimum 2-level SoP" instruction demands. A different assignment would give different — and possibly non-self-starting — behaviour from those states, so the self-start property here is a consequence of the minimisation that had to be checked, not an assumption. Had a lock-up been found, the standard remedy is to un-minimise: force one or more don't cares to the value that steers the offending state back into the ring, accepting an extra product term.

Topic. Synchronous counter design with T flip-flops, don't-care exploitation, and self-start (lock-up) analysis.

Key relations. T flip-flop excitation $T = Q \oplus Q^{+}$, and characteristic equation $Q^{+} = Q \oplus T$; a synchronous enable is realised as a common factor $T_i = E \cdot g_i$; the state count $2^n$ always exceeds the used-state count in a non-power-of-two counter, and the surplus states are exactly where lock-up can hide.

Why this works. The T flip-flop is the natural element for counters because a counter's defining property is which bits change, and that is precisely what T encodes; using D flip-flops would require the full next-state function rather than the sparser change function, typically costing more product terms. The complement symmetry used here is worth internalising: any counter whose down sequence is the bitwise complement of its up sequence can be designed once and mapped with an exclusive-OR on the direction control, and this is exactly how commercial up/down counters implement direction. Because the mapping preserves the exclusive-OR that defines T, the excitation logic is literally shared rather than duplicated — a straight two-copies-and-a-multiplexer design would cost roughly twice the gates.

Common pitfall. Answering parts (b) and (c) from the specification rather than from the implemented equations. The specification says nothing about the unused states; only the minimised logic does, and it must be evaluated. The second frequent error is forgetting that during a transition only $Q$ is continuous — students sometimes read the next state off the T values directly instead of exclusive-ORing them with the present state. A third is treating $E$ as an asynchronous inhibit and gating the clock with it, which produces clock skew and is poor practice; gate the T inputs, never the clock.

Source. Mano & Ciletti, Digital Design, 6th ed., §5.7 (design procedure with flip-flop excitation tables) and §6.4 (synchronous counters, unused-state analysis); Wakerly, 5th ed., §7.4 and §8.4.

← Question 3 Next: Question 5 →

Inputs	Required behaviour	States used
\(E=0\)	hold the present state, whatever \(X\) is	all eight
\(E=1,\ X=1\)	000 → 001 → 010 → 011 → 100 → 000 (modulo-5 up)	0, 1, 2, 3, 4
\(E=1,\ X=0\)	111 → 110 → 101 → 100 → 011 → 111 (modulo-5 down)	7, 6, 5, 4, 3

Quantity	Result
\(T_A\)	\(E(AX + \overline{A}\,\overline{X} + BCX + \overline{B}\,\overline{C}\,\overline{X})\)
\(T_B\)	\(E(CX + \overline{C}\,\overline{X})\)
\(T_C\)	\(E(A\overline{X} + \overline{A}X)\)
Total product terms	8 (4 + 2 + 2)
(b) count-up self-starting?	yes — 101→011, 110→010, 111→001 (one clock)
(c) count-down self-starting?	yes — 000→110, 001→101, 010→100 (one clock)