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;

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

Simulated waveform

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