L28: State Machines B

Objective
Perform the finite state machine design process: state identification, state table construction, state diagram derivation, state encoding, and next-state logic.


Before the Lecture

Required Textbook Reading:

  • 6.4 (Design of FSMs using CAD Tools)

The Full Design Process

  1. Gather requirements and write the word specification.
  2. Derive the abstract FSM (states + transitions).
  3. Create the state diagram and state table.
  4. Minimize the FSM (L29).
  5. Choose a state encoding (binary, one-hot, Gray, …).
  6. Choose the flip-flop type (D, T, JK).
  7. Derive next-state and output logic.
  8. Implement and verify (simulation, then FPGA).

Steps 1–3 are about correctness; steps 4–7 are about cost and speed.

State Identification

Start from the reset state and ask: “what is the smallest fact about the past that changes what I do next?” Each distinct answer is a state. Then add transitions for every input combination (including the ones the spec doesn’t mention – those become “don’t cares” or explicit error states).

State Encoding

With $n$ states you need $\lceil \log_2 n \rceil$ flip-flops for a binary encoding. Alternatives:

  • One-hot: one flip-flop per state; exactly one is 1 at a time. Uses more flip-flops but makes next-state logic very simple (often just AND/OR of current state bits and inputs). FPGAs have abundant flip-flops, so one-hot is common in practice.
  • Gray code: adjacent states differ in one bit; reduces switching noise and (in some technologies) glitches.
  • Output-encoded: state bits are the outputs (Moore). Saves output logic.

State assignment is not cosmetic. A clever assignment can cut combinational logic in half; a bad one can double it. CAD tools try many assignments automatically, which is why manual assignment matters less than it used to – but understanding it matters for reading the tool’s results and for small designs.

Deriving Next-State Logic

Once states are encoded, build the state-assigned table and derive $Y_i$ and $z$ with K-maps (or let the tool do it). With D flip-flops, $Y_i$ feeds $D_i$ directly. With JK flip-flops, use the excitation table from L26.

Case Study: Serial Adder

A serial adder adds two $n$-bit numbers one bit at a time using a single full adder and a carry flip-flop:

  • State = carry (0 or 1) – a two-state FSM.
  • Mealy version: sum bit is produced immediately from current carry and input bits.
  • Moore version: sum bit is produced one cycle later.

This is the textbook’s demonstration that the same algorithm, expressed as two different FSMs, needs different numbers of registers. It also shows how an FSM (carry state) cooperates with shift registers (M4 L23) to build a complete datapath.

Case Study: Arbiter

An arbiter grants access to a shared resource among several requesters. The FSM must remember which requester currently holds the grant and handle new requests without starving anyone. This case study shows priority encoding combined with state memory.

CAD Tools

Modern design flow:

  • Enter the FSM as a state diagram (graphical editor) or as behavioral Verilog.
  • The tool performs minimization and state assignment.
  • The tool generates a netlist (or HDL) that you simulate and synthesize.

Tools optimize for area or speed depending on settings; always simulate the tool’s output, not just your source.

Serial Adder FSM

stateDiagram-v2
    [*] --> C0
    C0 --> C0: a xor b == 0
    C0 --> C1: a and b == 1
    C1 --> C0: a nor b == 1
    C1 --> C1: otherwise

States represent the carry (C0/C1); the sum bit is computed combinationally from the current carry and inputs.

Looking Forward

L29 removes redundant states; L30 implements the result in Verilog.