Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Finite state machines and ASM charts

Finite state machines (Moore and Mealy) and ASM charts: definitions, design steps, state reduction, state assignment, conversion to flip-flop logic, and example designs (sequence detector and ASM controller).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Finite state machines (FSMs) model digital systems whose outputs depend on the present input and on the history of inputs stored as states. Engineers use FSMs to design controllers, protocol handlers, sequence detectors, counters, and the control part of a CPU; Algorithmic State Machine (ASM) charts give a structured, readable way to specify such controllers before implementing logic.

Key ideas

  • Moore machine: an FSM where each state's outputs depend only on the current state. Exact definition: Output Z(t) = f(State(t)). When drawing, label each state circle with state name and output value(s) beneath (e.g., S0 / Z=0).

  • Mealy machine: an FSM where outputs depend on the current state and current input. Exact definition: Output Z(t) = f(State(t), Input(t)). When drawing transitions, label arrows with input/output pairs (e.g., x=1 / z=0). Note: because outputs depend directly on inputs, Mealy outputs can change within a clock cycle when inputs change; to avoid glitches in synchronous systems, designers often register Mealy outputs.

  • State diagram: directed graph with nodes for states and labeled edges for transitions. For Mealy machines, label edges as input/output. For Moore machines, label edges with input only and write outputs inside state nodes.

  • State table (transition table): tabular form listing present state, input combinations, next state, and outputs. Universities expect both the truth-table style and the tabular form with binary-encoded states. Include handling of unused/illegal state encodings: either list them with safe next states or mark them as don't-cares for simplification, and specify a reset that forces a known start state.

  • ASM chart (Algorithmic State Machine chart): structured graphical notation combining state boxes (clusters of actions), decision diamonds (conditions on inputs), and conditional outputs. Draw a sequence of boxes (state actions) connected by vertical and horizontal arrows; annotate decisions with diamonds and next-state arrows.

  • Design procedure (common exam algorithm): (1) Specify behavior (problem statement). (2) Choose machine type (Moore/Mealy). (3) Draw state diagram or ASM chart. (4) Create state table. (5) Reduce states if possible (state equivalence). (6) Assign binary codes to states (state assignment). (7) Choose flip-flop type and derive excitation equations. (8) Simplify boolean equations and implement with gates. (9) Verify with timing/trace. Also define the reset state and ensure any illegal/unreachable encodings transition to a safe state.

  • State minimization (partition/refinement method): initial partition groups states with same outputs (for Moore) or same output mapping (for Mealy). Iteratively refine: states p and q are equivalent if for every input they transition to the same partition. Continue until no change. Draw: a table listing partitions per iteration.

  • State assignment: map each state to a unique binary vector. Common strategies: binary (simple), one-hot (one flip-flop per state), and Gray-code for reducing bit changes. Choice affects circuit complexity.

  • Flip-flop excitation: to implement next-state logic, convert desired next-state bits to required flip-flop inputs using excitation tables for chosen flip-flop type (D, JK, T). Universities expect you to show the excitation table and derive input equations.

  • ASM to implementation: each ASM state becomes a binary-encoded state; outputs and micro-operations in ASM translate to combinational outputs and control signals in logic equations.

Formulas

NS = f(PS, X) — NS is next-state vector, PS is present-state vector, X is input vector. Units: unitless; applies to synchronous FSMs.

Z_Moore = g(PS) — output for Moore machine depends only on present state. Z unitless.

Z_Mealy = h(PS, X) — output for Mealy machine depends on present state and input. Z unitless.

D_i = NS_i — for D flip-flop i, the D input equals the desired next-state bit NS_i. Applies when using edge-triggered D flip-flops.

T_i = NS_i XOR PS_i — for T flip-flop, toggle when next-state differs from present-state. T unitless; applies when using T flip-flops.

J_i K_i excitation relation: choose J,K values from the JK excitation table so that PS -> NS. For a single bit: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0. Units unitless; used for JK flip-flops.

(Note: all symbols are binary signals, unitless digital logic levels.)

Worked examples

