Finite state machine design

In short

A finite state machine is a clocked sequential circuit whose behaviour is described by a finite set of states, a next-state function and an output function - it remembers "where it is" in a sequence rather than just the present input. FSM design is the formal procedure that converts a word statement (detect the pattern 1011, control a traffic signal, run a UART) into a state diagram, a state table, a state assignment and finally flip-flops plus combinational logic. It is the highest-scoring sequential-logic area in GATE EC/EE/CS, and in digital-design interviews at Intel, Qualcomm, Texas Instruments, Samsung, Nvidia, Micron, Bosch, Tessolve, Sasken, BEL, ISRO and DRDO almost every candidate is asked to draw one FSM on the whiteboard. Every protocol controller, arbiter, memory controller and datapath controller inside an ASIC or FPGA is an FSM.

Explained

Definition, model and the two machine types

• An FSM is the 6-tuple (I, O, S, S₀, δ, λ): input alphabet, output alphabet, finite state set, reset state, next-state function δ, output function λ.
• Synchronous (clocked) FSM: state changes only at an active clock edge; the present state is held in flip-flops (the *state register*), and two combinational blocks compute next state and output. This is what universities and industry mean by "FSM design" unless asked otherwise.
• Moore machine: output depends on the present state only - λ(S). Output is written inside the state bubble.
• Mealy machine: output depends on present state and present input - λ(S, I). Output is written on the arc as input/output.
• Medvedev machine: a special Moore machine where the output *is* the state register bits - zero output logic, fastest, used for one-hot control signals.
• Registered (pipelined) Mealy: Mealy output passed through a flip-flop to remove glitches; costs one clock of latency.
• Completely specified machine defines a next state and output for every (state, input) pair; an incompletely specified machine has don't-cares, which allows *compatible* states to be merged (merger graph / compatibility classes).
• Deterministic FSM: exactly one next state per input. Non-deterministic machines are a theory-of-computation idea, not a hardware one.
• Asynchronous (fundamental-mode) FSM: no clock; described by a flow table, suffers critical races and essential hazards, needs one input change at a time. Mentioned in syllabi but rarely built today.

Representations: state diagram, state table, ASM chart

• State diagram (state transition graph): bubbles = states, directed arcs = transitions labelled with the input condition (Mealy adds /output). Every state must have arcs covering all input combinations, and all must sum to a complete, non-overlapping set.
• State table / state transition table: rows = present states, columns = input combinations, entries = next state (and output for Mealy). The *transition table* is the same thing after binary codes are substituted.
• ASM (Algorithmic State Machine) chart: a flowchart-like notation for bigger controllers -
  • State box (rectangle): one state, with unconditional Moore outputs and register transfers.
  • Decision box (diamond): tests an input, no time cost.
  • Conditional output box (oval): Mealy output, active only on that path.
  • One ASM block = one state box plus the decision/conditional boxes under it = one clock cycle.
• Timing diagram: verifies that the output appears in the intended cycle; the classic check of a Moore detector is that its output comes one cycle later than a Mealy detector's.

The nine-step classical design procedure

1. Read the specification - fix clock, inputs, outputs, reset, whether patterns may overlap, and Moore or Mealy.
2. Draw the state diagram - one state per "amount of useful history remembered". Name states by the input prefix matched (∅, 1, 10, 101 …).
3. Write the state table.
4. State reduction - remove equivalent/redundant states (next section).
5. State assignment - give each state a binary code; decide binary / Gray / one-hot.
6. Choose the flip-flop (D in all modern synthesis; JK/T/SR appear in exams).
7. Form the excitation (transition) table - for each flip-flop write the required input from the present → next state pair: D = next state; T = Q ⊕ Q⁺; JK from 0→0: J=0,K=X; 0→1: J=1,K=X; 1→0: J=X,K=1; 1→1: J=X,K=0.
8. Minimise each flip-flop input and each output by K-map/QM, using unused states as don't-cares if a *minimal* machine is wanted.
9. Draw the circuit and verify by simulation and by walking the original sequence through it.

