Part IV: Simulation & Verification | Chapter 12

Finite State Machines in HDL

Moore and Mealy machines, the one- and two-process styles, state encoding, and two complete designs: a sequence detector and a traffic-light controller.

1. What a finite state machine is

Many circuits must do different things at different times: wait for a button, then count, then signal; or watch a stream of bits for a pattern. The circuit needs to remember where it is in a procedure. A finite state machine (FSM) is the standard way to build this: a register holds the current state — one of a finite list you choose — and combinational logic decides, at every clock edge, which state comes next and what the outputs are. The debouncer of Chapter 14 and the UART of Chapter 16 are FSMs; so is the control unit of every processor.

Mathematically, an FSM with state \(s\), input \(x\) and output \(y\) is described by two functions:

\[ s_{k+1} = \delta(s_k, x_k), \qquad y_k = \begin{cases} \lambda(s_k) & \text{Moore} \\ \lambda(s_k, x_k) & \text{Mealy} \end{cases} \]

\(\delta\) is the next-state function (Greek delta) and \(\lambda\) the output function (lambda); \(k\) counts clock cycles. In hardware, the state is a register, and \(\delta\) and \(\lambda\) are blocks of combinational logic:

Every synchronous FSM: a state register and two blocks of combinational logic. In a Moore machine the output depends only on the state; a Mealy machine adds the dashed path from the input straight to the output logic.

2. Moore and Mealy

The two classic kinds of FSM differ only in what the outputs may depend on.

	Moore	Mealy
output depends on	state only	state and current input
output drawn on	the state bubble	the transition arrow (input/output)
reaction to an input	next cycle (after the clock edge)	same cycle (combinational)
number of states	often one or two more	often fewer
output glitches	none if decoded from registers	can glitch when the input does
timing path	register → output	input → output through logic

The practical rule: Moore outputs are clean and easy to time, because they change only just after a clock edge. Mealy outputs react one cycle earlier, which matters when the next block must respond immediately, but they create a combinational path from an input straight to an output — chaining Mealy machines can build long paths and even combinational loops (Chapter 11, Bug 7). A common compromise is a Mealy machine whose output goes through one flip-flop: same timing as Moore, fewer states.

Key idea: a state is a summary of the past

A state stores exactly as much history as the future behaviour needs, and no more. A detector for 1011 does not remember all past bits — only the longest recent piece that could still be the start of a match: nothing, 1, 10 or 101. Naming states after what they remember (S10 = “the last bits were 10”) makes diagrams self-explanatory.

3. A sequence detector for 1011, as state diagrams

The machine receives one bit din per clock cycle and raises detected when the last four bits were 1011. Matches may overlap: in 1011011 the final 1 of the first match is also the first 1 of the second, so there are two detections.

The tricky transitions are the ones on a mismatch. In S101 (seen 101) a 0 gives 1010; its last two bits 10 are still a valid start, so go to S10, not back to S0. After a full match 1011, the last bit 1 is a valid start, so a further 1 leads to S1 and a 0 to S10.

Left: Moore detector — five states, the output (/1) belongs to state S1011. Right: Mealy detector — four states, the output is on the arrow S101 → S1 taken when din = 1 (written 1/1). Arrows are labelled with the input bit.

State	Remembers	din = 0	din = 1	Moore output
S0	nothing useful	S0	S1	0
S1	…1	S10	S1	0
S10	…10	S0	S101	0
S101	…101	S10	S1011 (Mealy: S1, output 1)	0
S1011	…1011 (Moore only)	S10	S1	1

4. The two-process style

The most common way to write an FSM mirrors the block diagram of Section 1 exactly: one clocked process for the state register, one combinational process for the next-state logic, and the output logic as a separate assignment (or inside the combinational process). It is called the two-process style.

det1011_moore — two processes, Moore output

Verilog

// "1011" sequence detector, overlapping, Moore style (two processes).
// detected depends only on the state: high for one cycle AFTER the last 1.
module det1011_moore (
    input  wire clk,
    input  wire rst,
    input  wire din,
    output wire detected
);
    localparam [2:0] S0    = 3'd0,   // nothing useful seen yet
                     S1    = 3'd1,   // seen ...1
                     S10   = 3'd2,   // seen ...10
                     S101  = 3'd3,   // seen ...101
                     S1011 = 3'd4;   // seen ...1011: output high

    reg [2:0] state = S0, state_next;

    // Process 1: the state register
    always @(posedge clk) begin
        if (rst)
            state <= S0;
        else
            state <= state_next;
    end

    // Process 2: next-state logic (combinational)
    always @(*) begin
        state_next = S0;                         // safe default
        case (state)
            S0:    state_next = din ? S1    : S0;
            S1:    state_next = din ? S1    : S10;
            S10:   state_next = din ? S101  : S0;
            S101:  state_next = din ? S1011 : S10;
            S1011: state_next = din ? S1    : S10;  // overlap: reuse the tail
            default: state_next = S0;
        endcase
    end

    // Moore output: a function of the state only
    assign detected = (state == S1011);
