What is state encoding and which type should I use?

State encoding assigns binary values to states. Binary encoding uses log2(N) flip-flops for N states (compact). One-hot encoding uses N flip-flops — exactly one is '1' at a time (fast, fewer logic levels, preferred on FPGAs). Gray encoding changes only one bit per transition (low switching, good for power). FPGAs favor one-hot because they have abundant flip-flops and small LUTs. ASICs often use binary or gray encoding to minimize area.

How do you design an FSM from a word description?

Step 1: Identify all distinct states the system can be in. Step 2: Determine inputs that cause transitions and outputs for each state/transition. Step 3: Draw the state diagram (bubbles = states, arrows = transitions labeled with input/output). Step 4: Create the state table listing current state, input, next state, output. Step 5: Encode states into binary. Step 6: Derive next-state logic (K-map or boolean) and output logic. Step 7: Implement with flip-flops and combinational logic or write Verilog.

What is a sequence detector FSM?

A sequence detector is an FSM that asserts its output when a specific pattern of input bits has been received. For example, a '1011' sequence detector monitors a serial bit stream and outputs 1 when the last 4 bits were 1,0,1,1. Overlapping detectors allow the last bits of one match to count toward the next. They are used in communication protocols, pattern recognition, and error detection circuits.

How do you write an FSM in Verilog?

The standard 3-always-block style separates (1) state register: synchronous flip-flop that updates state on clock edge, (2) next-state logic: combinational always block computing next_state from state and inputs, (3) output logic: combinational block for Mealy or registered assignment for Moore. This separation keeps synthesis clean and timing analysis straightforward. Use parameter or localparam to name states, and a case statement for transitions.

What is the difference between synchronous and asynchronous reset in an FSM?

Synchronous reset only takes effect on the active clock edge — the FSM resets on the next rising edge after rst is asserted. This is glitch-immune and preferred in most FPGA and ASIC flows. Asynchronous reset takes effect immediately regardless of the clock — it appears in the sensitivity list (always @(posedge clk or posedge rst)). Async reset gives faster response but can cause metastability if released near a clock edge. Most design guidelines prefer synchronous reset.

Topic 14 · Digital Electronics

Finite State Machine
Mealy vs Moore

Q: What is the difference between a Mealy and Moore FSM?

In a Moore FSM, outputs depend only on the current state — every state has a fixed output regardless of inputs. In a Mealy FSM, outputs depend on both the current state AND the current inputs, so output can change immediately when input changes (even before a clock edge). Moore machines typically need more states but are safer from glitches. Mealy machines respond one clock cycle faster and usually need fewer states.

Q: What is a safe FSM and why does it matter?

A safe FSM handles illegal/unreachable states by transitioning to a known safe state (usually reset). In hardware, power-on conditions or radiation can corrupt state registers, landing in unused encodings. Without a default case in Verilog, synthesis may optimize away the unused states — if entered, the FSM hangs indefinitely. Adding 'default: state <= RESET;' in the case statement prevents lockup and is required in safety-critical designs.

From state diagrams to synthesizable Verilog — master FSM design with interactive traffic light and sequence detector simulators.

Moore FSM Mealy FSM State Diagram One-Hot Encoding Traffic Light Sequence Detector Verilog RTL

Mealy vs Moore — Core Difference

Moore FSM

Output depends only on current state
Output changes on clock edge (synchronized)
Glitch-free — no combinational output path
Needs more states than Mealy for same behavior
State diagram: output labeled inside the state bubble
Preferred in most RTL design guidelines

Mealy FSM

Output depends on state AND input
Output can change when input changes (async)
Can glitch if inputs have glitches
Fewer states needed — responds one cycle earlier
State diagram: output labeled on the transition arrow
Used when latency matters (serial protocols)

Property	Moore	Mealy
Output function	f(state)	f(state, input)
Output timing	Registered (safe)	Combinational (fast)
Number of states	More	Fewer
Glitch risk	None	Possible
Response latency	1 clock later	Same clock cycle
Diagram notation	State/Output	Input/Output on arc

How to Design an FSM — Step by Step

Identify states — Each distinct condition the system can be in becomes a state. Ask: "what information must the system remember?"
Determine inputs and outputs — Inputs cause transitions. Outputs are either per-state (Moore) or per-transition (Mealy).
Draw the state diagram — Circles = states, arrows = transitions labeled with input (and output for Mealy).
Build the state table — Tabulate: current state × input → next state + output.
Choose state encoding — Binary, one-hot, Gray, or Johnson. FPGAs: prefer one-hot.
Derive next-state logic — K-map or boolean algebra from state table. For Verilog: let synthesis handle it.
Implement and verify — 3-always-block Verilog + testbench with all state/input combinations.

State Encoding Comparison

Encoding	Flip-flops	Logic Complexity	Best For
Binary	log₂(N)	High (complex decode)	ASIC area-optimized
One-Hot	N (one per state)	Low (simple decode)	FPGA (abundant FFs)
Gray	log₂(N)	Medium	Low power, counters
Johnson	N/2	Medium	Ring counter variants

Interactive Simulator — Traffic Light Controller (Moore)

Moore FSM: the output (which light is on) depends only on the current state. Inputs only trigger transitions.

Mode:

State: RED

