Industrial Finite State Machines & Protocol Controllers
Datapaths do the work; state machines decide when. Almost all control logic in a chip is an FSM, and almost every RTL interview contains one. This volume builds the same sequence detector five different ways, then applies the winning style to two real protocol controllers - and finishes with what happens when a cosmic ray flips one of your state bits.
4.1 FSM classification: Moore, Mealy & Medvedev
Every synchronous state machine has the same skeleton: a state register, combinational next-state logic, and output logic. The three classifications differ in exactly one thing - what the output logic is allowed to look at.
| Moore | Mealy | Medvedev | |
|---|---|---|---|
| Output depends on | State only | State + inputs | Is the state register |
| State count | More | Fewer | Most - encoding is constrained |
| Reacts | One cycle later | Same cycle | One cycle later |
| Output glitches | Only from state decode | Yes - follows input glitches | Never - straight off a flop |
| Input-to-output path | None | Combinational | None |
| Safe to cross clock domains? | With care | No | Yes |
The running example: an overlapping 1011 detector
Assert an output whenever the last four bits of a serial stream were 1011.
Overlapping means a detection does not reset the machine - the tail of one
match may begin the next. This is the single most common FSM interview question.
1011 that the input stream currently ends with. That
framing is the whole trick: from 1011 on a 0 you go to
10, because the stream now ends …10110 and its longest useful
suffix is 10.
How to derive any sequence detector under pressure
Do not try to reason about the transitions directly. Instead: name each state after the
longest prefix of the target that the stream currently ends with. Then for
each state and each input bit, append the bit and ask "what is the longest prefix now?"
The transitions fall out mechanically, and overlapping handling is automatic. This is a
hand-run of the KMP failure function.
Moore vs Mealy on the same input
1011) form a second match that reuses the tail of
the first.
module seq1011_mealy (
input wire clk,
input wire rst_n,
input wire din,
output wire detected
);
// Only FOUR states - the Mealy machine does not need a state to
// "remember that it just matched", because the match is announced on
// the transition itself.
localparam [1:0] S0 = 2'd0, S1 = 2'd1, S10 = 2'd2, S101 = 2'd3;
reg [1:0] state, next_state;
always @(posedge clk or negedge rst_n)
if (!rst_n) state <= S0;
else state <= next_state;
always @(*) begin
case (state)
S0 : next_state = din ? S1 : S0;
S1 : next_state = din ? S1 : S10;
S10 : next_state = din ? S101 : S0;
S101: next_state = din ? S1 : S10; // match, and "1" is a new prefix
default: next_state = S0;
endcase
end
// THIS line is what makes it Mealy: the output reads din directly, so
// there is a combinational path from the din pin to the detected pin.
assign detected = (state == S101) && din;
endmodule
4.2 The three FSM coding styles
The same state machine can be written three ways. They are not stylistic preferences - they produce different hardware with different timing characteristics.
// Everything in one clocked block. State and output both registered.
module seq1011_style1 (
input wire clk,
input wire rst_n,
input wire din,
output reg detected
);
localparam [2:0] S0=3'd0, S1=3'd1, S10=3'd2, S101=3'd3, S1011=3'd4;
reg [2:0] state;
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
state <= S0;
detected <= 1'b0;
end else begin
detected <= 1'b0; // default every cycle
case (state)
S0 : state <= din ? S1 : S0;
S1 : state <= din ? S1 : S10;
S10 : state <= din ? S101 : S0;
S101 : begin
state <= din ? S1011 : S10;
if (din) detected <= 1'b1; // arrives WITH the S1011 state
end
S1011: state <= din ? S1 : S10;
default: state <= S0;
endcase
end
end
endmodule
// Clocked state register + ONE combinational block doing next-state
// AND output together. The textbook favourite.
module seq1011_style2 (
input wire clk,
input wire rst_n,
input wire din,
output reg detected
);
localparam [2:0] S0=3'd0, S1=3'd1, S10=3'd2, S101=3'd3, S1011=3'd4;
reg [2:0] state, next_state;
// --- 1. state register ---
always @(posedge clk or negedge rst_n)
if (!rst_n) state <= S0;
else state <= next_state;
// --- 2. next state + output, both combinational ---
always @(*) begin
next_state = state; // defaults first, so no latch (Volume 1.5)
detected = 1'b0;
case (state)
S0 : next_state = din ? S1 : S0;
S1 : next_state = din ? S1 : S10;
S10 : next_state = din ? S101 : S0;
S101 : next_state = din ? S1011 : S10;
S1011: begin
detected = 1'b1; // COMBINATIONAL - can glitch
next_state = din ? S1 : S10;
end
default: next_state = S0;
endcase
end
endmodule
// Clocked state register + combinational next-state + CLOCKED output.
// This is what production RTL looks like.
module seq1011_style3 (
input wire clk,
input wire rst_n,
input wire din,
output reg detected
);
localparam [2:0] S0=3'd0, S1=3'd1, S10=3'd2, S101=3'd3, S1011=3'd4;
reg [2:0] state, next_state;
// --- 1. state register ---
always @(posedge clk or negedge rst_n)
if (!rst_n) state <= S0;
else state <= next_state;
// --- 2. next-state logic ONLY. No outputs in here. ---
always @(*) begin
next_state = state;
case (state)
S0 : next_state = din ? S1 : S0;
S1 : next_state = din ? S1 : S10;
S10 : next_state = din ? S101 : S0;
S101 : next_state = din ? S1011 : S10;
S1011: next_state = din ? S1 : S10;
default: next_state = S0;
endcase
end
// --- 3. output register ---
// Decode from NEXT_STATE, not state. Decoding from `state` would put
// the output one cycle behind the state it is describing.
always @(posedge clk or negedge rst_n)
if (!rst_n) detected <= 1'b0;
else detected <= (next_state == S1011);
endmodule
| Style 1 one process |
Style 2 two process |
Style 3 three process |
|
|---|---|---|---|
| Outputs registered | Yes | No - combinational | Yes |
| Glitch-free outputs | Yes | No | Yes |
| Output drives a clean path | Straight off a flop | Flop → decode → destination | Straight off a flop |
| Readability | State and output logic tangled | Clear | Clearest - one job per block |
| Easy to add outputs | Edit every branch | Edit the case | Add one line to block 3 |
| Verdict | Fine for tiny machines | Fine if outputs feed more logic anyway | The default choice |
Why style 3 dominates at big semiconductor companies
A registered output leaves the module with the full clock period
available to reach its destination - nothing but wire delay stands between the flop and
the module boundary. A style-2 combinational output burns part of the budget on decode
logic before it even leaves the block, and that decode delay lands in someone else's
timing path. On a large chip assembled from many blocks, "all module outputs are
registered" is often a hard design rule for exactly this reason.
The
next_state = state; default line
Every combinational block here opens by assigning defaults. That is Volume 1.5's latch
rule applied to FSMs: without it, any state whose case branch forgets to
assign next_state infers a latch, and your state machine acquires a hidden
extra memory element that no one designed.
4.3 State encoding: binary, Gray & one-hot
The state names are symbolic; the numbers behind them are a real design decision that trades flip-flop count against decode depth.
| Encoding | Flops for 5 states | Test for "am I in S101?" | Best for |
|---|---|---|---|
| Binary | 3 | state == 3'b011 - 3-input AND | ASIC, small machines, flop-limited designs |
| Gray | 3 | state == 3'b010 - 3-input AND | Low power/noise: one bit toggles per step |
| One-hot | 5 | state[3] - a single wire | FPGA, large machines, timing-critical decode |
// One-hot: one bit per state. Every decode becomes a single bit test,
// so the next-state and output logic collapse to almost nothing.
localparam [4:0] S0 = 5'b00001,
S1 = 5'b00010,
S10 = 5'b00100,
S101 = 5'b01000,
S1011 = 5'b10000;
reg [4:0] state, next_state;
always @(*) begin
next_state = 5'b0;
// Index by BIT, not by value. Each line is one LUT input deep.
if (state[0]) next_state = din ? S1 : S0;
if (state[1]) next_state = din ? S1 : S10;
if (state[2]) next_state = din ? S101 : S0;
if (state[3]) next_state = din ? S1011 : S10;
if (state[4]) next_state = din ? S1 : S10;
end
// Output decode is literally one wire - no comparator at all.
assign detected = state[4];
Your synthesis tool probably already re-encoded it
Write symbolic
localparam states and modern tools will pick the encoding for
you - often silently converting your careful binary constants to one-hot on an FPGA. If
you need control, say so explicitly rather than fighting it:
(* fsm_encoding = "one_hot" *) on Xilinx/AMD,
(* syn_encoding = "onehot" *) on Synopsys/Lattice. And check the synthesis
report - it tells you which encoding it actually used.
4.4 Industrial FSM projects
Sequence detectors are exam questions. Here are two machines you will genuinely meet: a UART receiver and an APB bus controller.
A UART receiver
The receiver has no clock from the transmitter - it must recover bit timing from the data itself. The standard technique is oversampling: run a tick generator at 16× the baud rate, use the start bit's falling edge to align, then sample each bit at its midpoint, as far as possible from both edges.
module uart_rx #(
parameter OS = 16 // oversampling factor
) (
input wire clk,
input wire rst_n,
input wire tick, // one pulse per 1/OS of a bit period
input wire rx_sync, // rx pin, ALREADY 2-FF synchronized
output reg [7:0] data,
output reg valid, // 1-cycle pulse: byte captured
output reg frame_err // 1-cycle pulse: stop bit was low
);
localparam [1:0] IDLE = 2'd0, START = 2'd1, DATA = 2'd2, STOP = 2'd3;
reg [1:0] state, next_state;
reg [4:0] tick_cnt; // counts ticks within one bit
reg [2:0] bit_cnt; // 0..7
reg [7:0] shifter;
// --- 1. state register -------------------------------------------------
always @(posedge clk or negedge rst_n)
if (!rst_n) state <= IDLE;
else state <= next_state;
// --- 2. next-state logic -----------------------------------------------
always @(*) begin
next_state = state;
case (state)
IDLE: if (!rx_sync) next_state = START; // falling edge = start
// Count HALF a bit to land in the middle of the start bit, then
// re-check it. A short glitch will have gone by now -> reject.
START: if (tick && tick_cnt == OS/2 - 1)
next_state = rx_sync ? IDLE : DATA;
DATA: if (tick && tick_cnt == OS-1 && bit_cnt == 3'd7)
next_state = STOP;
STOP: if (tick && tick_cnt == OS-1)
next_state = IDLE;
default: next_state = IDLE;
endcase
end
// --- 3. datapath + registered outputs ----------------------------------
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
tick_cnt <= 5'd0; bit_cnt <= 3'd0; shifter <= 8'd0;
data <= 8'd0; valid <= 1'b0; frame_err <= 1'b0;
end else begin
valid <= 1'b0; // defaults: both are 1-cycle pulses
frame_err <= 1'b0;
case (state)
IDLE: tick_cnt <= 5'd0;
START: if (tick) begin
bit_cnt <= 3'd0;
// Restarting the count at mid-start-bit is what aligns every
// later sample to the middle of its own bit.
if (tick_cnt == OS/2 - 1) tick_cnt <= 5'd0;
else tick_cnt <= tick_cnt + 1'b1;
end
DATA: if (tick) begin
if (tick_cnt == OS-1) begin
tick_cnt <= 5'd0;
shifter <= {rx_sync, shifter[7:1]}; // LSB first: enter at top
bit_cnt <= bit_cnt + 1'b1;
end else
tick_cnt <= tick_cnt + 1'b1;
end
STOP: if (tick) begin
if (tick_cnt == OS-1) begin
tick_cnt <= 5'd0;
data <= shifter;
valid <= rx_sync; // stop bit high -> good frame
frame_err <= ~rx_sync; // stop bit low -> misaligned
end else
tick_cnt <= tick_cnt + 1'b1;
end
endcase
end
end
endmodule
Note the port name:
rx_sync
The rx pin comes from another board, with no relationship to your clock. Feeding
it directly into an FSM is a textbook metastability bug - the input must pass through a
two-flop synchronizer before it reaches this module. Naming the port
rx_sync is a cheap way to make that contract impossible to miss during review.
Volume 05 covers why two flops, and what "resolved" actually means.
An APB protocol controller
AMBA APB is the simplest bus in the ARM family, and its three-state machine is worth knowing verbatim - it turns up constantly in interviews as "describe a bus protocol FSM".
module apb_master_fsm (
input wire clk,
input wire rst_n,
input wire req, // a transfer is wanted
input wire pready, // slave says the transfer can complete
output reg psel,
output reg penable
);
localparam [1:0] IDLE = 2'd0, SETUP = 2'd1, ACCESS = 2'd2;
reg [1:0] state, next_state;
always @(posedge clk or negedge rst_n)
if (!rst_n) state <= IDLE;
else state <= next_state;
always @(*) begin
next_state = state;
case (state)
IDLE : if (req) next_state = SETUP;
SETUP : next_state = ACCESS; // always exactly 1 cycle
ACCESS: if (pready) next_state = req ? SETUP : IDLE; // back-to-back
default: next_state = IDLE;
endcase
end
// Style 3: registered outputs decoded from next_state.
// SETUP -> PSEL = 1, PENABLE = 0
// ACCESS -> PSEL = 1, PENABLE = 1
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin
psel <= 1'b0;
penable <= 1'b0;
end else begin
psel <= (next_state == SETUP) || (next_state == ACCESS);
penable <= (next_state == ACCESS);
end
end
endmodule
Why SETUP exists at all
APB deliberately spends a whole cycle with
PSEL high and
PENABLE low. That cycle gives the address and control signals time to settle
before the slave is told to act, which is what lets APB be implemented with slow,
low-power peripherals. When an interviewer asks "why is APB two phases?", that is the
answer: setup then enable, so the slave never acts on unsettled signals.
4.5 Fault-tolerant & safe FSM design
Five states encoded in three bits leaves three unused encodings. In a lab those never occur. In a satellite, a medical device, or a car, a single high-energy particle striking a flip-flop can flip it - a single event upset - and drop your machine into an encoding it was never designed to be in.
always @(*) begin
next_state = S0; // safe default for EVERY path
case (state)
S0 : next_state = din ? S1 : S0;
S1 : next_state = din ? S1 : S10;
S10 : next_state = din ? S101 : S0;
S101 : next_state = din ? S1011 : S10;
S1011: next_state = din ? S1 : S10;
// Enumerate the unused encodings EXPLICITLY. Writing them out stops
// the synthesis tool treating them as unreachable don't-cares and
// optimising the recovery logic away.
3'd5, 3'd6, 3'd7: next_state = S0;
default: next_state = S0;
endcase
end
full_case parallel_case - the evil twins
You will see these pragmas in legacy RTL. Both are dangerous:
parallel_casetells synthesis to assume branches are mutually exclusive even when they are not, so the hardware can disagree with simulation.full_casetells synthesis that unlisted values are don't-care - which is precisely how it deletes the recovery path you just wrote, turning a safe FSM back into a hanging one.
Detecting corruption in a one-hot machine
One-hot has a useful property: legality is checkable at runtime. Exactly one bit must be set, and any SEU breaks that invariant immediately.
// "Exactly one bit set" without a population count:
// clearing the lowest set bit of a one-hot value yields zero.
wire state_legal = (state != 5'b0) && ((state & (state - 1'b1)) == 5'b0);
always @(posedge clk or negedge rst_n) begin
if (!rst_n) state <= S0;
else if (!state_legal) state <= S0; // corrupted -> forced recovery
else state <= next_state;
end
// In SystemVerilog (Volume 09) you would also add a formal check:
// assert property (@(posedge clk) disable iff (!rst_n) $onehot(state));
| Technique | Protects against | Cost |
|---|---|---|
| Explicit illegal-state recovery | Hangs after an upset | A few gates |
| One-hot legality check | Detects any single bit flip | One small comparator |
| Hamming distance ≥ 3 encoding | Detects 2 flips, corrects 1 | Extra state bits |
| Triple modular redundancy | Corrects any single-copy failure | 3× area, plus voters |
| Watchdog timer | Any hang, from any cause | One counter |
Interview grilling - "Your FSM works in simulation but hangs on the board once a week. Where do you look?"
This is a debugging question, and they want a method, not a guess. Work outward:
- Asynchronous inputs entering the FSM unsynchronized. Overwhelmingly the most likely cause, and it fits the symptom exactly - metastability is rare and random, so it presents as "works fine, then occasionally does not". Check every input crossing a clock domain.
- Reset release. If the reset is asynchronous and not synchronized (Volume 3.2), part of the machine can start a cycle late and land in a state combination the design never anticipated.
-
No illegal-state recovery. Check the synthesis report for whether
your
defaultbranch actually survived, and grep the codebase forfull_case. - A Mealy output feeding another domain. A combinational output that glitches can be sampled mid-glitch by downstream logic.
- Timing violations at temperature. A path that just barely closes in the report can fail in a hot enclosure. Check the report at the slow corner.
The sentence that lands: "Intermittent and rare points at metastability or timing margin, not at logic. If the logic were wrong it would fail every time, deterministically - so I would start by auditing every asynchronous input and the reset path before I re-read the state diagram."
Volume 04 recap
| Concept | The one thing to remember |
|---|---|
| Moore vs Mealy | Mealy is one cycle earlier and fewer states, at the cost of an input-to-output combinational path. |
| Medvedev | The output is the state register - zero decode, zero glitch. |
| Sequence detectors | Name each state after the longest matched prefix. Transitions then fall out mechanically. |
| Coding style | Style 3. Registered outputs give the next block a full clock period. |
| Style 3 detail | Decode the output register from next_state, or it lags a cycle. |
| Defaults | Open every combinational block with defaults, or you infer a latch. |
| Encoding | One-hot on FPGA (decode is one wire); binary on ASIC for small machines. |
| Async inputs | Never let an unsynchronized signal reach an FSM. Name the port to enforce it. |
| Safe FSM | Enumerate unused encodings explicitly. Never use full_case. |