Chapter 3: Finite State Machines (FSMs)

Introduction

Finite State Machines (FSMs) are a powerful abstraction in digital design, used to model systems that move through a sequence of states in response to input signals and clock transitions. FSMs are used extensively in control circuits, communication protocols, sequencing logic, and embedded system design.

An FSM consists of a finite number of states, transitions between those states based on input conditions, and outputs that depend on the current state (and sometimes input). They are implemented using flip-flops to hold the current state and combinational logic to determine transitions and outputs.

3.1 Moore vs. Mealy FSMs

FSMs are commonly divided into two categories based on how their outputs are generated:

Moore Machine: Outputs depend only on the current state. Outputs are synchronized with the clock and change only on state transitions.
Mealy Machine: Outputs depend on both the current state and current inputs. This can lead to faster response but may increase design complexity.

3.2 State Diagrams and State Tables

State diagrams are graphical representations of FSM behavior. Each circle represents a state, and arrows show transitions between states triggered by input conditions. Outputs (in Moore machines) are typically labeled inside the states, while in Mealy machines, outputs are shown on transitions.

State tables provide a structured, tabular format listing all current states, possible inputs, resulting next states, and outputs.

3.3 Designing FSMs Using Flip-Flops

Designing an FSM requires translating the high-level description into hardware using these steps:

Define all required states, inputs, and outputs.
Draw a state diagram showing all transitions and outputs.
Assign binary codes to each state (using binary, Gray, or one-hot encoding).
Create a state transition table and output table.
Derive next-state and output logic equations.
Implement using flip-flops (usually D-type) and combinational logic.

3.4 FSM Implementation in Verilog

FSMs are coded in Verilog using state variables and case statements:

// State encoding
    parameter IDLE=2'b00, READ=2'b01, WRITE=2'b10;
    reg [1:0] state, next_state;
    
    // State update
    always @(posedge clk or posedge reset) begin
      if (reset)
        state <= IDLE;
      else
        state <= next_state;
    end
    
    // Next-state logic
    always @(*) begin
      case (state)
        IDLE:   next_state = start ? READ : IDLE;
        READ:   next_state = done ? WRITE : READ;
        WRITE:  next_state = done ? IDLE : WRITE;
        default: next_state = IDLE;
      endcase
    end

3.5 Practical Applications of FSMs

Traffic light controllers
UART communication control
Elevator controllers
Keypad scanners
Game logic controllers

Summary

FSMs describe sequential systems using states, transitions, and outputs
Moore and Mealy models differ in timing of outputs
Design process involves state diagramming, encoding, and logic implementation
FSMs are essential in embedded control and digital communication systems

🧪 MicroSim

Link to Simulation Demo

✅ Quiz: Check Your Understanding

1. In a Moore FSM, when are outputs updated?

A) On input change
B) On clock edge and input change
C) Only when input changes
D) Only based on current state

Show Answer

Correct answer: D) Only based on current state

2. Which FSM typically requires fewer states for the same functionality?

A) Moore
B) Mealy
C) Binary-encoded FSM
D) One-hot FSM

Show Answer

Correct answer: B) Mealy

3. What is the purpose of state encoding in FSM design?

A) To reduce the number of states
B) To improve testbench readability
C) To assign binary values to symbolic states
D) To convert Mealy to Moore

Show Answer

Correct answer: C) To assign binary values to symbolic states