State Machines

Counters remember a number; state machines remember a situation. An FSM is the standard way to express "what happens next depends on what has already happened", protocol handling, controllers, sequencers are all FSMs at heart.

This one watches a serial bit stream and pulses detected whenever the last four bits were 1011, with overlap (in 1011011 the pattern occurs twice; the middle 1 does double duty). Each state encodes how much of the pattern has been seen so far:

IDLE   nothing useful yet
S1     seen 1
S10    seen 10
S101   seen 101      -- a 1 now completes the pattern

The interesting transitions are the failure ones: from S101 on a 1 we output detected but go to S1 (that 1 may start the next match), not IDLE. Getting these right by hand is fiddly, which is exactly why the structure is rigid boilerplate: one register process, one combinational next-state case, defaults everywhere (the FSM generator writes this skeleton for you, and its DOT output draws the state diagram).

In the waveform the testbench feeds 1 0 1 1 0 1 1 1 0 1 1, predict where detected should pulse before you look (bits 4 and 7... check yourself).

Experiment: change the pattern to 1101, or make the detector non-overlapping and compare the pulse positions on the same input.

The design

Verilog, design.v 
// Serial pattern detector for 1011, overlapping matches (Mealy output).
module seq_detect (
    input  wire clk,
    input  wire rst,
    input  wire din,        // one bit per clock
    output wire detected    // pulses when the last 4 bits were 1011
);
    localparam [1:0] IDLE = 2'd0,  // nothing seen
                     S1   = 2'd1,  // seen 1
                     S10  = 2'd2,  // seen 10
                     S101 = 2'd3;  // seen 101

    reg [1:0] state, state_nxt;

    always @(posedge clk)
        if (rst) state <= IDLE;
        else     state <= state_nxt;

    always @* begin
        state_nxt = state;
        case (state)
            IDLE: state_nxt = din ? S1   : IDLE;
            S1:   state_nxt = din ? S1   : S10;   // 11: still "seen 1"
            S10:  state_nxt = din ? S101 : IDLE;  // 100: start over
            S101: state_nxt = din ? S1   : S10;   // hit! the 1 may restart
        endcase
    end

    assign detected = (state == S101) && din;
endmodule
Show the VHDL version
VHDL, design.vhd 
-- Serial pattern detector for 1011, overlapping (Mealy output).
library ieee;
use ieee.std_logic_1164.all;

entity seq_detect is
    port (
        clk, rst : in  std_logic;
        din      : in  std_logic;
        detected : out std_logic
    );
end entity;

architecture rtl of seq_detect is
    type state_t is (IDLE, S1, S10, S101);
    signal state, state_nxt : state_t;
begin
    process (clk) begin
        if rising_edge(clk) then
            if rst = '1' then state <= IDLE;
            else              state <= state_nxt;
            end if;
        end if;
    end process;

    process (all) begin
        state_nxt <= state;
        case state is
            when IDLE => if din = '1' then state_nxt <= S1;  else state_nxt <= IDLE; end if;
            when S1   => if din = '1' then state_nxt <= S1;  else state_nxt <= S10;  end if;
            when S10  => if din = '1' then state_nxt <= S101; else state_nxt <= IDLE; end if;
            when S101 => if din = '1' then state_nxt <= S1;  else state_nxt <= S10;  end if;
        end case;
    end process;

    detected <= '1' when state = S101 and din = '1' else '0';
end architecture;
Show the MyHDL (Python) version
MyHDL, design.py 
from myhdl import block, Signal, enum, always, always_comb, instance, delay, StopSimulation

t_state = enum('IDLE', 'S1', 'S10', 'S101')

@block
def seq_detect(clk, rst, din, detected):
    state = Signal(t_state.IDLE)
    nxt   = Signal(t_state.IDLE)

    @always(clk.posedge)
    def reg():
        if rst:
            state.next = t_state.IDLE
        else:
            state.next = nxt

    @always_comb
    def comb():
        if state == t_state.IDLE:
            nxt.next = t_state.S1 if din else t_state.IDLE
        elif state == t_state.S1:
            nxt.next = t_state.S1 if din else t_state.S10
        elif state == t_state.S10:
            nxt.next = t_state.S101 if din else t_state.IDLE
        else:  # S101
            nxt.next = t_state.S1 if din else t_state.S10

    @always_comb
    def out():
        detected.next = 1 if (state == t_state.S101 and din) else 0
    return reg, comb, out

@block
def tb():
    clk = Signal(bool(0))
    rst = Signal(bool(1))
    din = Signal(bool(0))
    detected = Signal(bool(0))
    dut = seq_detect(clk, rst, din, detected)
    stream = [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1]

    @always(delay(5))
    def clkgen():
        clk.next = not clk

    @instance
    def stim():
        yield delay(12); rst.next = 0
        for bit in stream:
            yield clk.negedge
            din.next = bit
        yield clk.negedge
        din.next = 0
        yield delay(20)
        raise StopSimulation
    return dut, clkgen, stim

inst = tb()
inst.config_sim(trace=True)
inst.run_sim()

The testbench

Verilog, tb.v 
`timescale 1ns/1ns
module tb;
    reg clk = 0, rst = 1, din = 0;
    wire detected;

    seq_detect dut (.clk(clk), .rst(rst), .din(din), .detected(detected));

    always #5 clk = ~clk;

    reg [10:0] stream = 11'b10110111011;   // fed MSB first
    integer i;

    initial begin
        $dumpfile("wave.vcd"); $dumpvars(0, tb);
        #12 rst = 0;
        for (i = 10; i >= 0; i = i - 1) begin
            @(negedge clk) din = stream[i];
        end
        @(negedge clk) din = 0;
        #20 $finish;
    end
endmodule
Show the VHDL testbench
VHDL, tb.vhd 
library ieee;
use ieee.std_logic_1164.all;
entity tb is end entity;
architecture sim of tb is
  signal clk : std_logic := '0';
  signal rst : std_logic := '1';
  signal din : std_logic := '0';
  signal detected : std_logic;
  constant stream : std_logic_vector(10 downto 0) := "10110111011";
begin
  dut : entity work.seq_detect port map (clk=>clk, rst=>rst, din=>din, detected=>detected);
  clk <= not clk after 5 ns;
  process begin
    wait for 12 ns; rst <= '0';
    for i in 10 downto 0 loop            -- feed the stream MSB first
      wait until falling_edge(clk); din <= stream(i);
    end loop;
    wait until falling_edge(clk); din <= '0';
    wait for 20 ns; std.env.stop;
  end process;
end architecture;

The MyHDL version keeps the design and its testbench in one design.py.

Simulated waveform

This trace was produced by actually simulating the code above with Icarus Verilog.

15 30 45 60 75 90 105 120 135 t (ns) detected clk din rst stream[10:0] 5BB i[31:0] x A 9 8 7 6 5 4 3 2 1 0 FFFFFFFF IDLE 0 S1 1 S10 2 S101 3 state[1:0] x 0 1 2 3 1 2 3 1 2 3 1 2 0 state_nxt[1:0] x 0 1 2 0 3 1 2 0 3 1 2 0 3 1 2 0

Try it live

Open this lesson in a playground, edit the code, and re-run it.

Verilog → VHDL → MyHDL →

Put it to work

Tools that apply what this lesson covers.

FSM Skeleton Generator

Transition list in - two-process Verilog/VHDL state machine + DOT graph out.