EVEN/ODD Parity-Tracking FSM: 04-BS-8, December 2015, Q4

Question 4: EVEN/ODD Parity-Tracking FSM (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. Synchronous inputs RESET (async clear), ENABLE, SERIAL_DATA; outputs EVEN, ODD must track the running parity of 1s seen while ENABLE was asserted, since the last RESET.

Find. (a) State diagram and table; (b) minimum flip-flop count, next-state equations, and the FSM circuit.

Approach. Only two conditions can ever be true — "even number of 1s counted so far" or "odd" — so a single-bit Moore machine suffices; toggle that bit only when ENABLE is asserted and SERIAL_DATA=1, hold it otherwise, and force it to the EVEN state on RESET.

Part (a) — states and table. Two states are necessary and sufficient: $S_0$ (EVEN, $Q{=}0$) and $S_1$ (ODD, $Q{=}1$), with $S_0$ the reset state (0 ones seen is even). A transition occurs only when $\text{ENABLE}\cdot\text{SERIAL\_DATA}=1$ (a counted "1" bit flips the parity); otherwise the state holds.

Present state	EN	SD	Next state	EVEN	ODD
$S_0$ (Q=0)	0	x	$S_0$	1	0
$S_0$ (Q=0)	1	0	$S_0$	1	0
$S_0$ (Q=0)	1	1	$S_1$	1	0
$S_1$ (Q=1)	0	x	$S_1$	0	1
$S_1$ (Q=1)	1	0	$S_1$	0	1
$S_1$ (Q=1)	1	1	$S_0$	0	1

Moore state diagram: EVEN/ODD toggles only on a counted 1-bit ($\text{EN}\cdot\text{SD}{=}1$); RESET (not shown as an edge, applies asynchronously from any state) forces $S_0$.

Part (b) — minimum flip-flops and next-state equation. One D flip-flop is the minimum (2 states $\Rightarrow \lceil\log_2 2\rceil=1$ bit). From the state table, $Q^+ = 1$ exactly on rows where a toggle occurs, i.e. whenever $\text{EN}\cdot\text{SD}=1$ and the current $Q$ differs from the next $Q$ — which is precisely the toggle relation $Q^+=Q\oplus(\text{EN}\cdot\text{SD})$. Wiring: an AND gate combines ENABLE and SERIAL\_DATA, an XOR gate combines that product with the flip-flop's own $Q$ output (fed back), and the XOR output drives $D$; RESET ties directly to the flip-flop's asynchronous clear. Outputs are combinational: $\text{ODD}=Q$, $\text{EVEN}=\overline{Q}$ (one inverter).

Minimum FSM hardware: 1 D flip-flop, 1 AND gate, 1 XOR gate (feedback from Q), 1 inverter for EVEN.

Quantity	Result
States / flip-flops	2 states, 1 D flip-flop (minimum)
Next-state equation	$D = Q\oplus(\text{EN}\cdot\text{SD})$
Outputs	$\text{ODD}=Q,\ \text{EVEN}=\overline{Q}$
Gate count	1 AND + 1 XOR + 1 NOT (+ 1 D-FF)

Concept & Theory

Topic. Minimum-state Moore FSM design for serial parity tracking.

Key relations. Minimum flip-flop count $=\lceil\log_2(\text{number of states})\rceil$; toggle-on-condition next-state form $Q^+=Q\oplus(\text{condition})$; D flip-flop excitation ($D=Q^+$ directly).

Why this works. Running parity is inherently a 1-bit quantity — it can only ever be "even so far" or "odd so far" — so no amount of additional state can reduce the flip-flop count below one; recognizing the toggle-on-condition pattern converts a state table that looks like it needs a K-map into a single XOR, since XOR is exactly the Boolean "flip A if B" operator.

Common pitfall. Adding a counter (multiple bits) to literally count the 1s instead of just tracking their parity — the question only asks for even/odd, not the count itself, so a full counter wastes flip-flops.

Source. Mano & Ciletti, Digital Design, Ch. 5 (Moore/Mealy FSM design, state minimization).

Question 4 of 5: EVEN/ODD Parity-Tracking FSM

Question 4: EVEN/ODD Parity-Tracking FSM (25 marks)