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

Question 2 of 6: Synchronous Counter Design with JK Flip-Flops

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

Notes on this paper

Paper format. National Exams, May 2014 — 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 given in the page-1 marking scheme (Q1 is 3+3+3+3; Q2 is 6+3+3; Q3 is 6+6; Q4 is 3+3+6; Q5 and Q6 are 4+4+4). A flip-flop excitation table for the RS/JK/T/D types 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, canonical forms and K-maps (Ch. 2–3), combinational MSI decoders and demultiplexers (Ch. 4), synchronous sequential design and flip-flop excitation (Ch. 5), registers and counters (Ch. 6).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — minimisation and static timing hazards (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. — the four essential subsystems and bus structure (Ch. 1–3), serial interfaces and UART framing (§3.5), the processor register set and addressing modes (Ch. 2).
M. A. Mazidi, R. McKinlay and D. Causey, PIC Microcontroller and Embedded Systems — port-driven multiplexed seven-segment displays and LED current limiting (Ch. 12).

Notation used throughout. A bar and a prime both denote complement: $\overline{A}$ in the mathematics and A′ in the figures, where SVG text cannot carry an overbar. In every K-map the leftmost variable is the most significant bit, so the minterm indices printed in the cells match the question’s own variable ordering.

Question 2: Synchronous Counter Design with JK 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. A modulo-6 counting sequence on three state variables $Q_AQ_BQ_C$ ($Q_A$ the MSB): 000 → 010 → 100 → 101 → 011 → 001 → 000. Six of the eight three-bit codes are used; 110 and 111 never appear in the specification. The storage elements are edge-triggered JK flip-flops with an active-low asynchronous clear, and the excitation table supplied on the last page of the paper applies.

Find. The state diagram, the state/excitation table, minimised expressions for the six flip-flop inputs and the resulting gate-level circuit; whether the two unused states return to the count; and the eight-pulse timing diagram starting from the cleared state.

State-transition diagram for the required modulo-6 sequence. The counter is autonomous — there is no external input, so every arc is unconditional and each state has exactly one successor.

Approach. Follow the five steps of the standard synchronous design procedure: state diagram, state table, excitation table using the JK entries, K-map minimisation of each $J$ and $K$ with the unused states as don’t-cares, and finally the gate-level schematic.

Build the state and excitation table (part a). For each present state read the required next state from the sequence, then convert each bit transition to JK inputs using the supplied excitation table ($0\to0:\;J=0,K=\times$; $0\to1:\;J=1,K=\times$; $1\to0:\;J=\times,K=1$; $1\to1:\;J=\times,K=0$):

State-transition table with the JK excitation required on every flip-flop (X = don’t care)
Present state Q_AQ_BQ_C	Next state Q_A⁺Q_B⁺Q_C⁺	J_A	K_A	J_B	K_B	J_C	K_C
000	010	0	X	1	X	0	X
010	100	1	X	X	1	0	X
100	101	X	0	0	X	1	X
101	011	X	1	1	X	X	0
011	001	0	X	X	1	X	0
001	000	0	X	0	X	X	1

Minimise each flip-flop input. Each of the six columns is a three-variable function of $Q_AQ_BQ_C$; the two unused states 110 and 111 are entered as don’t-cares, along with every X in the table. K-map minimisation gives$$J_A=Q_B\overline{Q_C},\qquad K_A=Q_C$$for the most significant stage. The middle stage collapses to an equivalence (XNOR) function and a permanently enabled clear, because $Q_B$ is never required to stay high for two consecutive states:$$J_B=\overline{Q_A}\,\overline{Q_C}+Q_AQ_C=\overline{Q_A\oplus Q_C},\qquad K_B=1$$and the least significant stage needs only one NOR gate:$$J_C=Q_A,\qquad K_C=\overline{Q_A}\,\overline{Q_B}=\overline{Q_A+Q_B}$$
Verify the equations reproduce the sequence. Substituting each present state into $Q^{+}=J\overline{Q}+\overline{K}Q$ for all three stages returns exactly the required successor in all six cases, so$$\boxed{\;J_A=Q_B\overline{Q_C},\;K_A=Q_C,\;J_B=\overline{Q_A\oplus Q_C},\;K_B=1,\;J_C=Q_A,\;K_C=\overline{Q_A+Q_B}\;}$$The realisation costs one 2-input AND, one XNOR and one NOR gate — three gates plus the three flip-flops.

Drawing the circuit is now mechanical: all three clock inputs are tied to the common CLK line (this is a synchronous counter, so the clock is never gated), all three clear inputs are tied to the common active-low $\overline{CLR}$ line, and the three feedback rails $Q_A,Q_B,Q_C$ run back to the input logic.

Final circuit. Feedback rails carrying Q_A (blue), Q_B (green) and Q_C (red) run beneath the flip-flops; K_B is tied HIGH, and the clock and clear lines are common to all three stages.

Check the unused states (part b). Self-starting must be judged from the minimised equations, not from the specification, because the don’t-care assignments made during minimisation are what decide what the unused states actually do. Substituting 110 into the equations gives $J_A=0,K_A=0\Rightarrow Q_A^{+}=1$; $J_B=1,K_B=1\Rightarrow Q_B^{+}=\overline{Q_B}=0$; $J_C=1,K_C=0\Rightarrow Q_C^{+}=1$, i.e. 110 → 101. Repeating for 111 gives $J_A=0,K_A=1\Rightarrow Q_A^{+}=0$, $Q_B^{+}=0$, $J_C=1\Rightarrow Q_C^{+}=1$, i.e. 111 → 001.
Conclude on self-starting. Both illegal codes map into the legal ring after a single clock, and 101 and 001 are members of the required sequence, so$$\boxed{\text{the counter is self-starting: 110}\to\text{101 and 111}\to\text{001, each in one clock}}$$No lock-out cycle exists, and the asynchronous $\overline{CLR}$ is therefore a convenience for power-up rather than a functional necessity.

Recovery of the two unused states. Neither forms a closed sub-cycle, so any power-up code joins the intended count within one clock period.

For part (c), holding $\overline{CLR}$ LOW before $t=0$ forces $Q_AQ_BQ_C=000$ asynchronously; releasing it HIGH at $t=0$ lets the first active clock edge move the counter to 010. Because the flip-flops are edge-triggered, every output changes on the same clock edge and holds until the next one.

Timing diagram for eight clock pulses after CLR′ is released. The state reached during each clock interval is printed beneath the waveforms; the pattern repeats with period six.

Read the waveforms (part c). Starting from the cleared state, the successive states are 000, 010, 100, 101, 011, 001, then 000 and 010 again. $Q_A$ is HIGH for the two intervals 100 and 101, giving one pulse per six clocks; $Q_B$ is HIGH during 010, 011 and (one interval later in the next revolution) again during 010, i.e. two separated HIGH intervals per cycle; $Q_C$ is HIGH during 101, 011 and 001, three consecutive intervals. None of the three outputs is a clean divide-by-two of another, which is the visible signature of a counter that does not follow the natural binary order.

Question 2 — final results
Part	Quantity	Result
(a)	Flip-flop A	$J_A=Q_B\overline{Q_C}$, $K_A=Q_C$
(a)	Flip-flop B	$J_B=\overline{Q_A\oplus Q_C}$, $K_B=1$
(a)	Flip-flop C	$J_C=Q_A$, $K_C=\overline{Q_A+Q_B}$
(a)	Gate count	1 AND + 1 XNOR + 1 NOR + 3 JK flip-flops
(b)	Unused states	110 → 101 and 111 → 001 — self-starting
(c)	States over 8 clocks	000, 010, 100, 101, 011, 001, 000, 010

Topic. The standard design procedure for synchronous counters, and the self-starting property.

Key relations. The JK characteristic equation $Q^{+}=J\overline{Q}+\overline{K}Q$; the JK excitation entries ($0\to0\!:\,0\times$, $0\to1\!:\,1\times$, $1\to0\!:\,\times1$, $1\to1\!:\,\times0$); and the K-map with unused states entered as don’t-cares.

Why this works. The JK excitation table is what makes the design cheap: because each transition constrains only one of the two inputs, half of every K-map is don’t-care before the unused states are even considered, and the resulting expressions are far simpler than the D-flip-flop equivalents. Entering the unused codes as don’t-cares buys further simplification but sells the behaviour of those codes to the minimiser, which is exactly why part (b) has to be answered by substituting back into the finished equations. A design that turns out not to be self-starting is repaired either by re-minimising with the offending don’t-cares forced to a chosen value, or by relying on a power-on reset through the asynchronous clear.

Common pitfall. Declaring the counter self-starting because the specification never visits 110 or 111 — the specification says nothing about them; only the minimised equations do. A second frequent error is gating the clock to skip states: in a synchronous counter the clock must reach every flip-flop ungated, and sequence control belongs entirely in the J and K logic.

Source. Mano & Ciletti, Digital Design 6th ed., §5.7–5.8 and §6.4 (synchronous counter design, unused states); Wakerly, 5th ed., §8.4.

← Question 1 Next: Question 3 →

Present state Q_AQ_BQ_C	Next state Q_A⁺Q_B⁺Q_C⁺	J_A	K_A	J_B	K_B	J_C	K_C
000	010	0	X	1	X	0	X
010	100	1	X	X	1	0	X
100	101	X	0	0	X	1	X
101	011	X	1	1	X	X	0
011	001	0	X	X	1	X	0
001	000	0	X	0	X	X	1

Part	Quantity	Result
(a)	Flip-flop A	\(J_A=Q_B\overline{Q_C}\), \(K_A=Q_C\)
(a)	Flip-flop B	\(J_B=\overline{Q_A\oplus Q_C}\), \(K_B=1\)
(a)	Flip-flop C	\(J_C=Q_A\), \(K_C=\overline{Q_A+Q_B}\)
(a)	Gate count	1 AND + 1 XNOR + 1 NOR + 3 JK flip-flops
(b)	Unused states	110 → 101 and 111 → 001 — self-starting
(c)	States over 8 clocks	000, 010, 100, 101, 011, 001, 000, 010

Present state Q_AQ_BQ_C	Next state Q_A⁺Q_B⁺Q_C⁺	J_A	K_A	J_B	K_B	J_C	K_C
000	010	0	X	1	X	0	X
010	100	1	X	X	1	0	X
100	101	X	0	0	X	1	X
101	011	X	1	1	X	X	0
011	001	0	X	X	1	X	0
001	000	0	X	0	X	X	1

Present state Q_AQ_BQ_C	Next state Q_A⁺Q_B⁺Q_C⁺	J_A	K_A	J_B	K_B	J_C	K_C
000	010	0	X	1	X	0	X
010	100	1	X	X	1	0	X
100	101	X	0	0	X	1	X
101	011	X	1	1	X	X	0
011	001	0	X	X	1	X	0
001	000	0	X	0	X	X	1