Example 1 — Design a 101 sequence detector (overlapping allowed), Mealy machine, implemented with D flip-flops. Problem: Input x streams bits; output z should be 1 when the last three bits seen are 101 (overlap allowed). Steps:

  1. Behavior and machine type: choose Mealy because it often needs fewer states.
  2. Draw state diagram (describe drawing): draw three states S0, S1, S2 in circles.
    • S0: no relevant prefix seen (start). From S0: if x=1 go to S1 (label arrow x=1 / z=0); if x=0 stay S0 (x=0 / z=0).
    • S1: prefix '1' seen. From S1: if x=0 go to S2 (x=0 / z=0); if x=1 stay S1 (x=1 / z=0).
    • S2: prefix '10' seen. From S2: if x=1 go to S1 (x=1 / z=1) because 101 detected; if x=0 go to S0 (x=0 / z=0).
  3. State table: list PS (S0,S1,S2), encode states (binary): S0=00, S1=01, S2=10 (use 2 bits: Q1 Q0). Table columns: PS, x=0: NS, z ; x=1: NS, z.
    • PS=00: x0 -> NS=00,z=0 ; x1-> NS=01,z=0
    • PS=01: x0 -> NS=10,z=0 ; x1-> NS=01,z=0
    • PS=10: x0 -> NS=00,z=0 ; x1-> NS=01,z=1
  4. Derive next-state bits NS1, NS0 and output z as boolean expressions from table using Karnaugh maps (describe process): make K-maps for NS1(Q1+), NS0(Q0+), and z.
    • From the table, the only defined case with NS1=1 is PS=01 and x=0, so NS1 = Q1'·Q0·x'.
    • From the table, NS0=1 whenever x=1 (for all defined PS), so NS0 = x. Treat unused state 11 as a don't-care or map it to a safe next state; the expression NS0=x remains valid.
    • Output z = Q1·Q0'·x (from the table, z=1 only when PS=10 and x=1).
  5. Implement with two D flip-flops: set D1 = NS1, D0 = NS0.
  6. Verify by tracing: input sequence 1 0 1: start 00 -> x=1 -> 01, x=0 -> 10, x=1 -> 01 and z=1 produced at last transition. Answer: final hardware: two D flip-flops with inputs D1, D0 as derived and z = Q1·Q0'·x. (Students must show K-maps in exam.)

Note: I marked simplifications above that you should verify by re-doing the K-maps—the expected exam step is the K-map work.

Example 2 — ASM chart for a simple traffic light controller with pedestrian request. Problem: Main road has Green->Yellow->Red cycle; pedestrian button when pressed causes the next red to include pedestrian Walk signal for one cycle. Show ASM and describe logic. Steps:

  1. Draw ASM: make three state boxes labeled Green, Yellow, Red. Inside each box list outputs: e.g., Green: MainGreen=1, PedDon'tWalk=1. From Green box draw timed transition (after timer) to decision diamond: if PedRequest=1 then go to Yellow then Red with Walk; else go Yellow then Red without Walk. Decision diamond labelled PedRequest? with arrows labeled yes/no. In Red state use sub-action: if came from PedRequest then PedWalk=1 for duration; otherwise PedWalk=0.
  2. Convert to states and table: list states G, Y, Rn (no-walk red), Rw (walk red). Encode states, make transition table, derive next-state logic and outputs. For Moore style outputs are inside states; for ASM you may combine micro-operations (set timers/clear button) as outputs.
  3. Implementation notes: use one-hot for readability (4 flip-flops), or binary with 2 bits (need 3 or more states). Derive equations as in Example 1. This example shows how ASM helps structure decisions and outputs before logic derivation.

Common mistakes

  • Forgetting overlapping sequences for detectors (e.g., 101 overlapping must allow last '1' to be start of next match).
  • Wrong excitation mapping: using next-state bit as D input with JK or T flip-flops without converting via excitation table.
  • Poor state assignment: random binary codes can increase gate count; for counters or shift-like FSMs use Gray or one-hot as exam may ask.
  • Not drawing or labelling the clock and reset signals when showing final implementation.

For your exam

Typical question types: definition and short notes (define FSM, Moore vs Mealy, ASM chart), design problem (give specification, draw ASM or state diagram, minimize states, derive equations), trace/verification (given FSM and input sequence, trace states and outputs), conversion (ASM to state table to logic), and short derivations (prove equivalence of two state machines). What full-marks answers include:

  • Clear statement of machine type and assumptions (synchronous, flip-flop type).
  • Correct state diagram or ASM with labels (states, transitions, inputs/outputs). Describe exactly what to draw: circles for states labelled S0 etc, arrows labelled with input/output pairs for Mealy or input only for Moore. For ASM: boxes with outputs listed, decision diamonds labelled, and annotated timing arrows.
  • Complete state table, correct minimization steps (if asked), explicit state encoding, excitation equations and K-maps or Boolean simplification, final gate-level expressions, and a brief timing/reset note. If asked for trace, show each clock step with PS, input, NS and outputs.

Quick check

  1. Define Mealy machine in one sentence.
  2. For a Moore machine, can output change in the middle of a clock cycle due to input change? (assume synchronous outputs)
  3. Which state assignment (binary or one-hot) uses more flip-flops but simplifies next-state logic? Answers: 1) An FSM whose outputs depend on present state and current inputs. 2) No — Moore outputs depend only on state and change only on clock edge when state changes (synchronous assumption). 3) One-hot.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?