endmodule

VHDL

-- "1011" sequence detector, overlapping, Moore style (two processes).
-- detected depends only on the state: high for one cycle AFTER the last 1.
library ieee;
use ieee.std_logic_1164.all;

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

architecture rtl of det1011_moore is
    type state_t is (S0, S1, S10, S101, S1011);
    signal state      : state_t := S0;
    signal state_next : state_t;
begin
    -- Process 1: the state register
    reg : process (clk)
    begin
        if rising_edge(clk) then
            if rst = '1' then
                state <= S0;
            else
                state <= state_next;
            end if;
        end if;
    end process;

    -- Process 2: next-state logic (combinational)
    comb : process (state, din)
    begin
        state_next <= S0;                        -- safe default
        case state is
            when S0    => if din = '1' then state_next <= S1;    else state_next <= S0;  end if;
            when S1    => if din = '1' then state_next <= S1;    else state_next <= S10; end if;
            when S10   => if din = '1' then state_next <= S101;  else state_next <= S0;  end if;
            when S101  => if din = '1' then state_next <= S1011; else state_next <= S10; end if;
            when S1011 => if din = '1' then state_next <= S1;    else state_next <= S10; end if;
        end case;
    end process;

    -- Moore output: a function of the state only
    detected <= '1' when state = S1011 else '0';
end architecture;

Points to notice:

Named states. In VHDL an enumerated type (type state_t is (S0, S1, …)) lets you write states by name and leaves the bit patterns to the synthesiser. Verilog-2001 has no enumerations, so states are localparam constants with explicit codes. (SystemVerilog adds enum.)
A default assignment first. state_next = S0; at the top of the combinational process guarantees it is assigned on every path — no latch (Chapter 11, Bug 2) — and gives a safe answer for any unexpected state.
Complete sensitivity. @(*) in Verilog; (state, din) in VHDL — both signals the process reads.
Synchronous reset to a known state, plus an initial value so the register starts there on the FPGA even without a reset pulse.

5. The Mealy version, and the one-cycle difference

In the Mealy detector the output is computed in the combinational process from both state and din. When the machine is in S101 and the incoming bit is 1, the output is high immediately, and the next state is S1 (overlap) — state S1011 is no longer needed.

det1011_mealy — four states, output on the transition

Verilog

// "1011" sequence detector, overlapping, Mealy style (two processes).
// detected depends on state AND input: high in the SAME cycle as the last 1.
module det1011_mealy (
    input  wire clk,
    input  wire rst,
    input  wire din,
    output reg  detected
);
    localparam [1:0] S0   = 2'd0,    // nothing useful seen yet
                     S1   = 2'd1,    // seen ...1
                     S10  = 2'd2,    // seen ...10
                     S101 = 2'd3;    // seen ...101

    reg [1:0] state = S0, state_next;

    always @(posedge clk) begin
        if (rst)
            state <= S0;
        else
            state <= state_next;
    end

    // Next state AND output, both combinational
    always @(*) begin
        state_next = S0;
        detected   = 1'b0;
        case (state)
            S0:   state_next = din ? S1 : S0;
            S1:   state_next = din ? S1 : S10;
            S10:  state_next = din ? S101 : S0;
            S101: begin
                      state_next = din ? S1 : S10;    // overlap
                      detected   = din;               // "101" + 1
                  end
            default: state_next = S0;
        endcase
    end
endmodule

VHDL

-- "1011" sequence detector, overlapping, Mealy style (two processes).
-- detected depends on state AND input: high in the SAME cycle as the last 1.
library ieee;
use ieee.std_logic_1164.all;

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

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

    -- Next state AND output, both combinational
    comb : process (state, din)
    begin
        state_next <= S0;
        detected   <= '0';
        case state is
            when S0   => if din = '1' then state_next <= S1;   else state_next <= S0;  end if;
            when S1   => if din = '1' then state_next <= S1;   else state_next <= S10; end if;
            when S10  => if din = '1' then state_next <= S101; else state_next <= S0;  end if;
            when S101 =>
                if din = '1' then state_next <= S1; else state_next <= S10; end if;  -- overlap
                detected <= din;                                                   -- "101" + 1
        end case;
    end process;
end architecture;

The testbench drives both detectors with the same 64-bit pattern, which contains 12 overlapping matches. The reference model is just a 4-bit shift register of the last input bits: the Mealy output must equal hist == 1011 in the same cycle, and the Moore output must equal the same comparison one cycle later.

det1011_tb — both detectors against a shift-register model

Verilog

