2IC30 · resource
FSM crashcourse
How to go from a written scenario to gates and flip-flops.
Q3 = ~18 pts. Like Q4 it follows a fixed design flow. Given a Moore machine you (1) encode the states, (2) build the output + next-state tables, (3) Karnaugh each bit into an equation, (4) wire two D-flip-flops. This page walks the real 2026 Q3 end to end. Drill more in the FSM Trainer.
📷 The actual 2026 Q3 (verbatim)
The exact wording from the official 2026 exam, with the machine diagram and the model-solution scans. Try each part on paper first, then follow the worked steps below. Note: Q3 contains two unrelated machines — Q3a (below) and the Q3b–d machine (further down).
Q3a — 6 pt · its OWN machine
⚠ Q3a is a standalone design task — a different machine from Q3b/c/d (inputs k,b,o,c and a single output m, vs c,d → m,n). Just draw the diagram + mark the start state; no encoding/tables/circuit needed here.
Controller for an autonomous warehouse patrol robot. Inputs: k (docked), b (battery full), o (obstacle), c (charge complete). Output m (move). Idle while docked; patrol when battery full; stop & wait for obstacles; on returning, dock and charge. Fault if charge complete but battery not full (exit only when full). Name states meaningfully, mark the start state, follow lecture conventions for inputs vs outputs.
The Q3b–d machine — a different, given Moore machine
Parts b–d all refer to this given Moore machine (the exam states it is unrelated to Q3a): two inputs c, d, two outputs m, n. If the inputs on a state are not explicitly drawn, the machine stays in that state.
Q3b — 2 pt
Give the output truth table. Encoding A:00, B:01, C:11, D:10. Outputs m and n. (Worked in §3 below.)
Q3c — 4 pt
Give the state transition table. Encoding A:00, B:01, C:11, D:10. Current (s,t), inputs (c,d), next (s_new,t_new). (Worked in §4 below.)
Q3d — 4 pt
Given: n=(s∧¬t)∨(¬t∧¬s), m=s∧t, s_new=(¬s∧¬c∧d)∨(s∧d)∨(s∧¬t∧¬d), t_new=(c∧d)∨(¬s∧c)∨(¬t∧d). Draw the circuit using clocked D-flip-flops (block form; show D, Q, Q̄, CLK).
⚠ Q3d prints its own equations to draw (a separate given machine — note its m=s∧t, n=¬t differ from the Q3b/Q3c machine). The worked steps below instead derive the equations from the Q3b/Q3c tables, which is the skill examiners test.
0 · What you are building
A Moore machine: outputs depend on the state only (written inside the state, not on transitions). You implement it as:
0 · What you are building
- State register = one clocked D-flip-flop per state bit. 4 states → ⌈log₂4⌉ = 2 FFs, call their outputs s and t.
- Next-state logic = combinational gates computing s_new, t_new from the current s,t + inputs → fed into the D inputs.
- Output logic = combinational gates computing the outputs from s,t only.
- Feedback: each FF's Q output (the current s,t) loops back into the next-state logic. On every clock edge the D values latch → the machine steps.
⚠ s,t are produced BY the flip-flops AND feed back IN to decide the next s,t. The D input gets s_new/t_new — never the current value.
1 · The universal recipe
- Encode the states — use the encoding the question dictates.
- Output table: one row per state → read each output off the state (Moore).
- Next-state table: one row per (state × every input) → follow the arrows.
- Karnaugh each output and each next-state bit separately → minimal equation.
- Draw: 2 D-FFs + the next-state logic on the D inputs + output logic, close the feedback loop.
2 · Encode the states (2026 Q3b/c)
The 2026 paper dictates this encoding (note it is Gray-ordered A→B→C→D, not plain binary count) with bits (s,t):
| State | s | t |
|---|---|---|
| A | 0 | 0 |
| B | 0 | 1 |
| C | 1 | 1 |
| D | 1 | 0 |
Two state bits → two flip-flops. s is the high bit, t the low bit.
3 · Output table → output equations
2026 Q3b gives the outputs m, n per state. Rewrite it in (s,t) order:
| State | s | t | m | n |
|---|---|---|---|---|
| A | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 0 | 1 |
| C | 1 | 1 | 1 | 1 |
| D | 1 | 0 | 1 | 0 |
K-map for m (only 2 vars s,t):
| Column 1 | t=0 | t=1 |
|---|---|---|
| s=0 | 1 | 0 |
| s=1 | 1 | 1 |
Only the cell (s=0,t=1) is 0 → m = 0 exactly there → m = s ∨ ¬t.
K-map for n:
| Column 1 | t=0 | t=1 |
|---|---|---|
| s=0 | 1 | 1 |
| s=1 | 0 | 1 |
Only (s=1,t=0) is 0 → n = ¬s ∨ t.
4 · Next-state table (2026 Q3c)
Inputs c,d. 4 states × 4 input combos = 16 rows. Each row: follow the arrow, write the destination code (s',t').
| s | t | c | d | → | s' | t' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | A | 0 | 0 |
| 0 | 0 | 0 | 1 | A | 0 | 0 |
| 0 | 0 | 1 | 0 | A | 0 | 0 |
| 0 | 0 | 1 | 1 | B | 0 | 1 |
| 0 | 1 | 0 | 0 | B | 0 | 1 |
| 0 | 1 | 0 | 1 | D | 1 | 0 |
| 0 | 1 | 1 | 0 | C | 1 | 1 |
| 0 | 1 | 1 | 1 | B | 0 | 1 |
| 1 | 0 | 0 | 0 | A | 0 | 0 |
| 1 | 0 | 0 | 1 | D | 1 | 0 |
| 1 | 0 | 1 | 0 | D | 1 | 0 |
| 1 | 0 | 1 | 1 | D | 1 | 0 |
| 1 | 1 | 0 | 0 | C | 1 | 1 |
| 1 | 1 | 0 | 1 | C | 1 | 1 |
| 1 | 1 | 1 | 0 | C | 1 | 1 |
| 1 | 1 | 1 | 1 | B | 0 | 1 |
No arrow drawn for an input → the machine stays (s',t' = s,t). Unused state codes → mark don't-care (X) to grow your K-map groups.
5 · Karnaugh each next-state bit
Split the table into one map per output bit. Rows = s,t; columns = c,d in Gray order 00,01,11,10.
K-map for s' (plot the s' column):
| st \ cd | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 0 | 0 |
| 01 | 0 | 1 | 0 | 1 |
| 11 | 1 | 1 | 0 | 1 |
| 10 | 0 | 1 | 1 | 1 |
Cover the 1s with the largest blocks. One valid minimal cover:
(Equivalently (s∨t)∧(c⊕d) ∨ (s∧t∧¬c∧¬d) ∨ (s∧¬t∧c∧d) if XOR gates are allowed.)
K-map for t' (plot the t' column):
s' = (s∧t∧¬c) ∨ (s∧¬t∧c) ∨ (s∧¬c∧d) ∨ (t∧¬c∧d) ∨ (t∧c∧¬d)
| st \ cd | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 0 |
| 01 | 1 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
The whole st=11 row is 1 → s∧t. The t∧¬d column-pair + the lone ¬s∧c∧d cells finish it:
6 · The four equations (the answer)
m = s ∨ ¬t (output) n = ¬s ∨ t (output) s' = (s∧t∧¬c) ∨ (s∧¬t∧c) ∨ (s∧¬c∧d) ∨ (t∧¬c∧d) ∨ (t∧c∧¬d) (D input of s-FF) t' = (s∧t) ∨ (t∧¬d) ∨ (¬s∧c∧d) (D input of t-FF)
All four verified against every one of the 16 table rows. s'→D of the s flip-flop, t'→D of the t flip-flop.
⚠ On the real paper, Q3d sometimes hands you equations to draw — those describe a different given machine. Here we derived ours straight from the Q3b/Q3c tables, which is the skill examiners test.
7 · Draw the circuit (clocked D-FFs)
Two D-flip-flops form the state register. The next-state logic drives their D inputs; the Q outputs feed back. Block form:
┌─────────────────────────┐ c ───►│ │── s' ──►┌───┐ d ───►│ next-state logic │ │ D Q│──┬──► s ┌───►│ (s' , t' equations) │── t' ─┐ │CLK│ │ │┌──►│ │ │ └───┘ │ ││ └─────────────────────────┘ │ │ ││ ▼ │ ││ ┌───┐ │ ││ │ D Q│──┬──┼─► t ││ │CLK│ │ │ ││ └───┘ │ │ │└──────────────── t feedback ──────────────┘ │ └─────────────────── s feedback ───────────────┘ outputs: m = s ∨ ¬t n = ¬s ∨ t (from s,t only)
7 · Draw the circuit (clocked D-FFs)
- One shared CLK to both FFs (synchronous).
- Q̄ pins are handy: a needed ¬t (in m) can come straight off the t-FF's Q̄ instead of an extra inverter.
- The D inputs carry s'/t' (next), the Q outputs carry the current s,t — that loop IS the memory.
8 · Point-losers checklist
- ❌ Putting Moore outputs on transitions (they depend on STATE only).
- ❌ Using your own encoding when the question dictates one — copy theirs exactly.
- ❌ Missing rows: every (state × input) combination needs a next state (use the "stay" convention).
- ❌ Feeding the CURRENT state into the D input — D gets s'/t' (the NEXT state).
- ❌ Forgetting the feedback loop Q → next-state logic.
- ❌ Not minimising — group the largest power-of-two blocks; use don't-cares for unused codes.
8 · Point-losers checklist
Drill it now in the FSM Trainer →