Lights: R=ON Y=OFF G=OFF

RED

YEL

GRN

Clock simulation — press Step

State	Meaning	Input=0 → next/out	Input=1 → next/out
S0	Reset / start	S0 / 0	S1 / 0
S1	Got '1'	S2 / 0	S1 / 0
S2	Got '10'	S0 / 0	S3 / 1 ✓
S3	Got '101'	S2 / 0	S1 / 0

Verilog — 3-Always-Block Style

Moore FSM — Traffic Light Controller

// Moore FSM: output depends only on state
module traffic_light (
  input  logic       clk, rst_n,
  output logic [2:0] lights   // {R, Y, G}
);
  typedef enum logic [1:0] {RED, RED_GRN, GREEN, YELLOW} state_t;
  state_t state, next;

  // 1. State register
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= RED;
    else        state <= next;

  // 2. Next-state logic
  always_comb case (state)
    RED:     next = RED_GRN;
    RED_GRN: next = GREEN;
    GREEN:   next = YELLOW;
    YELLOW:  next = RED;
    default: next = RED;
  endcase

  // 3. Output logic (Moore: only depends on state)
  always_comb case (state)
    RED:     lights = 3'b100;
    RED_GRN: lights = 3'b110;
    GREEN:   lights = 3'b001;
    YELLOW:  lights = 3'b010;
    default: lights = 3'b100;
  endcase
endmodule

Mealy FSM — Sequence Detector (101)

// Mealy FSM: output depends on state AND input
module seq_det_101 (
  input  logic clk, rst_n, x,
  output logic z
);
  typedef enum logic [1:0] {S0, S1, S2, S3} state_t;
  state_t state, next;

  // 1. State register
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= S0;
    else        state <= next;

  // 2. Next-state + output (Mealy: both depend on state AND x)
  always_comb begin
    next = S0; z = 1'b0;
    case (state)
      S0: if (x) begin next = S1; z = 0; end
          else   begin next = S0; z = 0; end
      S1: if (x) begin next = S1; z = 0; end
          else   begin next = S2; z = 0; end
      S2: if (x) begin next = S3; z = 1; end // match: 101
          else   begin next = S0; z = 0; end
      S3: if (x) begin next = S1; z = 0; end
          else   begin next = S2; z = 0; end
    endcase
  end
endmodule

One-Hot Encoding (FPGA-Preferred)

// One-hot: N states → N flip-flops, exactly one '1' at a time
module fsm_onehot (
  input  logic clk, rst_n, in_a, in_b,
  output logic out
);
  typedef enum logic [3:0] {
    IDLE  = 4'b0001,
    LOAD  = 4'b0010,
    PROC  = 4'b0100,
    DONE  = 4'b1000
  } state_t;
  state_t state;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else case (state)
      IDLE: state <= in_a ? LOAD : IDLE;
      LOAD: state <= PROC;
      PROC: state <= in_b ? DONE : PROC;
      DONE: state <= IDLE;
      default: state <= IDLE; // safe — handles bit errors
    endcase

  assign out = (state == DONE);
endmodule

Safe FSM — Handling Illegal States

// Always add default — prevents lockup from cosmic ray / power glitch
always_comb case (state)
  IDLE:  next = START;
  START: next = in ? RUN : IDLE;
  RUN:   next = done ? DONE : RUN;
  DONE:  next = IDLE;
  default: next = IDLE; // ← CRITICAL for safety
endcase

Common FSM Patterns in RTL Design

Pattern	Use Case	States
Handshake FSM	AXI, APB, UART — valid/ready protocol	IDLE → REQ → ACK → IDLE
Timeout FSM	Watchdog, protocol timeout detection	IDLE → WAIT (counter) → TIMEOUT
Arbitration FSM	Bus arbiter, shared resource	IDLE → GRANT_A / GRANT_B → RELEASE
Control FSM	Memory controller, DMA	IDLE → FETCH → DECODE → EXECUTE
Sequence Detector	Pattern match in serial data	S0→S1→…→MATCH
Power Gating FSM	Low-power design, ISO/clamp control	ON → ISOLATE → OFF → RESTORE → ON

Interview tip: When asked to design any controller — traffic light, vending machine, elevator, UART TX — the answer is always: identify states first, draw the diagram, then write 3-always-block Verilog with a default case.

Frequently Asked Questions

What is the difference between a Mealy and Moore FSM?

Moore: output = f(state). Mealy: output = f(state, input). Moore is glitch-free; Mealy responds one cycle faster and needs fewer states.

Why is one-hot encoding preferred on FPGAs?

FPGAs have abundant flip-flops and small LUTs. One-hot decoding is just checking a single bit — minimal LUT depth. Binary encoding would need log₂(N) bits decoded through logic — more LUT levels, slower.

What is a safe FSM and why does it matter?

A safe FSM always transitions back to a known state when in an illegal encoding. Adding default: state <= RESET prevents the FSM from hanging if radiation or a glitch corrupts the state register.

How many always blocks should a Verilog FSM use?

The industry-standard 3-always-block style: (1) state register — always_ff with clock/reset, (2) next-state logic — always_comb, (3) output logic — always_comb for Mealy or Moore. This separation produces clean synthesis and straightforward STA.

Finite State MachineMealy vs Moore