State reduction and machine equivalence

• Equivalent states: two states are equivalent if, for *every* possible input sequence, they give the same output sequence. Equivalent states can be merged without changing external behaviour.
• Equivalence partitioning (the exam method):
  1. P₁ - partition states by output (Moore) or by output row (Mealy).
  2. Split any group whose members send some input to different groups.
  3. Repeat until a partition repeats; each final block becomes one state of the reduced machine.
• Implication chart (merger table): a triangular table of state pairs; cross out pairs with different outputs, enter the implied pairs for the rest, and iterate the crossing-out. Surviving pairs are equivalent. For incompletely specified machines the same chart gives compatible pairs, and a minimum closed cover of maximal compatibles gives the minimum machine.
• A fully reduced machine is the minimal machine; it is unique up to state renaming for completely specified machines, not unique for incompletely specified ones.
• Moore ↔ Mealy: Moore → Mealy keeps the same number of states (move the state's output onto all its incoming arcs). Mealy → Moore may need more states - a Mealy state carrying k different outputs splits into k states, so at most (states × distinct outputs).
• Reduction saves flip-flops only when it crosses a power of two (6 → 4 states saves one flip-flop; 6 → 5 saves none).

State assignment, unused states and encoding styles

• Flip-flop count: n = ⌈log₂S⌉ for binary encoding; the 2ⁿ − S leftover codes are unused (invalid) states.
• Binary (sequential) encoding: fewest flip-flops, most next-state logic, longer critical path - good for CPLDs and area-critical ASIC blocks.
• Gray encoding: adjacent states differ in one bit - fewer simultaneous transitions, so less switching power and fewer output glitches; useful when the FSM walks a fixed sequence.
• One-hot encoding: one flip-flop per state, exactly one high. Next-state logic for each flip-flop is just the OR of its incoming arc conditions, so logic is shallow and fast; natural fit for FPGAs, which are flip-flop-rich. Output decoding is free (Medvedev).
• Almost one-hot / Johnson: variants trading flip-flops against decode logic.
• Assignment guidelines (Armstrong/Humphrey rules) when flip-flops are scarce: give adjacent codes to (i) states with the same next state, (ii) states that are the next states of a common state, (iii) states with the same output. Reset state is normally all-zeros so an asynchronous reset or power-up clears it.
• Unused-state policy - an exam-and-interview favourite:
  • *Minimal FSM:* treat unused codes as don't-care - smallest logic, but a single-event upset can lock the machine in an invalid state.
  • *Safe FSM:* explicitly route every unused code to the reset state. Costs gates, but required in automotive (ISO 26262) and aerospace work; FPGA synthesis tools expose it as a "safe state machine" option.

Timing, inputs and practical issues

• Maximum clock frequency is set by the longest register-to-register path: clock-to-Q of the state flip-flops + worst-case next-state logic delay + setup time (+ clock skew). The output path to a primary output or to another block has its own check.
• Hold check: the fastest path must still be slower than the hold requirement - fails only with very short combinational paths or large clock skew at the capture flip-flop.
• Asynchronous inputs (push-buttons, cross-clock signals) must be synchronised by a two-flip-flop synchroniser before they reach the FSM; otherwise metastability can make different state bits sample different values and the machine jumps to an invalid state. Debounce mechanical switches too.
• Mealy outputs are not glitch-free - they follow the input asynchronously within the cycle, so they must not drive an edge-sensitive load (clock, write-enable) directly. Use Moore or a registered Mealy output for such control lines.
• Output glitches in binary-coded Moore machines come from multi-bit state changes; one-hot or Gray coding avoids them.
• FSM decomposition: split a large controller into a main FSM plus counters/timers/shift registers rather than creating hundreds of states. "Wait 2 seconds" is a counter with a done flag, not 2 crore states.
• FSMD / controller-datapath partition: the FSM issues control signals (load, shift, add, mux-select) and reads status flags (zero, carry, done) from the datapath - the standard architecture for multipliers, dividers, CORDIC blocks and protocol engines.
• Limitations: state explosion in complex protocols, no arithmetic memory beyond the state, and poor fit for data-dominated algorithms - which is where microprogrammed control or a soft processor is used instead.
• In HDL, an FSM is coded as a state register block plus a combinational next-state block (the "two-process" style); enumerated/parameterised state names and a default/others branch let the synthesiser recognise and encode the FSM. Language detail belongs to the HDL topic.

Key points

• FSM - sequential circuit with finite states; outputs depend on history captured in the state register.
• Moore - output = f(state); stable, glitch-free, one cycle of latency; needs ≥ as many states as Mealy.
• Mealy - output = f(state, input); faster response, usually fewer states, output can glitch.
• k-bit overlapping sequence detector - Mealy needs k states, Moore needs k + 1.
• State diagram completeness - every state must account for all 2^m input combinations, with no overlap.
• Flip-flop count - n = ⌈log₂S⌉ for binary; n = S for one-hot.
• Excitation table - maps present → next state onto flip-flop inputs; D = Q⁺, T = Q ⊕ Q⁺.
• Equivalence partitioning - group by output, split on differing next-state groups, iterate to a stable partition.
• Implication chart - systematic pairwise test for equivalent (or compatible) states.
• Minimal machine - unique for completely specified machines, not for incompletely specified ones.
• One-hot - shallow OR-based next-state logic, free output decode, FPGA-friendly, costs flip-flops.
• Gray/adjacent coding - single-bit transitions, lower power and fewer output glitches.
• Unused states - don't-care gives minimum logic; routing them to reset gives a safe FSM.
• fmax - limited by t_cq + t_comb + t_su (+ skew); reduce by one-hot coding or pipelining the output.
• Asynchronous input - must pass a two-stage synchroniser; never feed a raw button into state logic.
• Mealy output - never use directly as a clock or write pulse; register it.
• Decomposition - timing and counting go to counters with done flags, not to extra states.
• FSMD - controller FSM plus datapath, linked by control signals and status flags.

Formulas and examples

Example 1 - Moore "101" overlapping detector, with D and then JK flip-flops. States: S0 = nothing, S1 = "1", S2 = "10", S3 = "101" (Z = 1 only in S3). Codes S0=00, S1=01, S2=10, S3=11 (Q₁Q₀).

Transition table for Q₁⁺ over (Q₁Q₀x): 1 at 010, 101, 110 only.

• K-map grouping: 010 + 110 → Q₀x′ ; 101 stands alone → Q₁Q₀′x.
• D₁ = Q₀x′ + Q₁Q₀′x, D₀ = x (Q₀⁺ is 1 exactly when x = 1), Z = Q₁Q₀.
• Cost: 2 flip-flops, 2 AND + 1 OR + 2 inverters for the next-state logic, 1 AND for the output.
• Same machine with JK flip-flops, from the excitation rules:
  • Q₁: set required at 010 → J₁ = Q₀x′; reset required at 100 and 111 → K₁ = Q₀′x′ + Q₀x = Q₀ ⊙ x (XNOR).
  • Q₀: J₀ = x, K₀ = x′.
• Check with input 1 0 1 0 1 from reset: S0→S1→S2→S3(Z=1)→S2→S3(Z=1) - two detections from overlapping patterns, correct.

Example 2 - Mealy "1011" overlapping detector. States A = ∅, B = "1", C = "10", D = "101". After 1011 the longest useful suffix is "1", so D on x=1 outputs 1 and goes to B.

• With A=00, B=01, C=10, D=11 the next-state table is identical to Example 1, so D₁ = Q₀x′ + Q₁Q₀′x, D₀ = x, and the Mealy output is Z = Q₁Q₀x - 4 states, 2 flip-flops.
• A Moore detector for the same 4-bit pattern needs 5 states (k + 1) and asserts Z one clock later. This is the standard "Mealy saves a state and a cycle, Moore gives a clean output" answer.

Example 3 - state reduction by equivalence partitioning.

• By inspection C and E have identical rows (A, D, 0) → C ≡ E; replace E by C, so D's 0-successor becomes C.
• Formal check on the reduced table {A,B,C,D}: P₁ = (A B C)(D) by output. On x=1: A→B (grp 1), B→B (grp 1), C→D (grp 2) → split: (A B)(C)(D). On x=0: A→A (same block), B→C (different block) → split: (A)(B)(C)(D).
• Result: 5 states reduce to 4. ⌈log₂5⌉ = 3 and ⌈log₂4⌉ = 2, so this reduction does save one flip-flop and removes the 3 invalid codes.

Example 4 - flip-flop count, assignments and speed. A controller has 12 states.

• Binary: n = ⌈log₂12⌉ = 4 flip-flops, unused codes = 16 − 12 = 4.
• Number of possible assignments = 16!/(16 − 12)! = 20,922,789,888,000 / 24 = 871,782,912,000 - which is why heuristics or tool defaults are used, not exhaustive search. (For the 4-state machine of Example 1: 4!/0! = 24 assignments, and 24/(2! × 2²) = 3 functionally distinct ones.)
• One-hot: 12 flip-flops, but each D is a simple OR of incoming arcs.
• Timing with t_cq = 0.8 ns, worst-case next-state logic 2.4 ns, t_su = 0.5 ns, skew 0 → T_min = 3.7 ns → f_max ≈ 270 MHz. Re-coding one-hot cuts the logic to 0.9 ns → T = 2.2 ns → f_max ≈ 455 MHz, at the cost of 8 extra flip-flops.

Example 5 - Mealy vending controller (₹10 item, accepts ₹5 and ₹10). Inputs a = ₹5 coin, b = ₹10 coin (never together); outputs DISP = dispense, RET5 = return ₹5. States S0 = ₹0 credit (Q=0), S5 = ₹5 credit (Q=1).

• D = Q′a + Qa′b′ = b′(Q ⊕ a) (the second term holds the ₹5 credit when no coin arrives), DISP = Q′b + Q(a + b), RET5 = Qb - one flip-flop and a handful of gates. Because DISP is a Mealy output it must be registered before driving the dispense solenoid.

// two-block FSM template (Example 1, Moore 101 detector)
localparam S0=2'b00, S1=2'b01, S2=2'b10, S3=2'b11;
reg [1:0] cs, ns;
always @(posedge clk or negedge rstn)
  if (!rstn) cs <= S0; else cs <= ns;
always @(*) case (cs)
  S0: ns = x ? S1 : S0;
  S1: ns = x ? S1 : S2;
  S2: ns = x ? S3 : S0;
  S3: ns = x ? S1 : S2;
  default: ns = S0;        // safe FSM: invalid codes go to reset
endcase
assign z = (cs == S3);     // Moore output

Where it is used

• VLSI and ASIC design (Intel Bengaluru, Qualcomm, Texas Instruments, Samsung SRI-B, Nvidia, Micron Hyderabad, Synopsys, Cadence): FSMs are the control plane of every block - AMBA AXI/APB masters and slaves, SPI/I²C/UART controllers, DDR and cache controllers, bus arbiters, clock-gating and power-state machines (D0-D3), JTAG TAP controller.
• FPGA and embedded product companies (Tessolve, Sasken, Mistral, L&T Technology Services, HCL, Wipro VLSI): protocol bridges, image-sensor interfaces, motor-control sequencers, CAN and Ethernet MAC state machines, with FSMD partitioning between controller and datapath.
• Defence and space (ISRO - URSC/SAC, DRDO - LRDE/RCI, BEL, SCL Mohali): radiation-tolerant safe FSMs for telemetry/telecommand framing, with unused states forced to reset and triple-redundant state registers.
• Industrial and consumer control: traffic-light and pedestrian-signal controllers in Indian city intersections, lift/elevator controllers, washing-machine and microwave sequencers, UPI card-reader and POS transaction flows, vending machines, prepaid smart energy meters (BIS IS 16444 series).
• Job roles and exams: RTL design, design verification (writing the reference FSM model in SystemVerilog/UVM), physical design timing closure; examined in GATE EC/EE/CS, ISRO and DRDO scientist tests, BARC, and in university digital-electronics and VLSI lab vivas.
• Software side: lexers and parsers, regular-expression engines and TCP connection state machines use the same Moore/Mealy theory.

Interview questions

• Q: What is the difference between a Moore and a Mealy machine? A: A Moore output depends only on the present state, so it is synchronous and glitch-free but one cycle late; a Mealy output depends on state and present input, so it responds in the same cycle but can glitch.
• Q: How many states does a Mealy detector for 1101 with overlap need, and how many for Moore? A: 4 for Mealy and 5 for Moore - k and k + 1 for a k-bit overlapping pattern.
• Q: Minimum flip-flops for a 12-state FSM? A: 4 with binary encoding (⌈log₂12⌉), leaving 4 unused codes; 12 if one-hot encoding is used.
• Q: Why is one-hot encoding preferred on FPGAs? A: Flip-flops are plentiful in LUT fabric, and each next-state input reduces to an OR of incoming arc conditions, which fits one LUT level and raises f_max; state decoding for outputs becomes free.
• Q: What do you do with unused states? A: Either treat them as don't-cares for minimum logic, or explicitly route them to the reset state for a safe FSM - mandatory in safety- and radiation-critical designs.
• Q: Two states have the same next states and the same outputs for all inputs - what next? A: They are equivalent and can be merged; verify by equivalence partitioning or an implication chart, then re-encode.
• Q: Why must a Mealy output not drive a clock or a write-enable? A: It changes combinationally with the input, so it can glitch mid-cycle and produce a spurious edge; register it or use a Moore output.
• Q: What limits the clock frequency of an FSM? A: The state-register clock-to-Q delay plus the worst-case next-state combinational delay plus the flip-flop setup time, plus clock skew and uncertainty.
• Q: An asynchronous push-button feeds your FSM directly. What is the risk? A: Metastability - different state flip-flops may sample different values and the machine can enter an invalid state; use a two-flip-flop synchroniser and debounce.
• Q: How would you implement a "wait 1 second" state? A: Not with states - use a counter loaded in that state, hold the state while its done flag is low, and branch out when it asserts.
• Q: Does state reduction always save hardware? A: No. Flip-flop count falls only when the reduction crosses a power of two, and reduction can sometimes increase next-state logic complexity.
• Q: Convert a Mealy machine to Moore - what happens to the state count? A: Each Mealy state that emits different outputs on different arcs splits into one state per output value, so the Moore machine may have up to (states × distinct outputs) states and its output is delayed one cycle.

Common mistakes

• Leaving a state diagram incomplete - missing an input combination, or giving two overlapping arc conditions for the same input, which is not a valid deterministic FSM.
• Forgetting overlap: returning to the reset state after a detection instead of to the state matching the longest useful suffix, which misses patterns like 10101.
• Writing a Mealy output inside the bubble or a Moore output on the arc, and then being unable to explain the one-cycle timing difference.
• Mixing up the JK excitation entries (using 0→1 as J=1,K=1) or writing D = present state instead of D = next state.
• Using unused states as don't-cares and then claiming the design is "safe" against lock-up - the two goals conflict and must be stated.
• Ignoring state-register reset: no reset, or a reset code that is not the intended start state, so simulation starts from X and never recovers.
• Solving state reduction only by eyeballing identical rows and missing deeper equivalences that need the full partitioning iteration.

Related topics

Sequential circuits: flip-flops, counters and registers · Combinational circuits · Verilog and HDL basics · Programmable logic: PLDs, CPLDs and FPGAs · Number systems and Boolean algebra · Computer organisation: control unit design