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

Question 3 of 6: JK Finite State Machine — 2-Bit Up/Down Counter

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

Notes on this paper

Paper format. National Exams, May 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 all questions are worth 12 marks. An excitation table for the RS/JK/T/D flip-flops and a table of basic Boolean identities are supplied on the last page of the paper. 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 (Ch. 2), combinational design (Ch. 4), synchronous sequential logic (Ch. 5), registers and counters (Ch. 6), memory and address decoding (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms and minimisation (Ch. 3–4), counters and shift registers (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and addressing (Ch. 2), stacks (§2.6), memory system organisation and chip-select decoding (Ch. 8).

Convention used throughout. In the address/data expressions a prime denotes complement ($\overline{A}$ is written A′ in the figures, where SVG text cannot carry an overbar). Hexadecimal constants keep the Motorola dollar-sign notation of the exam paper, written here as $7A01 in prose so that it cannot be mistaken for a mathematics delimiter.

Question 3: JK Finite State Machine — 2-Bit Up/Down Counter (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. A synchronous machine with one control input $X$, two JK flip-flops holding the state $Q_1Q_0$ ($Q_1$ the most significant bit), and the JK excitation table supplied with the paper:

$Q \rightarrow Q^{+}$	$J$	$K$	Meaning
$0 \rightarrow 0$	0	X	hold low
$0 \rightarrow 1$	1	X	set
$1 \rightarrow 0$	X	1	reset
$1 \rightarrow 1$	X	0	hold high

Find. The state diagram, the transition table annotated with $J_1, K_1, J_0, K_0$, the minimised excitation equations, and the gate-level schematic. Marks: (a) 3, (b) 3, (c) 3, (d) 3.

Approach. Write the two required sequences as one four-state ring traversed in opposite directions, tabulate present state and input against next state, convert each bit transition to $J$/$K$ requirements through the excitation table, minimise with the don't-cares, and draw the result.

(a) State diagram. The machine has four states, one per value of $Q_1Q_0$, and one input. With $X = 0$ it advances $00 \rightarrow 01 \rightarrow 10 \rightarrow 11 \rightarrow 00$; with $X = 1$ it retraces the same ring in the opposite direction. Because the outputs are the state bits themselves, this is a Moore machine whose output labels can be omitted from the arcs.
Question 3(a) - state transition diagram of the 2-bit up/down counter.
(b) State-transition and excitation table. Each row lists the present state, the input, the required next state and the flip-flop inputs read from the excitation table (with d marking a don't-care):

$X$ $Q_1$ $Q_0$ $Q_1^{+}$ $Q_0^{+}$ $J_1$ $K_1$ $J_0$ $K_0$

0 0 0 0 1 0 d 1 d

0 0 1 1 0 1 d d 1

0 1 0 1 1 d 0 1 d

0 1 1 0 0 d 1 d 1

1 0 0 1 1 1 d 1 d

1 0 1 0 0 0 d d 1

1 1 0 0 1 d 1 1 d

1 1 1 1 0 d 0 d 1

Two structural facts jump out of the table. First, $Q_0$ inverts on every single row: an up-count and a down-count both toggle the least significant bit. Second, wherever $J_1$ is specified it equals the specified value of $K_1$ in the mirror row, which is the signature of a toggle flip-flop hidden inside a JK.
(c) Minimise the excitation equations. For the least significant stage every specified entry of $J_0$ and $K_0$ is 1, so $$J_0 = K_0 = 1$$ and stage 0 is wired as a permanent toggle. For the most significant stage, collect the rows where $J_1$ is specified ($Q_1 = 0$): it is 1 for $(X,Q_0) = (0,1)$ and $(1,0)$, and 0 for $(0,0)$ and $(1,1)$. That is precisely the exclusive-OR pattern. The rows where $K_1$ is specified ($Q_1 = 1$) give the identical pattern. Hence $$J_1 = K_1 = \overline{X}Q_0 + X\overline{Q_0} = X \oplus Q_0$$ $$\boxed{\,J_0 = K_0 = 1, \qquad J_1 = K_1 = X \oplus Q_0\,}$$ The result is intuitive: the high bit must toggle when the low bit is about to roll over, and rolling over means $Q_0 = 1$ when counting up but $Q_0 = 0$ when counting down — exactly what $X \oplus Q_0$ expresses.
Check the design against the specification. Substituting the equations into the JK characteristic equation $Q^{+} = J\overline{Q} + \overline{K}Q$ gives $Q_0^{+} = \overline{Q_0}$ and $Q_1^{+} = Q_1 \oplus (X \oplus Q_0)$. For $X = 0$ this is $Q_1 \oplus Q_0$, the binary up-count rule; for $X = 1$ it is $Q_1 \oplus \overline{Q_0}$, the down-count rule. All eight rows of the table are reproduced, and because both flip-flops share one clock the machine is fully synchronous — there is no ripple delay and the count may be decoded safely.
(d) Draw the circuit. One exclusive-OR gate is the entire combinational network; the $J$ and $K$ inputs of each flip-flop are tied together, so each JK behaves as a T flip-flop.
Question 3(d) - logic circuit: two JK flip-flops wired as toggles, steered by one XOR gate.

$X$	$Q_1$	$Q_0$	$Q_1^{+}$	$Q_0^{+}$	$J_1$	$K_1$	$J_0$	$K_0$
0	0	0	0	1	0	d	1	d
0	0	1	1	0	1	d	d	1
0	1	0	1	1	d	0	1	d
0	1	1	0	0	d	1	d	1
1	0	0	1	1	1	d	1	d
1	0	1	0	0	0	d	d	1
1	1	0	0	1	d	1	1	d
1	1	1	1	0	d	0	d	1

Part	Quantity	Result
(a)	State diagram	Four-state ring; $X = 0$ clockwise (up), $X = 1$ counter-clockwise (down)
(b)	Excitation table	8 rows; $Q_0$ toggles unconditionally, $Q_1$ toggles when $X \oplus Q_0 = 1$
(c)	LSB inputs	$J_0 = K_0 = 1$
(c)	MSB inputs	$J_1 = K_1 = X \oplus Q_0 = \overline{X}Q_0 + X\overline{Q_0}$
(d)	Gate count	Two JK flip-flops and one 2-input XOR gate

Topic. Synchronous sequential design with JK flip-flops using the excitation-table method.

Key relations. JK characteristic equation $Q^{+} = J\overline{Q} + \overline{K}Q$. Excitation entries $(J,K)$ for $0\rightarrow0,\,0\rightarrow1,\,1\rightarrow0,\,1\rightarrow1$ are $(0,d),(1,d),(d,1),(d,0)$. Up-count rule $Q_k^{+} = Q_k \oplus (Q_{k-1}\cdots Q_0)$; down-count rule uses the complemented lower bits.

Why this works. The excitation table inverts the characteristic equation: instead of asking what a given $J,K$ pair does, it asks what $J,K$ pair produces a required transition. Half of those entries are don't-cares, because a JK flip-flop can reach a required next state in two ways when the relevant input is masked by the current state — and that freedom is exactly what makes JK designs cheaper than D designs. Here the don't-cares let $J_1$ and $K_1$ collapse to the same expression, which converts each JK into a toggle element and reduces the whole steering network to a single gate. The general lesson is that a bidirectional counter differs from a unidirectional one only in whether the carry condition looks at $Q$ or $\overline{Q}$, and an exclusive-OR with the direction control is the standard way to select between the two.

Common pitfall. Filling don't-care cells with zeros "to be safe". Doing so here would give $J_1 = \overline{X}Q_0\overline{Q_1} + X\overline{Q_0}\,\overline{Q_1}$ and a separate, larger expression for $K_1$, roughly tripling the gate count for identical behaviour. The second pitfall is drawing the ring in the diagram as $00 \rightarrow 01 \rightarrow 11 \rightarrow 10$ (Gray order) instead of binary order; the question asks for a binary counter.

Source. Mano & Ciletti, Digital Design, 6th ed., §5.7 (design procedure), Table 5.12 (flip-flop excitation tables), §6.4 (up/down counters); Wakerly, 5th ed., §7.4.

← Question 2 Next: Question 4 →

$X$	$Q_1$	$Q_0$	$Q_1^{+}$	$Q_0^{+}$	$J_1$	$K_1$	$J_0$	$K_0$
0	0	0	0	1	0	d	1	d
0	0	1	1	0	1	d	d	1
0	1	0	1	1	d	0	1	d
0	1	1	0	0	d	1	d	1
1	0	0	1	1	1	d	1	d
1	0	1	0	0	0	d	d	1
1	1	0	0	1	d	1	1	d
1	1	1	1	0	d	0	d	1

$X$	$Q_1$	$Q_0$	$Q_1^{+}$	$Q_0^{+}$	$J_1$	$K_1$	$J_0$	$K_0$
0	0	0	0	1	0	d	1	d
0	0	1	1	0	1	d	d	1
0	1	0	1	1	d	0	1	d
0	1	1	0	0	d	1	d	1
1	0	0	1	1	1	d	1	d
1	0	1	0	0	0	d	d	1
1	1	0	0	1	d	1	1	d
1	1	1	1	0	d	0	d	1

$X$	$Q_1$	$Q_0$	$Q_1^{+}$	$Q_0^{+}$	$J_1$	$K_1$	$J_0$	$K_0$
0	0	0	0	1	0	d	1	d
0	0	1	1	0	1	d	d	1
0	1	0	1	1	d	0	1	d
0	1	1	0	0	d	1	d	1
1	0	0	1	1	1	d	1	d
1	0	1	0	0	0	d	d	1
1	1	0	0	1	d	1	1	d
1	1	1	1	0	d	0	d	1