FSM Fundamentals

Chapter 4 · Section 4.1 · FSM Design

1. The Engineering Problem

You are building a serial receiver that must raise a one-cycle found pulse every time it sees the bit pattern 1011 arrive on a single-bit input din, one bit per clock, most-significant bit first — and the patterns may overlap, so the stream 1011011 contains the sequence twice (positions 0–3 and 3–6, sharing the middle 1). Nothing you have built so far can do this. A combinational function of din sees only this cycle's bit; it has no way to know that the previous three bits were 1, 0, 1. A counter can count cycles, but it cannot express "I have matched 101 so far and I am now hoping for a 1" — because counting is a fixed sequence, and this problem branches: what you do on the next bit depends on how much of the pattern you have already matched, which itself depends on the whole history of din.

That phrase — how much of the pattern I have matched so far — is the tell. It is a small, named summary of everything relevant about the past: not the entire history of din, just "which prefix of 1011 am I currently sitting on." Call those summaries states: IDLE (matched nothing), S1 (matched 1), S2 (matched 10), S3 (matched 101). Each incoming bit moves you from one state to another according to a fixed rule, and when a bit completes the pattern you emit found. This is not a made-up puzzle; it is the shape of nearly every controller in a chip. A bus master is in IDLE, then REQUEST, then DATA, then DONE; a UART receiver is in START, SAMPLE, STOP; a cache controller is in LOOKUP, MISS, FILL. In every case the design must remember where it is in an ongoing process and decide what to do next based on that plus the current inputs — and that is precisely what a finite state machine is for. The FSM is the RTL pattern for control: anything that sequences or decides is one.

   // GOAL: pulse found=1 whenever the last four bits of din were 1,0,1,1 (overlapping).
 
   // WRONG #1 — combinational: sees only THIS cycle's bit, no memory of the prefix.
   //   assign found = (din == 1'b1);            // knows nothing about 1,0,1 before it
 
   // WRONG #2 — a counter: counts cycles, but the pattern BRANCHES on din, it does
   //   not advance a fixed number of steps. A mismatch mid-pattern must fall BACK to
   //   a partial match, not to zero. A counter cannot express "fall back to S1".
 
   // RIGHT — remember WHICH PREFIX of 1011 we have matched so far, as a STATE, and
   //   move between states on each bit. That named "where are we" IS a state machine:
   //     IDLE (matched nothing) -> S1 (1) -> S2 (10) -> S3 (101) -> emit found on the last 1
   //   The pattern this page builds — state register + next-state logic + output logic.

2. Mental Model

3. Pattern Anatomy

An FSM is a register in a feedback loop with two combinational functions. Trace the loop and the three pieces are unmistakable.