`timescale 1ns/1ps
// Drives the Moore and Mealy detectors with the same 64-bit pattern and
// checks both against a 4-bit shift-register model of "the last four bits".
module det1011_tb;
    localparam [63:0] PATTERN = 64'hB758_B7B4_B62E_5B5E;   // contains 12 overlapping "1011"
    reg        clk = 0, rst = 1, din = 0;
    wire       det_moore, det_mealy;
    reg  [3:0] hist = 4'b0000;          // reference model: last four input bits
    reg        match_prev = 1'b0;       // the model's match one cycle ago
    integer    i, n_moore = 0, n_mealy = 0, errors = 0;
    integer    t_mealy = -1, t_moore = -1;

    det1011_moore u_moore (.clk(clk), .rst(rst), .din(din), .detected(det_moore));
    det1011_mealy u_mealy (.clk(clk), .rst(rst), .din(din), .detected(det_mealy));

    always #4 clk = ~clk;

    initial begin
        repeat (2) @(negedge clk);
        rst = 0;
        for (i = 63; i >= 0; i = i - 1) begin
            din  = PATTERN[i];                          // new bit, half a cycle before the edge
            hist = {hist[2:0], din};
            #1;
            // Mealy: must see "1011" in the same cycle as its last bit
            if (det_mealy !== (hist == 4'b1011)) errors = errors + 1;
            // Moore: one cycle later
            if (det_moore !== match_prev) errors = errors + 1;
            if (det_mealy && t_mealy < 0) t_mealy = 63 - i;
            if (det_moore && t_moore < 0) t_moore = 63 - i;
            n_mealy    = n_mealy + det_mealy;
            n_moore    = n_moore + det_moore;
            match_prev = (hist == 4'b1011);
            @(negedge clk);
        end
        n_moore = n_moore + det_moore;                  // Moore's last pulse arrives after the last bit
        if (errors == 0 && n_mealy == 12 && n_moore == 12)
            $display("PASS: Mealy %0d, Moore %0d detections; first at bit %0d (Mealy) and %0d (Moore)",
                     n_mealy, n_moore, t_mealy, t_moore);
        else
            $display("FAIL: errors=%0d mealy=%0d moore=%0d", errors, n_mealy, n_moore);
        $finish;
    end
endmodule

VHDL

library ieee;
use ieee.std_logic_1164.all;

-- Drives the Moore and Mealy detectors with the same 64-bit pattern and
-- checks both against a 4-bit shift-register model of "the last four bits".
entity det1011_tb is
end entity;

architecture sim of det1011_tb is
    constant PATTERN : std_logic_vector(63 downto 0) := x"B758B7B4B62E5B5E";  -- 12 overlapping "1011"
    signal clk, din            : std_logic := '0';
    signal rst                 : std_logic := '1';
    signal det_moore, det_mealy : std_logic;
    signal done                : boolean := false;
begin
    u_moore : entity work.det1011_moore port map (clk => clk, rst => rst, din => din, detected => det_moore);
    u_mealy : entity work.det1011_mealy port map (clk => clk, rst => rst, din => din, detected => det_mealy);

    clk <= not clk after 4 ns when not done;

    process
        variable hist                : std_logic_vector(3 downto 0) := "0000";
        variable match, match_prev   : std_logic := '0';
        variable n_moore, n_mealy    : natural := 0;
        variable errors              : natural := 0;
        variable t_mealy, t_moore    : integer := -1;
    begin
        for k in 1 to 2 loop wait until falling_edge(clk); end loop;
        rst <= '0';
        for i in 63 downto 0 loop
            din  <= PATTERN(i);                         -- new bit, half a cycle before the edge
            hist := hist(2 downto 0) & PATTERN(i);
            match := '1' when hist = "1011" else '0';
            wait for 1 ns;
            -- Mealy: must see "1011" in the same cycle as its last bit
            if det_mealy /= match then errors := errors + 1; end if;
            -- Moore: one cycle later
            if det_moore /= match_prev then errors := errors + 1; end if;
            if det_mealy = '1' and t_mealy < 0 then t_mealy := 63 - i; end if;
            if det_moore = '1' and t_moore < 0 then t_moore := 63 - i; end if;
            if det_mealy = '1' then n_mealy := n_mealy + 1; end if;
            if det_moore = '1' then n_moore := n_moore + 1; end if;
            match_prev := match;
            wait until falling_edge(clk);
        end loop;
        if det_moore = '1' then n_moore := n_moore + 1; end if;  -- Moore's last pulse arrives after the last bit
        if errors = 0 and n_mealy = 12 and n_moore = 12 then
            report "PASS: Mealy " & to_string(n_mealy) & ", Moore " & to_string(n_moore)
                 & " detections; first at bit " & to_string(t_mealy) & " (Mealy) and "
                 & to_string(t_moore) & " (Moore)";
        else
            report "FAIL: errors=" & to_string(errors) & " mealy=" & to_string(n_mealy)
                 & " moore=" & to_string(n_moore) severity failure;
        end if;
        done <= true;
        wait;
    end process;
end architecture;

Output

Icarus: PASS: Mealy 12, Moore 12 detections; first at bit 3 (Mealy) and 4 (Moore)
GHDL:   det1011_tb.vhd:48:13:@528ns:(report note): PASS: Mealy 12, Moore 12 detections; first at bit 3 (Mealy) and 4 (Moore)

The first match ends at bit 3 of the pattern (1011…): the Mealy machine reports it during bit 3, the Moore machine during bit 4. The figure below also hints at a Mealy hazard: the output rises at the edge where the machine enters S101, while din still shows the previous 1. Had the next bit been 0 (1010), detected would have been high for half a cycle untildin changed — a pulse that logic sampling on the next rising edge ignores, but which is real on the wire. As a check that the test has teeth, making the Moore machine non-overlapping (S1011 → S0 on a 0) gives FAIL: errors=4 mealy=12 moore=8.

Same input, two detectors; din changes on falling edges and is sampled on rising edges (green dashes mark the edges that capture the last 1 of each match). The Mealy output is high in the cycle that ends with that edge, the Moore output in the cycle after it, while the machine sits in S1011. The second match shares its first 1 with the end of the first (overlap).

Common mistake: forgetting the overlap

The most frequent error in sequence detectors is sending every mismatch, and every completed match, back to S0. The machine then misses patterns that start inside the previous partial or complete match. For each state and each input, ask: “what is the longest tail of the bits seen so far that is still a beginning of the pattern?” — that tail names the next state.

6. The one-process style: a traffic light with a timer

Real FSMs often stay in a state for a number of cycles. The cleanest way is a timer counter that runs alongside the state and is cleared on every transition. When state and timer change together, the one-process style — state register and next-state logic in a single clocked process — is usually shorter and easier to read. Because every assignment is inside a clocked process, there is no risk of latches; the price is that outputs computed inside that process are registered (one cycle later), so we decode the Moore outputs from state outside it.

The controller below manages a crossing of a main road (north–south, NS) and a side road (east–west, EW). NS stays green until it has been green for at least GREEN_T ticks and a car is waiting on the side road. Then NS goes yellow, EW gets a fixed green, EW goes yellow, and NS is green again. Times are counted in tick pulses — the clock-enable pattern of Chapter 14 — so the same FSM runs at 1 tick/s on the board and 1 tick per 4 cycles in the testbench.

Traffic-light FSM. Each state shows the NS and EW lights; transitions fire on a tick once the timer reaches its limit.

traffic — one-process FSM with a timer

Verilog

// Traffic light: a main road (NS) that stays green until a car waits on
// the side road (EW). One-process style: state and timer in one clocked
// block. Moore outputs {red, yellow, green}. Times count 'tick' pulses.
module traffic #(
    parameter GREEN_T  = 8,           // minimum green time, in ticks (>= 2)
    parameter YELLOW_T = 2            // yellow time, in ticks (<= GREEN_T)
) (
    input  wire       clk,
    input  wire       rst,
    input  wire       tick,           // one-cycle enable pulse (e.g. 1 Hz)
    input  wire       ew_car,         // car sensor on the side road
    output wire [2:0] ns_light,       // {R, Y, G}
    output wire [2:0] ew_light        // {R, Y, G}
);
    localparam [1:0] NS_GO = 2'd0, NS_YEL = 2'd1, EW_GO = 2'd2, EW_YEL = 2'd3;

    (* fsm_encoding = "one_hot" *)    // Vivado: ask for one-hot state bits
    reg [1:0] state = NS_GO;
    reg [$clog2(GREEN_T)-1:0] timer = 0;   // ticks spent in this state

    always @(posedge clk) begin
        if (rst) begin
            state <= NS_GO;
            timer <= 0;
        end else if (tick) begin
            case (state)
                NS_GO:                         // green until min time AND a car
                    if (timer < GREEN_T - 1)  timer <= timer + 1'b1;
                    else if (ew_car)          begin state <= NS_YEL; timer <= 0; end
                NS_YEL:
                    if (timer < YELLOW_T - 1) timer <= timer + 1'b1;
                    else                      begin state <= EW_GO;  timer <= 0; end
                EW_GO:
                    if (timer < GREEN_T - 1)  timer <= timer + 1'b1;
                    else                      begin state <= EW_YEL; timer <= 0; end
                EW_YEL:
                    if (timer < YELLOW_T - 1) timer <= timer + 1'b1;
                    else                      begin state <= NS_GO;  timer <= 0; end
                default:                      begin state <= NS_GO;  timer <= 0; end
            endcase
        end
    end

    // Moore outputs, decoded from the state only
    assign ns_light = (state == NS_GO) ? 3'b001 : (state == NS_YEL) ? 3'b010 : 3'b100;
    assign ew_light = (state == EW_GO) ? 3'b001 : (state == EW_YEL) ? 3'b010 : 3'b100;
endmodule

VHDL

-- Traffic light: a main road (NS) that stays green until a car waits on
-- the side road (EW). One-process style: state and timer in one clocked
-- process. Moore outputs (R, Y, G). Times count 'tick' pulses.
library ieee;
use ieee.std_logic_1164.all;

entity traffic is
    generic (
        GREEN_T  : positive := 8;     -- minimum green time, in ticks (>= 2)
        YELLOW_T : positive := 2      -- yellow time, in ticks (<= GREEN_T)
    );
    port (
        clk      : in  std_logic;
        rst      : in  std_logic;
        tick     : in  std_logic;     -- one-cycle enable pulse (e.g. 1 Hz)
        ew_car   : in  std_logic;     -- car sensor on the side road
        ns_light : out std_logic_vector(2 downto 0);   -- (R, Y, G)
        ew_light : out std_logic_vector(2 downto 0)    -- (R, Y, G)
    );
end entity;

architecture rtl of traffic is
    type state_t is (NS_GO, NS_YEL, EW_GO, EW_YEL);
    signal state : state_t := NS_GO;
    signal timer : natural range 0 to GREEN_T - 1 := 0;   -- ticks spent in this state

    attribute fsm_encoding : string;                    -- Vivado: ask for
    attribute fsm_encoding of state : signal is "one_hot";  -- one-hot state bits
begin
    process (clk)
    begin
        if rising_edge(clk) then
            if rst = '1' then
                state <= NS_GO;
                timer <= 0;
            elsif tick = '1' then
                case state is
                    when NS_GO =>                       -- green until min time AND a car
                        if timer < GREEN_T - 1 then timer <= timer + 1;
                        elsif ew_car = '1' then     state <= NS_YEL; timer <= 0;
                        end if;
                    when NS_YEL =>
                        if timer < YELLOW_T - 1 then timer <= timer + 1;
                        else                         state <= EW_GO;  timer <= 0;
                        end if;
                    when EW_GO =>
                        if timer < GREEN_T - 1 then timer <= timer + 1;
                        else                        state <= EW_YEL; timer <= 0;
                        end if;
                    when EW_YEL =>
                        if timer < YELLOW_T - 1 then timer <= timer + 1;
                        else                         state <= NS_GO;  timer <= 0;
                        end if;
                end case;
            end if;
        end if;
    end process;

    -- Moore outputs, decoded from the state only
    ns_light <= "001" when state = NS_GO else "010" when state = NS_YEL else "100";
    ew_light <= "001" when state = EW_GO else "010" when state = EW_YEL else "100";
end architecture;

The testbench generates a tick every four clock cycles, waits 20 ticks with no car (NS must stay green), raises ew_car, and checks a safety property on every cycle: at least one road is red. That check is not tied to any particular scenario; it would catch a wrong transition anywhere.

traffic_tb — safety check and sequence check

Verilog

`timescale 1ns/1ps
// Ticks every 4 clock cycles. Checks the safety property (never green or
// yellow both ways), the minimum green time, and the full light sequence.
module traffic_tb;
    reg        clk = 0, rst = 1, tick = 0, ew_car = 0;
    wire [2:0] ns_l, ew_l;
    reg  [5:0] prev = 6'b001_100;
    integer    cyc = 0, n_tick = 0, errors = 0, changes = 0, ns_green_ticks = 0;

    traffic #(.GREEN_T(8), .YELLOW_T(2)) dut (.clk(clk), .rst(rst), .tick(tick),
        .ew_car(ew_car), .ns_light(ns_l), .ew_light(ew_l));

    always #4 clk = ~clk;
    always @(posedge clk) begin                   // tick generator: 1 cycle in 4
        cyc  <= cyc + 1;
        tick <= (cyc % 4 == 3);
    end

    // Monitor, sampled at each falling edge
    always @(negedge clk) if (!rst) begin
        if (ns_l != 3'b100 && ew_l != 3'b100) begin   // safety: one road must be red
            $display("ERROR at %0d ns: ns_l=%b ew_l=%b", $time, ns_l, ew_l);
            errors = errors + 1;
        end
        if ({ns_l, ew_l} != prev) begin
            changes = changes + 1;
            $display("%5d ns: NS %s  EW %s", $time,
                     ns_l == 3'b001 ? "green " : ns_l == 3'b010 ? "yellow" : "red   ",
                     ew_l == 3'b001 ? "green " : ew_l == 3'b010 ? "yellow" : "red   ");
        end
        prev = {ns_l, ew_l};
    end

    initial begin
        repeat (2) @(negedge clk);
        rst = 0;
        // No car for 20 ticks: NS must stay green the whole time
        repeat (20 * 4) @(negedge clk);
        if (ns_l != 3'b001) begin $display("ERROR: NS left green with no car"); errors = errors + 1; end
        // A car arrives: expect NS yellow, NS red / EW green, EW yellow, NS green
        ew_car = 1;
        repeat (4 * 4) @(negedge clk);
        ew_car = 0;
        repeat (20 * 4) @(negedge clk);
        if (errors == 0 && changes == 4 && ns_l == 3'b001)
            $display("PASS: 4 light changes, back to NS green, never both roads open");
        else
            $display("FAIL: errors=%0d changes=%0d", errors, changes);
        $finish;
    end
endmodule

VHDL

library ieee;
use ieee.std_logic_1164.all;

-- Ticks every 4 clock cycles. Checks the safety property (never green or
-- yellow both ways), the minimum green time, and the full light sequence.
entity traffic_tb is
end entity;

architecture sim of traffic_tb is
    signal clk, tick, ew_car : std_logic := '0';
    signal rst               : std_logic := '1';
    signal ns_l, ew_l        : std_logic_vector(2 downto 0);
    signal cyc               : natural := 0;
    signal errors, changes   : natural := 0;
    signal done              : boolean := false;

    function name(l : std_logic_vector(2 downto 0)) return string is
    begin
        if l = "001" then return "green ";
        elsif l = "010" then return "yellow";
        else return "red   ";
        end if;
    end function;
begin
    dut : entity work.traffic
        generic map (GREEN_T => 8, YELLOW_T => 2)
        port map (clk => clk, rst => rst, tick => tick, ew_car => ew_car,
                  ns_light => ns_l, ew_light => ew_l);

    clk <= not clk after 4 ns when not done;

    tick_gen : process (clk)                     -- tick generator: 1 cycle in 4
    begin
        if rising_edge(clk) then
            cyc <= cyc + 1;
            if cyc mod 4 = 3 then tick <= '1'; else tick <= '0'; end if;
        end if;
    end process;

    monitor : process (clk)                      -- sampled at each falling edge
        variable prev : std_logic_vector(5 downto 0) := "001100";
    begin
        if falling_edge(clk) and rst = '0' then
            if ns_l /= "100" and ew_l /= "100" then  -- safety: one road must be red
                report "ERROR: ns_l=" & to_string(ns_l) & " ew_l=" & to_string(ew_l) severity error;
                errors <= errors + 1;
            end if;
            if (ns_l & ew_l) /= prev then
                changes <= changes + 1;
                report "NS " & name(ns_l) & "  EW " & name(ew_l);
            end if;
            prev := ns_l & ew_l;
        end if;
    end process;

    stimulus : process
        procedure cycles(n : natural) is
        begin
            for i in 1 to n loop wait until falling_edge(clk); end loop;
        end procedure;
    begin
        cycles(2);
        rst <= '0';
        cycles(20 * 4);                          -- no car: NS must stay green
        assert ns_l = "001" report "ERROR: NS left green with no car" severity error;
        ew_car <= '1';                           -- a car arrives
        cycles(4 * 4);
        ew_car <= '0';
        cycles(20 * 4);
        if errors = 0 and changes = 4 and ns_l = "001" then
            report "PASS: 4 light changes, back to NS green, never both roads open";
        else
            report "FAIL: errors=" & to_string(errors) & " changes=" & to_string(changes)
                severity failure;
        end if;
        done <= true;
        wait;
    end process;
end architecture;

Output (Icarus; GHDL prints the same lines as report notes)

  680 ns: NS yellow  EW red
  744 ns: NS red     EW green
 1000 ns: NS red     EW yellow
 1064 ns: NS green   EW red
PASS: 4 light changes, back to NS green, never both roads open

The car is raised at 656 ns; NS turns yellow at the next tick (680 ns), stays yellow for 2 ticks (64 ns = 8 cycles), EW stays green for 8 ticks (256 ns), and so on. If the car condition is removed by mistake, the lights cycle on their own and the test reports FAIL: errors=0 changes=8. In the testbench the signals are called ns_l and ew_l, because ns is the nanosecond unit in VHDL.

To see the VHDL state names in a waveform viewer, dump with --wave=traffic.ghw: GHW keeps enumerated types, while VCD would show only codes (Chapter 11).

7. State encoding

Somebody has to choose the bit pattern of each state. With five states (the Moore detector) the main options are:

State	Binary	Gray	One-hot
S0	000	000	00001
S1	001	001	00010
S10	010	011	00100
S101	011	010	01000
S1011	100	110	10000
flip-flops	3	3	5

Binary (sequential): the fewest flip-flops, \(\lceil \log_2 N \rceil\), but the next-state logic must decode several bits at once.
Gray: also minimal, with neighbouring codes differing in one bit. Useful when the state is read by another clock domain or when most transitions go to the “next” state.
One-hot: one flip-flop per state, exactly one of them is 1. Testing “am I in state S101?” is reading a single bit, so the logic is small and fast. FPGAs are rich in flip-flops (106 400 on the PYNQ-Z2's XC7Z020) and their LUTs have 6 inputs, so one-hot is often the best choice there.

Vivado recognises FSMs during synthesis and, by default, picks the encoding itself — the synthesis log reports each FSM it found and the codes it used. You can override the choice with the fsm_encodingattribute on the state register, as traffic does; the usual values are "one_hot", "sequential", "gray", "johnson", "auto" and "none" (keep the codes as written). In Verilog it is written (* fsm_encoding = "one_hot" *) before the declaration; in VHDL it is a user-defined attribute of type string. Simulators ignore it, so it changes nothing in your testbench results — which is the point: encoding is an implementation choice, not a behaviour change.

8. Safe FSMs: reset, defaults and illegal states

A 3-bit binary register can hold 8 codes, but the Moore detector uses only 5. A one-hot register of 5 bits has 32 codes and only 5 are legal. The others are illegal states. Normally they are unreachable, but a missed synchroniser on an asynchronous input (Chapter 15), a glitch at power-up, or a radiation upset could put the machine there. A safe FSM is written so that it cannot get stuck:

Reset (and initialise) the state register to a defined state.
Start the combinational process with a default next state, and give the case a default (Verilog) or when others (VHDL) branch that returns to the idle state.
Synchronise every asynchronous input before it reaches the next-state logic.

One caution: synthesis tools optimise away logic that handles unreachable states, because by definition it never runs. A default branch therefore documents intent and protects simulation, but it does not by itself guarantee recovery in hardware. When recovery really matters, Vivado offers an fsm_safe_stateattribute that adds explicit recovery logic; see the Vivado synthesis guide (UG901) for its options.

Key idea: separate what from how

Write the state machine with named states and a clear transition table; let the tool choose the encoding unless you have a reason; and verify the behaviour against a model that knows nothing about states at all — a regular expression, a shift register, a timetable. The next section does exactly that.

On the board: the traffic light on the PYNQ-Z2 (after Chapter 14)

Once you have built first_lights in Chapter 14, this FSM drops straight in: drive tick from tick_gen with DIV = 125_000_000 (1 tick per second), connect ew_car to BTN0 through the synchroniser and debouncer, and show the lights on the two RGB LEDs: LD4 for NS (blue, green, red on pins L15, G17, N15) and LD5 for EW (G14, L14, M15). Yellow is red and green on together. Use GREEN_T = 8 and YELLOW_T = 2, and simulate the top level first.

9. Python: proving the detector on 200 000 random bits

The HDL testbench checked one 64-bit pattern. To gain real confidence we run the same transition tablesas the HDL in Python on 200 000 random bits and compare every output with an entirely independent method: a regular-expression search. The lookahead (?=1011) finds overlapping matches because it does not consume characters. The Mealy output must be high exactly where a match ends; the Moore output exactly one cycle later. The program also runs the non-overlapping variant to count what it would miss.

Python

script.py93 lines

import re
import numpy as np
import matplotlib.pyplot as plt

# State tables copied from det1011_moore / det1011_mealy.
# NEXT[state] = (next state if din = 0, next state if din = 1)
MOORE_NEXT = {'S0': ('S0', 'S1'), 'S1': ('S10', 'S1'), 'S10': ('S0', 'S101'),
              'S101': ('S10', 'S1011'), 'S1011': ('S10', 'S1')}
MEALY_NEXT = {'S0': ('S0', 'S1'), 'S1': ('S10', 'S1'), 'S10': ('S0', 'S101'),
              'S101': ('S10', 'S1')}

def run_moore(bits):
    """Output during each clock cycle (Moore: depends on the state only)."""
    state, out = 'S0', []
    for b in bits:
        out.append(int(state == 'S1011'))    # visible during this cycle
        state = MOORE_NEXT[state][b]         # clock edge at the end of the cycle
    return np.array(out)

def run_mealy(bits):
    """Output during each clock cycle (Mealy: state AND the current input)."""
    state, out = 'S0', []
    for b in bits:
        out.append(int(state == 'S101' and b == 1))
        state = MEALY_NEXT[state][b]
    return np.array(out)

rng = np.random.default_rng(12)
N = 200_000
bits = rng.integers(0, 2, N).tolist()
text = ''.join(map(str, bits))

# Reference: every position where "1011" ENDS, overlaps allowed (lookahead)
ends = np.array([m.start() + 3 for m in re.finditer('(?=1011)', text)])
mealy = run_mealy(bits)
moore = run_moore(bits)

ok_mealy = np.array_equal(np.flatnonzero(mealy), ends)
ok_moore = np.array_equal(np.flatnonzero(moore), ends[ends < N - 1] + 1)
print(f'random bits         : {N}')
print(f'regex matches       : {len(ends)}  (expected about N/16 = {N/16:.0f})')
print(f'Mealy == regex      : {ok_mealy}')
print(f'Moore == regex + 1  : {ok_moore}  (one cycle later)')

# A non-overlapping detector (S1011 -> S0 on a 0) misses matches like 1011011
NONOV = dict(MOORE_NEXT, S1011=('S0', 'S1'))
state, nonov = 'S0', 0
for b in bits:
    nonov += state == 'S1011'
    state = NONOV[state][b]
print(f'non-overlapping FSM : {nonov} detections, misses {len(ends) - nonov}')

gaps = np.diff(ends)
print(f'mean gap between detections: {gaps.mean():.2f} bits (theory: 16)')

# ---- plot ----
plt.style.use('dark_background')
fig = plt.figure(figsize=(11, 7))
fig.patch.set_facecolor('#0a0a0a')
gs = fig.add_gridspec(2, 1, height_ratios=[1.25, 1], hspace=0.35)

ax = fig.add_subplot(gs[0]); ax.set_facecolor('#0f0f0f')
W = 40
start = int(ends[(ends > 10) & (np.diff(np.r_[ends, N])[:] == 3)][0]) - 6   # a window with an overlap
t = np.arange(W + 1)
rows = [(np.array(bits[start:start + W]), 'din', '#38bdf8'),
        (mealy[start:start + W], 'Mealy', '#fbbf24'),
        (moore[start:start + W], 'Moore', '#fb923c')]
for k, (sig, name, col) in enumerate(rows):
    y0 = (2 - k) * 1.6
    ax.step(t, np.r_[sig, sig[-1]] + y0, where='post', color=col, lw=1.6)
    ax.text(-0.8, y0 + 0.5, name, ha='right', va='center', color=col, fontsize=11)
for i, b in enumerate(bits[start:start + W]):
    ax.text(i + 0.5, 3.2 + 1.25, str(b), ha='center', color='#7dd3fc', fontsize=8)
for e in ends[(ends >= start) & (ends < start + W)] - start:
    ax.axvspan(e - 3, e + 1, color='#4ade80', alpha=0.10)
ax.set_xlim(0, W); ax.set_ylim(-0.3, 4.8); ax.set_yticks([])
ax.set_xlabel('clock cycle (window of the random stream)')
ax.set_title('Same stream, two detectors: Mealy fires on the last 1, Moore one cycle later '
             '(green = "1011" found by regex)', color='#fdba74', fontsize=10)
for sp in ax.spines.values(): sp.set_edgecolor('#374151')

ax2 = fig.add_subplot(gs[1]); ax2.set_facecolor('#0f0f0f')
hist = np.bincount(gaps, minlength=60)[:60]
ax2.bar(np.arange(60), hist / len(gaps), color='#fb923c', width=0.8)
ax2.axvline(gaps.mean(), color='#4ade80', ls='--', lw=1.2, label=f'mean = {gaps.mean():.2f}')
ax2.set_xlabel('bits between consecutive detections')
ax2.set_ylabel('fraction')
ax2.set_title('Gaps of 3 are overlaps (1011011): a non-overlapping detector would miss them',
              color='#fdba74', fontsize=10)
ax2.legend(framealpha=0.3)
for sp in ax2.spines.values(): sp.set_edgecolor('#374151')
plt.savefig('output.png', dpi=120, bbox_inches='tight', facecolor='#0a0a0a')

Click Run to execute the Python code

Code will be executed with Python 3 on the server

Both machines agree with the regex at every one of the 200 000 positions. The number of matches is close to \(N/16\), since each position starts 1011 with probability \(2^{-4}\). The histogram shows that no two matches end fewer than 3 bits apart, and that gaps of exactly 3 — overlaps like 1011011 — occur in about one case in eight: those are the matches the non-overlapping machine misses.

With testbenches, waveforms and FSMs in hand, Part IV is complete. Part V takes these verified designs through Vivado and onto the PYNQ-Z2.

Practice Problems

Progress: 0/5 (0%)

⭐ Easy

An FSM has 12 states. How many flip-flops does it need with (a) binary, (b) Gray, (c) one-hot encoding?

⭐ Easy

Feed the input sequence 1 0 1 1 0 1 1 (one bit per clock cycle, starting in S0) to the overlapping Moore detector. List the states visited and the cycles in which detected is high. Then do the same for the Mealy detector.

⭐⭐ Medium

Design (state diagram and transition table) a Moore machine that detects 110 with overlap. How many states does it need? Why does the Mealy version need one state fewer?

⭐⭐ Medium

In the traffic light, the side-road sensor ew_car comes from a push-button on the board. Name two things that must happen to this signal before it reaches the FSM, and what could go wrong in the FSM without them.

⭐⭐⭐ Hard

The Python program of Section 9 found that a random stream of \(N\) bits contains about \(N/16\) overlapping matches of 1011, and that a non-overlapping detector misses about 11% of them. Explain the \(1/16\) and estimate the miss rate analytically.

Problem Set Statistics

Total Problems

Attempted

Completion

Share:X Reddit LinkedIn

← 11. Waveforms & Debugging 13. Vivado & the PYNQ-Z2 →