Question 1 of 5: Synchronous Counter with a Non-Binary Repeating Sequence

Question 1: Synchronous Counter with a Non-Binary Repeating Sequence (25 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 4-bit state (Q3 Q2 Q1 Q0) must cycle 0→1→3→5→7→9→11→13→0… on positive clock edges, using D-type flip-flops. The eight states NOT in that list (2, 4, 6, 8, 10, 12, 14, 15) are unused and must transition to 0000 on the very next clock pulse — that is an explicit design requirement, not a “don’t care,” so all 16 rows of the state table carry a specified next state.

Find. (a) the complete state table; (b) minimized next-state equations D3, D2, D1, D0; (c) the flip-flop + combinational-logic circuit.

Approach. Tabulate all 16 present-state rows (8 from the sequence, 8 unused → 0000), read D_i = Q_i⁺ directly off each row (a D flip-flop’s input equals its desired next output), then K-map/Boolean-minimize each of the four next-state functions over all 16 specified rows.

1. Part (b) — read D_i off the table and group 1-cells. Because a D flip-flop’s next state equals its D input (D_i = Q_i⁺), each column of the state table above IS the truth table for that D-equation. K-map grouping the 1-cells of each column over all 16 rows gives:$$D_3 = Q_3'Q_2Q_1Q_0 + Q_3Q_2'Q_0$$Two prime implicants: the first fires only at state 7 (0111→1001, so D3 must go high), the second covers states 9 and 11 (1001, 1011 both have Q3=1, Q2=0 and both need D3=1).
2. D2. $$D_2 = Q_3'Q_2Q_1'Q_0 + Q_2'Q_1Q_0$$ The first term is state 5 alone (0101→0111); the second covers states 1 and 3 (0001, 0011), both needing D2=1 on the next edge.
3. D1. $$D_1 = Q_2'Q_1'Q_0 + Q_3'Q_1'Q_0$$ covering states 1, 5 and 9 — every sequence state whose Q1=0 while Q0=1 needs D1=1 on the next edge (states 3, 7, 11, 13 already have Q1=1 and fall out of this group).
4. D0. Every state in the 8-value sequence is odd and every unused state is even, so $$D_0 = Q_3'Q_0 + Q_3'Q_2'Q_1' + Q_2'Q_0$$ $$\boxed{D_3,\,D_2,\,D_1,\,D_0 \text{ as above}}$$ reproduces the full 16-row table exactly.
5. Part (c) — implement. Four positive-edge-triggered D flip-flops hold Q3…Q0; a shared combinational-logic block realizes the four boxed equations above from the current Q3…Q0 and feeds D3…D0 back into the flip-flops on the next active edge (Fig. Q1c).