Piece 1 — the state register (from 2.1). A register, WIDTH = log2(#states) bits wide (binary encoding) or one-hot, clocked, that holds the current state and loads next_state on every clock edge. It resets to a known initial state (IDLE here) so the machine starts in a defined place. This is the only sequential element in the FSM and the only memory of "where we are."

Piece 2 — the next-state logic (from 1.1). A combinational case over the current state — a mux — that, for each state and each input, produces next_state. This is the transition graph, transcribed. It must be latch-free: assign next_state on every path, which the discipline of a leading default (next_state = state; or next_state = IDLE;) guarantees. This piece is where the FSM's behaviour lives and where the signature bug (§7) hides.

Piece 3 — the output logic. What the FSM drives. If the outputs depend only on the current state, the machine is a Moore FSM (outputs are a function of state alone); if they depend on the state and the current inputs, it is a Mealy FSM (a bit faster to react, one fewer cycle of latency). Our 1011 detector emits found on the transition that completes the pattern (state S3 seeing din == 1), which is a Mealy output — this distinction is the subject of 4.2, previewed here.

The state enumeration. States get names, not bare numbers — enum/typedef in SystemVerilog, localparam/parameter in Verilog, an enumerated type in VHDL. Named states make the graph readable and let the tool (and 4.4) choose the encoding (binary, one-hot, gray) independently of the RTL. The RTL is written against the names; the bits are an implementation choice.

Now the graph itself — the 1011 overlapping detector. The load-bearing subtlety is overlap: after a full match, the trailing 1 can begin a new 1011, and after a mismatch you must fall back to the longest partial match still consistent with the bits just seen, not all the way to IDLE. Here is the original visual — the state graph as a data-flow of states (stages) and transitions (edges).

Read the fall-backs as a table — this is the transition/output table the next-state case transcribes directly. (After a completing 1 in S3, the last bit seen is a lone 1, which is a partial match of length 1, so we return to S1 — overlap preserved.)

Two anatomy rules close it. First, latch-free next-state logic: the case must define next_state for every (state, din) pair — a leading next_state = state; (or = IDLE;) default makes that automatic even if you forget a branch, exactly as the mux default did in 1.1. Second, reset to a known state: the state register resets to IDLE, so the machine starts matched-nothing rather than in an X/illegal state. Omit either and you get §7's two failures — a frozen machine or a machine that never starts.

4. Real RTL Implementation

This is the core of the page. We build (a) the complete canonical FSM — the 1011 overlapping sequence detector, all three pieces (state register + next-state case + output logic), with named states and reset to IDLE — and (b) the incomplete-next-state-case latch bug, buggy vs fixed — and each is shown in SystemVerilog, Verilog, and VHDL with an RTL block and a self-checking clocked testbench. The three pieces are identical in intent across all three languages; only the syntax differs.

One discipline runs through every next-state block: next_state is assigned on every path. In SystemVerilog/Verilog that means a leading default (next_state = state;) before the case; in VHDL it means the case is exhaustive with a when others => arm. Miss it and you get pattern (b)'s latch — the FSM freezes in whatever state it was in when the uncovered (state, din) pair occurred.

4a. The complete FSM — the 1011 detector, three ways

We use the classic two-always (plus output) style: one clocked block for the state register, one combinational block for the next-state logic, and the found output computed combinationally. (One-vs-two-vs-three-block styles and their trade-offs are 4.3, previewed in §8.) Watch the three pieces line up.

   module seq1011 (
       input  logic clk,
       input  logic rst,                          // synchronous, active-high reset to IDLE
       input  logic din,                          // one bit per clock, MSB-first
       output logic found                         // 1-cycle pulse when 1011 completes (overlapping)
   );
       // --- state enumeration: NAMES, not bare numbers (encoding is 4.4's choice) ---
       typedef enum logic [1:0] { IDLE, S1, S2, S3 } state_t;   // matched: -, 1, 10, 101
       state_t state, next_state;
 
       // --- PIECE 1: the STATE REGISTER (2.1) — the only memory; resets to IDLE ---
       always_ff @(posedge clk) begin
           if (rst) state <= IDLE;                 // known initial state
           else     state <= next_state;           // load next state each edge
       end
 
       // --- PIECE 2: the NEXT-STATE LOGIC (1.1) — a combinational case = the graph ---
       always_comb begin
           next_state = state;                     // DEFAULT-ASSIGN FIRST => latch-free
           case (state)
               IDLE: next_state = din ? S1   : IDLE;   // 1 -> S1,  0 -> stay
               S1:   next_state = din ? S1   : S2;     // 11 -> S1 (fresh 1), 10 -> S2
               S2:   next_state = din ? S3   : IDLE;   // 101 -> S3, 100 -> restart
               S3:   next_state = din ? S1   : S2;     // 1011 done -> S1 (overlap); 1010 -> S2
           endcase
       end
 
       // --- PIECE 3: the OUTPUT LOGIC — Mealy: found on S3 seeing din=1 (completes 1011) ---
       assign found = (state == S3) && din;
   endmodule

The three pieces are visible one to a block: the clocked always_ff is the state register, the always_comb case is the next-state logic (a direct transcription of the §3 table), and the assign found is the output logic. The clocked testbench drives a bit stream that contains overlapping matches and self-checks that found pulses on exactly the cycles the pattern completes — and that reset returns the machine to IDLE.

   module seq1011_tb;
       logic clk = 1'b0, rst, din, found;
       int   errors = 0;
 
       seq1011 dut (.clk(clk), .rst(rst), .din(din), .found(found));
       always #5 clk = ~clk;
 
       // Stimulus stream and the EXPECTED found for each bit (reference model).
       // Stream: 1 0 1 1 0 1 1  -> matches 1011 at bits [0..3] and, overlapping, [3..6].
       localparam int LEN = 7;
       logic [0:LEN-1] stream = 7'b1011011;
       logic [0:LEN-1] exp    = 7'b0001001;   // found asserts on the completing 1s
 
       initial begin
           rst = 1'b1; din = 1'b0;                 // hold reset -> state = IDLE
           @(posedge clk); #1;
           rst = 1'b0;
           for (int i = 0; i < LEN; i++) begin
               din = stream[i];
               #1;                                 // sample found in the SAME cycle (Mealy)
               assert (found === exp[i])
                   else begin $error("bit %0d din=%b found=%b exp=%b", i, din, found, exp[i]); errors++; end
               @(posedge clk);                     // advance the state register
           end
           // Reset must return the machine to IDLE (no spurious found afterwards).
           rst = 1'b1; din = 1'b1; #1;
           assert (found === 1'b0)
               else begin $error("found asserted while in reset"); errors++; end
           if (errors == 0) $display("PASS: 1011 detected on every completing bit incl. overlap; reset -> IDLE");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

The Verilog form is the same three pieces with reg/wire typing and localparam state codes instead of an enum. The always @(*) next-state block still leads with the default assignment.

   module seq1011 (
       input  wire clk,
       input  wire rst,                            // sync active-high reset to IDLE
       input  wire din,
       output wire found
   );
       // state enumeration as localparams (2-bit binary codes; encoding is 4.4's choice)
       localparam [1:0] IDLE = 2'd0,               // matched nothing
                        S1   = 2'd1,               // matched 1
                        S2   = 2'd2,               // matched 10
                        S3   = 2'd3;               // matched 101
       reg [1:0] state, next_state;
 
       // PIECE 1: STATE REGISTER
       always @(posedge clk) begin
           if (rst) state <= IDLE;
           else     state <= next_state;
       end
 
       // PIECE 2: NEXT-STATE LOGIC (default-first => latch-free)
       always @(*) begin
           next_state = state;                     // DEFAULT FIRST
           case (state)
               IDLE: next_state = din ? S1 : IDLE;
               S1:   next_state = din ? S1 : S2;
               S2:   next_state = din ? S3 : IDLE;
               S3:   next_state = din ? S1 : S2;
               default: next_state = IDLE;          // recover from any illegal code
           endcase
       end
 
       // PIECE 3: OUTPUT LOGIC (Mealy)
       assign found = (state == S3) & din;
   endmodule

   module seq1011_tb;
       reg  clk, rst, din;
       wire found;
       integer i, errors;
 
       reg [0:6] stream; reg [0:6] exp;
 
       seq1011 dut (.clk(clk), .rst(rst), .din(din), .found(found));
       always #5 clk = ~clk;
 
       initial begin
           errors = 0; clk = 1'b0;
           stream = 7'b1011011;                    // overlapping matches at [0..3] and [3..6]
           exp    = 7'b0001001;                    // found on the completing 1s
           rst = 1'b1; din = 1'b0;
           @(posedge clk); #1; rst = 1'b0;
           for (i = 0; i < 7; i = i + 1) begin
               din = stream[i];
               #1;                                 // Mealy: found valid same cycle
               if (found !== exp[i]) begin
                   $display("FAIL: bit %0d din=%b found=%b exp=%b", i, din, found, exp[i]);
                   errors = errors + 1;
               end
               @(posedge clk);
           end
           rst = 1'b1; din = 1'b1; #1;             // reset -> IDLE, no spurious found
           if (found !== 1'b0) begin
               $display("FAIL: found asserted during reset"); errors = errors + 1;
           end
           if (errors == 0) $display("PASS: 1011 detected incl. overlap; reset returns to IDLE");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

In VHDL the state enumeration is a first-class type — the cleanest of the three — and the three pieces map onto a clocked process, a combinational process (all), and a concurrent assignment. when others => is VHDL's latch-free default.

   library ieee;
   use ieee.std_logic_1164.all;
 
   entity seq1011 is
       port (
           clk   : in  std_logic;
           rst   : in  std_logic;                          -- sync active-high reset to IDLE
           din   : in  std_logic;
           found : out std_logic
       );
   end entity;
 
   architecture rtl of seq1011 is
       type state_t is (IDLE, S1, S2, S3);                 -- matched: -, 1, 10, 101
       signal state, next_state : state_t;
   begin
       -- PIECE 1: STATE REGISTER (only memory; resets to IDLE)
       reg_proc : process (clk)
       begin
           if rising_edge(clk) then
               if rst = '1' then state <= IDLE;
               else              state <= next_state;
               end if;
           end if;
       end process;
 
       -- PIECE 2: NEXT-STATE LOGIC (combinational; when others => latch-free)
       ns_proc : process (all)
       begin
           next_state <= state;                            -- DEFAULT FIRST
           case state is
               when IDLE => if din = '1' then next_state <= S1;   else next_state <= IDLE; end if;
               when S1   => if din = '1' then next_state <= S1;   else next_state <= S2;   end if;
               when S2   => if din = '1' then next_state <= S3;   else next_state <= IDLE; end if;
               when S3   => if din = '1' then next_state <= S1;   else next_state <= S2;   end if;
               when others => next_state <= IDLE;           -- total => no latch
           end case;
       end process;
 
       -- PIECE 3: OUTPUT LOGIC (Mealy: found on S3 seeing din=1)
       found <= '1' when (state = S3 and din = '1') else '0';
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
 
   entity seq1011_tb is
   end entity;
 
   architecture sim of seq1011_tb is
       signal clk   : std_logic := '0';
       signal rst   : std_logic := '1';
       signal din   : std_logic := '0';
       signal found : std_logic;
       constant STREAM : std_logic_vector(0 to 6) := "1011011";  -- overlap at [0..3],[3..6]
       constant EXP    : std_logic_vector(0 to 6) := "0001001";  -- found on completing 1s
   begin
       dut : entity work.seq1011 port map (clk => clk, rst => rst, din => din, found => found);
       clk <= not clk after 5 ns;
 
       stim : process
       begin
           rst <= '1'; din <= '0';
           wait until rising_edge(clk); wait for 1 ns;
           rst <= '0';
           for i in 0 to 6 loop
               din <= STREAM(i);
               wait for 1 ns;                               -- Mealy: found valid same cycle
               assert found = EXP(i)
                   report "1011 detect mismatch at bit index" severity error;
               wait until rising_edge(clk);
           end loop;
           rst <= '1'; din <= '1'; wait for 1 ns;           -- reset -> IDLE
           assert found = '0' report "found asserted during reset" severity error;
           report "seq1011 self-check complete" severity note;
           wait;
       end process;
   end architecture;

4b. The incomplete-next-state-case latch bug — buggy vs fixed, in all three HDLs

Pattern (b) is the signature FSM failure, shown here as buggy vs fixed RTL in each language and dramatized in §7. The bug is the same everywhere: the combinational next-state case omits a state (or an input branch) and has no default/others, so on that uncovered (state, din) pair the block assigns nothing to next_state — and "assign nothing in combinational logic" means "hold the old value," which is a latch. The FSM's next state then freezes, and the machine sticks in whatever state it was in.

   // BUGGY: the S3 branch is missing and there is NO default. When state == S3 the
   //        next-state block assigns NOTHING to next_state -> a LATCH holds next_state,
   //        so the FSM STICKS in S3 forever once it gets there. found never clears.
   module seq1011_bad (
       input  logic clk, rst, din,
       output logic found
   );
       typedef enum logic [1:0] { IDLE, S1, S2, S3 } state_t;
       state_t state, next_state;
 
       always_ff @(posedge clk)
           if (rst) state <= IDLE; else state <= next_state;
 
       always_comb begin
           // NO leading default assignment, and...
           case (state)
               IDLE: next_state = din ? S1 : IDLE;
               S1:   next_state = din ? S1 : S2;
               S2:   next_state = din ? S3 : IDLE;
               // ...S3 branch is MISSING and there is NO default -> LATCH on next_state
           endcase
       end
 
       assign found = (state == S3) && din;
   endmodule
 
   // FIXED: default-assign next_state first (or list every state). Every path drives
   //        next_state -> pure combinational next-state logic, no latch.
   module seq1011_good (
       input  logic clk, rst, din,
       output logic found
   );
       typedef enum logic [1:0] { IDLE, S1, S2, S3 } state_t;
       state_t state, next_state;
 
       always_ff @(posedge clk)
           if (rst) state <= IDLE; else state <= next_state;
 
       always_comb begin
           next_state = state;                     // DEFAULT FIRST => total assignment
           case (state)
               IDLE: next_state = din ? S1 : IDLE;
               S1:   next_state = din ? S1 : S2;
               S2:   next_state = din ? S3 : IDLE;
               S3:   next_state = din ? S1 : S2;   // the branch that was missing
           endcase
       end
 
       assign found = (state == S3) && din;
   endmodule

   module seq_bug_tb;
       logic clk = 1'b0, rst, din, found;
       int   errors = 0;
 
       // Point at seq1011_good to PASS; at seq1011_bad to watch the FSM stick in S3.
       seq1011_good dut (.clk(clk), .rst(rst), .din(din), .found(found));
       always #5 clk = ~clk;
 
       task step(input logic b); begin din = b; #1; @(posedge clk); end endtask
 
       initial begin
           rst = 1'b1; din = 1'b0; @(posedge clk); #1; rst = 1'b0;
           // Drive 1,0,1 to reach S3, then a completing 1 (found), then MORE bits.
           step(1'b1); step(1'b0); step(1'b1);     // now in S3
           din = 1'b1; #1;                          // completing bit: found must be 1
           assert (found === 1'b1) else begin $error("no found at 1011 completion"); errors++; end
           @(posedge clk);
           // After the completing 1 the GOOD FSM has moved on (to S1); found must clear.
           din = 1'b0; #1;
           assert (found === 1'b0)
               else begin $error("found STUCK high -> FSM did not leave S3 (latched next_state)"); errors++; end
           if (errors == 0) $display("PASS: FSM leaves S3 after completion; no stuck state");
           else             $display("FAIL: %0d mismatches (buggy FSM latches next_state and sticks)", errors);
           $finish;
       end
   endmodule

The Verilog buggy/fixed pair is the same story with reg next-state and always @(*). Reaching S3 and then driving another bit is what exposes the stuck FSM: the good machine leaves S3, the buggy one never does.

   // BUGGY: no S3 branch, no default -> next_state latches in S3 -> FSM sticks.
   module seq1011_bad (input wire clk, rst, din, output wire found);
       localparam [1:0] IDLE=2'd0, S1=2'd1, S2=2'd2, S3=2'd3;
       reg [1:0] state, next_state;
 
       always @(posedge clk)
           if (rst) state <= IDLE; else state <= next_state;
 
       always @(*) begin
           case (state)                             // NO default, S3 missing -> LATCH
               IDLE: next_state = din ? S1 : IDLE;
               S1:   next_state = din ? S1 : S2;
               S2:   next_state = din ? S3 : IDLE;
           endcase
       end
 
       assign found = (state == S3) & din;
   endmodule
 
   // FIXED: default-first assignment -> every path drives next_state, no latch.
   module seq1011_good (input wire clk, rst, din, output wire found);
       localparam [1:0] IDLE=2'd0, S1=2'd1, S2=2'd2, S3=2'd3;
       reg [1:0] state, next_state;
 
       always @(posedge clk)
           if (rst) state <= IDLE; else state <= next_state;
 
       always @(*) begin
           next_state = state;                      // DEFAULT FIRST
           case (state)
               IDLE: next_state = din ? S1 : IDLE;
               S1:   next_state = din ? S1 : S2;
               S2:   next_state = din ? S3 : IDLE;
               S3:   next_state = din ? S1 : S2;    // the missing branch
               default: next_state = IDLE;          // recover from illegal codes
           endcase
       end
 
       assign found = (state == S3) & din;
   endmodule

   module seq_bug_tb;
       reg  clk, rst, din;
       wire found;
       integer errors;
 
       // Bind to seq1011_good to PASS; to seq1011_bad to observe the stuck FSM.
       seq1011_good dut (.clk(clk), .rst(rst), .din(din), .found(found));
       always #5 clk = ~clk;
 
       task step; input b; begin din = b; #1; @(posedge clk); end endtask
 
       initial begin
           errors = 0; clk = 1'b0;
           rst = 1'b1; din = 1'b0; @(posedge clk); #1; rst = 1'b0;
           step(1'b1); step(1'b0); step(1'b1);      // reach S3
           din = 1'b1; #1;
           if (found !== 1'b1) begin $display("FAIL: no found at completion"); errors=errors+1; end
           @(posedge clk);
           din = 1'b0; #1;
           if (found !== 1'b0) begin
               $display("FAIL: found STUCK -> FSM latched in S3"); errors = errors + 1;
           end
           if (errors == 0) $display("PASS: FSM exits S3, found clears (no latch)");
           else             $display("FAIL: %0d mismatches", errors);
           $finish;
       end
   endmodule

In VHDL the same bug appears when the next-state case omits when others => (or leaves a when branch that does not assign next_state). The when others => arm — plus the leading default — is exactly VHDL's answer; omit it and the synthesis tool infers a latch to hold next_state on the unlisted state.

   library ieee;
   use ieee.std_logic_1164.all;
 
   -- BUGGY: the case omits S3 and has NO "when others" -> next_state unassigned there
   --        -> LATCH -> the FSM sticks in S3.
   entity seq1011_bad is
       port (clk, rst, din : in std_logic; found : out std_logic);
   end entity;
   architecture rtl of seq1011_bad is
       type state_t is (IDLE, S1, S2, S3);
       signal state, next_state : state_t;
   begin
       process (clk) begin
           if rising_edge(clk) then
               if rst = '1' then state <= IDLE; else state <= next_state; end if;
           end if;
       end process;
       process (all) begin
           case state is                            -- no default, no "when others" -> LATCH
               when IDLE => if din = '1' then next_state <= S1; else next_state <= IDLE; end if;
               when S1   => if din = '1' then next_state <= S1; else next_state <= S2;   end if;
               when S2   => if din = '1' then next_state <= S3; else next_state <= IDLE; end if;
               when others => null;                 -- assigns NOTHING for S3 -> latch
           end case;
       end process;
       found <= '1' when (state = S3 and din = '1') else '0';
   end architecture;
 
   -- FIXED: default-first assignment + a real "when others" -> total assignment, no latch.
   entity seq1011_good is
       port (clk, rst, din : in std_logic; found : out std_logic);
   end entity;
   architecture rtl of seq1011_good is
       type state_t is (IDLE, S1, S2, S3);
       signal state, next_state : state_t;
   begin
       process (clk) begin
           if rising_edge(clk) then
               if rst = '1' then state <= IDLE; else state <= next_state; end if;
           end if;
       end process;
       process (all) begin
           next_state <= state;                     -- DEFAULT FIRST
           case state is
               when IDLE => if din = '1' then next_state <= S1; else next_state <= IDLE; end if;
               when S1   => if din = '1' then next_state <= S1; else next_state <= S2;   end if;
               when S2   => if din = '1' then next_state <= S3; else next_state <= IDLE; end if;
               when S3   => if din = '1' then next_state <= S1; else next_state <= S2;   end if;
               when others => next_state <= IDLE;   -- total => no latch
           end case;
       end process;
       found <= '1' when (state = S3 and din = '1') else '0';
   end architecture;

   library ieee;
   use ieee.std_logic_1164.all;
 
   entity seq_bug_tb is
   end entity;
   architecture sim of seq_bug_tb is
       signal clk, rst, din, found : std_logic := '0';
   begin
       -- Bind to seq1011_good to PASS; to seq1011_bad to observe the stuck FSM.
       dut : entity work.seq1011_good port map (clk => clk, rst => rst, din => din, found => found);
       clk <= not clk after 5 ns;
       stim : process
           procedure step(b : std_logic) is
           begin din <= b; wait for 1 ns; wait until rising_edge(clk); end procedure;
       begin
           rst <= '1'; din <= '0'; wait until rising_edge(clk); wait for 1 ns; rst <= '0';
           step('1'); step('0'); step('1');         -- reach S3
           din <= '1'; wait for 1 ns;
           assert found = '1' report "no found at 1011 completion" severity error;
           wait until rising_edge(clk);
           din <= '0'; wait for 1 ns;
           assert found = '0'
               report "found STUCK -> FSM latched next_state and did not leave S3" severity error;
           report "seq_bug self-check complete" severity note;
           wait;
       end process;
   end architecture;

Across all three languages the lesson is one sentence: assign next_state on every path — a leading next_state = state; default in SV/Verilog, a when others => in VHDL — or the next-state logic becomes a latch and the FSM freezes.

5. Verification Strategy

An FSM's correctness is a state graph, so verification proves three things: the machine visits the right states in response to inputs, it drives the right outputs in those states, and it can never get stuck or start in an illegal state. The self-checking testbench idea is a reference model driven by the same stimulus, checked cycle-by-cycle.

From the reset state, every input sequence drives the FSM through the intended states and outputs; reset always returns it to the initial state; and every state has a defined exit for every input (no stuck or dead states).

The verification checklist — the enumerated properties and corner cases a learner must check, mapping onto the §4 testbenches:

• Sequence-driven, self-checking (reference model). Drive a bit stream and, in parallel, compute the expected found for each cycle from a golden model (a software or golden-RTL reference), asserting found === expected every clock. The §4a testbenches do exactly this: SV assert (found === exp[i]), Verilog if (found !== exp[i]) $display("FAIL…"), VHDL assert found = EXP(i) … severity error. Because found is checked every cycle against the model, this proves the whole graph, not a spot check.
• Overlap coverage (the corner case the graph exists for). Drive a stream with overlapping matches (1011011 → two detections sharing the middle 1) and confirm found pulses on both completions. A naive detector that falls back to IDLE after a match instead of S1 will detect the first 1011 and miss the overlapping second — the overlap stream is what catches a wrong fall-back edge.
• Reset returns to the initial state. Assert reset mid-sequence and confirm the machine is back in IDLE with found low, then that it detects correctly from scratch afterwards. A machine that does not reset cleanly, or resets to a non-IDLE state, is caught here (this is the §7 second failure).
• Every state reachable, every state has a defined exit (no stuck/dead states). Two structural properties. Reachability: a directed test that walks the FSM into every state (IDLE→S1→S2→S3 and the fall-backs) — an unreachable state is dead logic. Liveness / no-stuck: from every state, both din values must move the machine to a defined next state; the §4b bug testbench proves this by reaching S3 and asserting the machine leaves it — a found that stays high because the FSM latched in S3 is the stuck-state signature. Conceptually: "no (state, din) pair leaves next_state undefined."
• Failure modes (tie to the DebugLab). The incomplete next-state case (§7) makes the FSM freeze in the uncovered state — caught by driving into that state and checking it exits. A missing reset (§7 second row) leaves the machine in an X/illegal state at power-up — caught by asserting the post-reset state is IDLE before any real stimulus.
• Expected waveform. On a correct run, state steps IDLE→S1→S2→S3 as 1,0,1 arrive; found pulses high for exactly one cycle on each completing 1 and is low otherwise; after reset, state is IDLE and found is 0. The visual signature of the bug is state (or next_state) that stops changing while inputs keep arriving — an FSM frozen mid-graph — or a found that never clears.

6. Common Mistakes

Incomplete next-state case / missing default → inferred latch (the signature bug). In the combinational next-state block (SV always_comb, Verilog always @(*), VHDL combinational process), if some (state, din) path does not assign next_state, the tool must "remember" the old next-state to honour it — memory in combinational logic is a latch. The FSM then holds next_state and can stick in the uncovered state. Fix: the default-assignment discipline — lead with next_state = state; (or = IDLE;), and in VHDL add when others =>. Full post-mortem in §7; buggy-vs-fixed RTL in §4b.

Dead or unreachable states. A state the transition graph can never enter is dead logic — wasted, and often a symptom of a wrong edge (you meant to transition into it but the case never does). Conversely, a state with no exit for some input is a stuck state. Verification must walk into every state and out of it on both inputs; a state you cannot reach or cannot leave is a graph bug.

Forgetting reset to a known state → powers up illegal. The state register is memory, so without a reset it powers up X (sim) or a random binary code (silicon). If that code is not one of the defined states, the machine is in an illegal state the case may not handle, and it may never reach a legal one. Always reset the state register to a defined initial state; for safety-critical FSMs, also give the case a default/when others that steers illegal codes back to IDLE (the subject of 4.5, Safe FSMs).

Mixing blocking and non-blocking assignments. The state register must use non-blocking (<=) in its clocked block — it is sequential — while the next-state and output logic must use blocking (=) with a full assignment in their combinational blocks. Using = in the clocked state-register block, or <= in the combinational next-state block, produces simulation/synthesis mismatches and races (this is the v1 blocking/non-blocking rule applied to the FSM's two block types).

Encoding the state graph wrong (a missing or wrong transition). The subtle, high-cost FSM bug: the RTL compiles, has no latch, resets fine — but a transition is wrong. For the 1011 detector, falling back from S3 on a mismatch to IDLE instead of S2, or from S3 on a match to IDLE instead of S1, breaks overlap — the machine detects some matches and silently misses the overlapping ones. There is no tool warning for a wrong-but-complete graph; only the reference-model testbench with an overlap stream (§5) catches it. Draw the graph, build the table, and verify against a golden model.

7. DebugLab

The engineering lesson: an FSM has exactly one memory element — the state register — and two combinational functions, and both failure modes come from mistreating that split. Leave the next-state logic incomplete and it stops being combinational: it infers a latch that can trap the machine in a state it can never leave (the tell is a hang that only appears once the input reaches the uncovered state). Leave the state register un-reset and the machine has no defined place to start: X in sim, a random legal-or-illegal code in silicon (the tell is a power-up-dependent, board-dependent hang). Two habits make both impossible, and they are identical across SystemVerilog, Verilog, and VHDL: default-assign next_state at the top of the combinational block (a leading next_state = state;, or a when others =>), and reset the state register to a known initial state — with an illegal-state default in the case when the FSM must be safe (4.5).

8. Interview Q&A

9. Exercises

Design and reasoning exercises — no syntax drills. Each rehearses the "draw the graph, then transcribe the three pieces" habit.

Exercise 1 — Draw a state diagram for a spec

Design an FSM that detects the non-overlapping sequence 110 on a serial input din (one bit per clock), asserting found for one cycle each time it completes, and then starting the match over from scratch (no overlap). Draw the state graph: name each state by the prefix it represents, give the transition on din=0 and din=1 from every state, and mark where found asserts. Then write the state-transition table. Finally, state in one line where this graph differs from the overlapping 1011 detector's — specifically, what the fall-back edge after a completed match looks like when overlap is not allowed.

Exercise 2 — Find the wrong transition

An engineer's 1011 overlapping detector compiles, has no inferred latch, resets cleanly to IDLE, and passes on the stream 1011 (one detection). But on 1011011 it detects only one match instead of two. Without seeing the RTL, name the single most likely bug (which transition edge is wrong), explain why it breaks overlap specifically while leaving the single-match case correct, and give the exact stimulus + check you would add to a self-checking testbench so this class of bug can never pass again.

Exercise 3 — Map the three pieces

Take the 1011 RTL from §4a and, for each of its three constructs — the clocked always_ff/process, the combinational always_comb/process (all) case, and the assign found/concurrent assignment — state (i) which of the three FSM pieces it is, (ii) what hardware it synthesizes to (flops, mux/gates), and (iii) the one discipline that keeps that piece correct (reset, default-assignment, or Moore/Mealy choice). Then explain why the state register uses non-blocking <= while the next-state block uses blocking =.

Exercise 4 — Moore-ify the detector, and count the cost

Rewrite the 1011 detector as a Moore machine: add a DONE state that the machine enters after the completing 1, and assert found whenever state == DONE. Draw the modified graph (what does DONE transition to on din=0 and din=1, preserving overlap?), state how many cycles later found now asserts compared with the Mealy version, and give one concrete situation where the Moore (registered, glitch-free, one-cycle-late) output is the right choice and one where the Mealy (same-cycle) output is.

10. Related Tutorials

Continue in RTL Design Patterns (sibling and forward links unlock as they ship):

• Moore vs Mealy FSMs — Chapter 4.2; the output-logic distinction previewed here — outputs from state alone (Moore, registered, glitch-free, one cycle later) vs state + inputs (Mealy, same-cycle, can glitch).
• FSM Coding Styles — Chapter 4.3; the one- vs two- vs three-block partitioning of the three pieces, and why the separate combinational next-state block makes the latch-free discipline obvious.
• FSM State Encoding — Chapter 4.4; how the named states here become bits — binary vs one-hot vs gray — and the area/speed trade-off the RTL is deliberately independent of.
• Safe FSMs & Latch-Free Outputs — Chapter 4.5; the illegal-state recovery (default/when others back to IDLE) and registered-output discipline that hardens the machine against the §7 failures.
• FSM + Datapath — Chapter 4.6; the FSM as a controller steering a datapath (the control/data split), the shape of every real sequencer.
• FSM Worked Example — Chapter 4.7; a full controller built end to end applying everything in this chapter.

Backward / in-track dependencies:

• The Register Pattern (D-FF) — Chapter 2.1; the state register is a register pattern — the FSM's only memory element.
• Multiplexers (2:1, N:1, one-hot) — Chapter 1.1; the next-state case is a mux over the current state and inputs, and the incomplete-case latch is the same failure as the mux's.
• Synchronous Reset — Chapter 2.3; the sampled-on-the-edge reset that returns the state register to IDLE.
• Reset Strategy in Practice — Chapter 2.5; how the FSM's reset is asserted async / deasserted sync so the machine leaves reset on a clean edge.
• Register with Enable / Load — Chapter 2.2; the hold-vs-update mux inside a register — the same "load next value or keep current" the state register performs.
• Up/Down Counters — Chapter 3; a counter is a degenerate FSM (a fixed linear state graph) — the contrast that shows why branching control needs a full FSM.

Verilog v1 prerequisites (the grammar the three pieces transcribe into):

• Case Statements — the construct behind the next-state logic, and where default and latch inference live.
• If-Else Statements — the din ? … : … / if din = '1' branch inside each state's transition.
• Blocking and Non-Blocking Assignments — why the state register uses non-blocking (<=) and the combinational next-state/output logic uses blocking (=).
• Parameters — the localparam/parameter state codes that name the states in Verilog.

11. Summary

• An FSM is the RTL pattern for control — anything that sequences or decides is one. Combinational logic sees only this cycle and a counter only counts; neither can express "it depends on where we are in the process." A finite state machine captures that with named states, transition rules, and state-dependent outputs — the single highest-leverage RTL skill, because every controller, protocol front-end, and sequencer is an FSM.
• It is exactly three pieces you already know. A state register (2.1) that holds the current state and resets to a known initial state; next-state logic (1.1) — a combinational case/mux that picks the next state from the current state and inputs; and output logic — Moore (from state alone) or Mealy (state + inputs). The state register is the only memory; the other two are pure combinational.
• Design the state graph first; the RTL is a transcription. The engineering is in the graph — states, the transition on each input, the output per state — captured as a state-transition table. The 1011 overlapping detector's whole difficulty is the fall-back edges (after a match or mismatch, fall back to the longest partial match, not to IDLE), and getting those right is the design; the three pieces are mechanical once the graph is correct.
• Two disciplines keep an FSM correct, in every HDL. Default-assign next_state on every path (a leading next_state = state; in SV/Verilog, a when others => in VHDL) or an incomplete next-state case infers a latch that freezes the machine mid-sequence (§7). And reset the state register to a known state or the FSM powers up X/illegal and never starts. Verify by driving an overlapping stream against a reference model, checking found every cycle, confirming reset returns to IDLE, and proving every state is reachable and has a defined exit — self-checking clocked testbenches shown here in SystemVerilog, Verilog, and VHDL.
• Synthesis reality: three flops-and-gates blocks, and two previews. The state register synthesizes to log2(#states) flops (binary) or one flop per state (one-hot); the next-state logic to a mux/gate network; the output logic to gates (Moore) or gates fed by inputs (Mealy). The encoding trade-off — binary (fewest flops) vs one-hot (fastest next-state, simplest decode, more flops) — is 4.4, and the coding-style trade-off (one vs two vs three blocks, registered vs combinational outputs) is 4.3; this page's RTL is written against named states precisely so those choices stay independent of the graph.