Part IV: Digital Electronics | Chapter 12

Finite State Machines

Mealy vs Moore machines, state diagrams, state tables, state encoding, FSM design procedure, traffic light controller example, and FPGA implementation

1. What is a Finite State Machine?

A Finite State Machine (FSM) is a mathematical model of computation consisting of:

States Q
A finite set of distinct conditions the system can be in
Inputs I
External signals that drive state transitions
Outputs O
Signals produced as a function of state (and inputs)
Transition Function δ
Next state = δ(current state, input)
Output Function λ
Output = λ(state) for Moore, λ(state, input) for Mealy
Initial State q₀
The state the machine starts in at reset
\[ \text{FSM} = (Q,\, I,\, O,\, \delta,\, \lambda,\, q_0) \]

2. Mealy vs Moore Machines

Moore Machine

Outputs depend only on current state:\( O = \lambda(q) \).

Outputs change only on clock edges. Glitch-free. One extra state may be needed compared to Mealy. Traffic lights are a classic Moore machine example.

Mealy Machine

Outputs depend on state AND current inputs:\( O = \lambda(q, i) \).

Faster response (combinational path from input to output). Fewer states required. Outputs may glitch if inputs change asynchronously.

3. State Encoding

States must be encoded as binary patterns for hardware implementation. The choice of encoding affects logic complexity, speed, and power:

Binary Encoding

Uses ceil(log₂N) flip-flops for N states. Minimal hardware but complex next-state logic.

3 states → 2 bits: 00, 01, 10
One-Hot Encoding

One flip-flop per state, exactly one FF HIGH at any time. Fastest; simple logic; uses most FFs.

3 states → 3 bits: 001, 010, 100
Gray Encoding

Adjacent states differ by one bit. Eliminates glitches in output during transitions.

3 states → 00, 01, 11 (1-bit transitions)

4. Design Example: Traffic Light Controller

A traffic light is a Moore FSM with three states and a timeout-driven transition. The state table is:

RED4 cyclesOut: R=1,G=0,Y=0GREEN4 cyclesOut: R=0,G=1,Y=0YELLOW2 cyclesOut: R=0,G=0,Y=1timeouttimeouttimeoutstart
Traffic light Moore FSM: three states with timeout-driven transitions
Current StateDurationRGYNext State
RED (00)4 clk100GREEN
GREEN (01)4 clk010YELLOW
YELLOW (10)2 clk001RED

5. FPGA Implementation

FPGAs (Field-Programmable Gate Arrays) implement FSMs in configurable logic blocks (CLBs) containing LUTs (Look-Up Tables) and flip-flops. A synthesis tool converts HDL code (VHDL/Verilog) into an FSM automatically:

// Verilog Moore FSM — Traffic Light
module traffic_light(
  input  clk, rst,
  output reg red, green, yellow
);
  localparam RED=2'd0, GREEN=2'd1, YELLOW=2'd2;
  reg [1:0] state;
  reg [2:0] cnt;
  always @(posedge clk or posedge rst) begin
    if (rst) begin state <= RED; cnt <= 0; end
    else begin
      cnt <= cnt + 1;
      case (state)
        RED:    if (cnt==3) begin state<=GREEN;  cnt<=0; end
        GREEN:  if (cnt==3) begin state<=YELLOW; cnt<=0; end
        YELLOW: if (cnt==1) begin state<=RED;    cnt<=0; end
      endcase
    end
  end
  always @(*) begin
    {red,green,yellow} = 3'b000;
    case (state)
      RED:    red    = 1;
      GREEN:  green  = 1;
      YELLOW: yellow = 1;
    endcase
  end
endmodule

6. Python: Traffic Light FSM Simulation

Simulate the traffic light FSM over 40 clock cycles, plot the state diagram, state transition color map, and output waveforms for the RED, GREEN, and YELLOW signals.

Python
script.py144 lines

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Flip-Flops & CountersNext: Sampling & ADC →