RTL Design Patterns · Chapter 4 · FSM Design
FSM + Datapath (FSMD)
Almost nothing you ship is a single piece. A block that computes a GCD, walks a memory, or serializes a byte is a controller driving a datapath. The FSM tells a collection of registers, adders, comparators, and muxes what to do each cycle, and reads back a few status flags to decide what to do next. The controller emits control signals down into the datapath and the datapath returns status up to the controller, such as zero, less-than, equal, or done. That two-way interface across a clean boundary is the most important composition in RTL, because it is how you build anything that takes more than one cycle. Keep the two separate and the design scales; fold the datapath into the states and you get a monolith. This lesson builds a GCD engine, controller and datapath composed, in SystemVerilog, Verilog, and VHDL, and dwells on the control-status timing bug.
Intermediate16 min readRTL Design PatternsFSMDController DatapathControl Status InterfaceGCD EngineMulti-Cycle Datapath
Chapter 4 · Section 4.6 · FSM Design
1. The Engineering Problem
You need a block that computes the greatest common divisor of two numbers. You know the algorithm — Euclid by subtraction: while the two values differ, subtract the smaller from the larger; when they are equal, that value is the answer. In software it is four lines. In hardware it is the moment the whole track has been building toward, because you cannot write it as one expression. A GCD takes a variable, data-dependent number of cycles — GCD(48,36) needs a handful of subtractions, GCD(1000000,3) needs hundreds of thousands — so there is no single combinational cloud that produces the answer. You must step through the computation, holding intermediate values in registers, deciding each cycle whether to subtract-X-from-Y or Y-from-X or stop, and you must decide based on a comparison of the values you are holding.
Sit with what that requires and the shape of the solution appears on its own. You need state — registers to hold the current X and Y between cycles (Chapter 2). You need arithmetic — a subtractor to compute the difference, and a comparator to ask "is X less than Y? are they equal?" (Chapters 1 and 3). You need selection — muxes to route either operand into the subtractor and to choose what loads back into each register (Chapter 1). And you need sequencing — something that walks the algorithm: get the operands in, keep subtracting until they are equal, then signal done (Chapter 4, the FSM you already know). The registers, the subtractor, the comparator, the muxes — those hold and transform the data; call that collection the datapath. The FSM that walks the algorithm and tells the datapath what to do each cycle — that is the controller.
Here is the part that is not obvious until you try to write it wrong: those two responsibilities must stay separate, connected only by a narrow interface. The controller must not contain the data — it should not know that X is 48, only that "X is not less than Y, so subtract Y from X this cycle." The datapath must not contain the algorithm — it should not know it is computing a GCD, only that its control inputs said "load the subtractor result into X." The controller reaches into the datapath with control signals (register enables, mux selects, an op command) and the datapath reaches back with status flags (X-less-than-Y, X-equal-Y). Get that separation right and you have a machine you can widen, retime, and verify one half at a time. Fold the subtraction and comparison into the FSM's state transitions instead — a monolith where every state hardcodes an operand relationship — and you have something that works for GCD and teaches you nothing, scales to nothing, and cannot be verified except end to end. This page is that separation, done deliberately: the FSM + Datapath pattern, or FSMD.
// GCD by subtraction is data-dependent in LENGTH -> it cannot be one combinational cloud:
// while (x != y) if (x > y) x = x - y; else y = y - x; // variable #iterations
// return x;
// So you must STEP it. Two responsibilities fall out, and they must stay SEPARATE:
// DATAPATH — holds and transforms DATA:
// x_reg, y_reg // Chapter 2: registers hold X and Y between cycles
// x_lt_y, x_eq_y // Chapters 1/3: comparator asks the questions
// diff = big - small // Chapters 1/3: subtractor + input muxes do the work
// CONTROLLER — walks the ALGORITHM, emits control, reads status:
// IDLE -> COMPARE -> SUB -> ... -> DONE // Chapter 4: the FSM
// controls: en_x, en_y, sel_* // DOWN into the datapath
// status: x_lt_y, x_eq_y // UP from the datapath -> which branch?
// The interface between them — control DOWN, status UP — is the whole pattern (FSMD).2. Mental Model
3. Pattern Anatomy
An FSMD has exactly three parts and one interface: the controller (an FSM), the datapath (registers + functional units + muxes), and the control/status interface that binds them. Take them in turn.
The datapath — what holds and transforms the data. For our GCD engine the datapath is: two working registers x_reg and y_reg (the values being reduced); a comparator that continuously produces the status flags x_lt_y (x_reg < y_reg) and x_eq_y (x_reg == y_reg); a subtractor that computes a difference; and input muxes that route the operands. Concretely, the subtractor computes big − small, and a select decides which register loads the result: when X is the larger, subtract Y from X and reload X; when Y is the larger, subtract X from Y and reload Y. Every register has an enable (en_x, en_y) so it only updates when the controller says so — an enabled register is a load-mux feeding a flop (Chapter 2.2). The datapath is entirely combinational logic plus these two registers; it has no notion of "GCD," only "on this control, load this."
The controller — the FSM that walks the algorithm. It is the three-piece machine from 4.1: a state register, next-state logic, and output (control) logic. Its states are the phases of the procedure: IDLE (wait for start, latch the operands), COMPARE (look at the status flags and decide), SUB (command one subtraction), and DONE (assert done, hold the result). Its outputs are the datapath's control signals; its inputs are start, and the datapath's status flags. Crucially, the controller carries no data — it never adds, never compares values itself; it only reads the one-bit flags the datapath computed and emits one-bit controls. That is what keeps the controller small: a GCD over 64-bit operands has the same four-state controller as one over 8-bit operands.
The control/status interface — the contract between them. This is the load-bearing part. Control signals (controller → datapath, "down"): load (latch the initial operands from the input ports into X and Y), en_x / en_y (which register updates this cycle), sel_sub (which direction the subtractor runs — X−Y or Y−X). Status flags (datapath → controller, "up"): x_lt_y, x_eq_y. The controller in COMPARE reads x_eq_y to decide whether to finish, and x_lt_y to decide which register to reduce; in SUB it asserts the enable and select that perform that reduction. The interface is deliberately narrow — a few control bits down, a couple of status bits up — and that narrowness is the point: it is the seam along which you can verify each half in isolation and change each half independently.
The FSMD interface — control DOWN into the datapath, status UP to the controller
data flowThe second visual opens the datapath box and shows the GCD engine concretely — the two registers, the comparator that produces the status, the subtractor, and the muxes the control signals steer.
Inside the datapath — the GCD-by-subtraction engine the controller drives
data flowOne reasoning thread runs under all of it: the status flags are combinational functions of the register outputs. The comparator reads x_reg and y_reg — values that only change on a clock edge — and produces x_lt_y / x_eq_y that are valid this cycle for this cycle's register contents. The controller therefore reads the status in the same cycle it plans to act on it, before the enable it is about to assert changes the registers on the next edge. Getting that timing relationship right — status reflects the current register state, control acts to produce the next — is the entire subtlety of the pattern, and getting it wrong (§7) is its signature failure.
4. Real RTL Implementation
This is the core of the page. We build the GCD engine in three parts — (a) the datapath (X/Y registers, comparator, subtractor, input muxes; driven by control, producing status; WIDTH-generic), (b) the controller FSM (emits control, branches on status), and (c) the composed FSMD plus the control/status timing bug beside its fix — and each is shown in SystemVerilog, Verilog, and VHDL with an RTL block and a self-checking clocked testbench. The worked example is the same throughout: reduce two operands by Euclid's subtraction, and prove the result on GCD(48,36) = 12.
Two conventions run through every block. The reset is a synchronous, active-high rst (as in 2.3) that returns the controller to IDLE. Every datapath register has an explicit enable — it updates only when the controller asserts it — so the controller has full, cycle-accurate command of the data, and no register ever moves on its own. Widths are WIDTH-generic: the operands, registers, subtractor, and result are all WIDTH bits; the comparator and controller are width-independent.
4a. The datapath — registers, comparator, subtractor, input muxes
The datapath holds x_reg and y_reg, compares them to produce the status, and subtracts under control. It has no state machine inside it: it is combinational logic plus two enabled registers, and it exposes a clean control/status interface. The subtractor always computes larger − smaller internally; sel_sub and the two enables decide which register absorbs the result.
module gcd_datapath #(
parameter int WIDTH = 8
)(
input logic clk,
input logic rst, // synchronous, active-high
input logic [WIDTH-1:0] x_in, y_in, // initial operands
// control IN (from the controller, "down"):
input logic load, // latch x_in/y_in into the registers
input logic en_x, en_y, // which register updates this cycle
input logic sel_sub, // 0: x_reg <= x_reg - y_reg ; 1: y_reg <= y_reg - x_reg
// status OUT (to the controller, "up"):
output logic x_lt_y, // x_reg < y_reg (combinational)
output logic x_eq_y, // x_reg == y_reg (combinational)
output logic [WIDTH-1:0] result // x_reg (== GCD once x_eq_y)
);
logic [WIDTH-1:0] x_reg, y_reg;
// STATUS: combinational comparator over the CURRENT register contents. These are
// valid THIS cycle for THIS cycle's x_reg/y_reg — the controller branches on them
// before the enable it asserts changes the registers on the next edge.
assign x_lt_y = (x_reg < y_reg);
assign x_eq_y = (x_reg == y_reg);
assign result = x_reg;
// DATAPATH registers with explicit ENABLES. load has priority (initial capture);
// otherwise each register updates only when the controller enables it, absorbing
// the subtractor result routed by sel_sub. No register moves without a control.
always_ff @(posedge clk) begin
if (rst) begin
x_reg <= '0;
y_reg <= '0;
end else if (load) begin
x_reg <= x_in; // capture operands
y_reg <= y_in;
end else begin
if (en_x) x_reg <= x_reg - y_reg; // reduce X by Y (used when x_reg > y_reg)
if (en_y) y_reg <= y_reg - x_reg; // reduce Y by X (used when y_reg > x_reg)
end
end
// sel_sub selects the direction at the controller; here en_x/en_y encode it directly,
// which is the same mux — the controller asserts exactly one of them in SUB.
endmoduleThe datapath testbench drives the control interface by hand — no controller yet — to prove the primitive operations in isolation: load captures the operands; the status flags read the registers correctly; and an enabled subtraction reduces exactly the intended register. Verifying the datapath alone, before wiring the controller, is the payoff of the clean interface.
module gcd_datapath_tb;
localparam int WIDTH = 8;
logic clk = 1'b0, rst, load, en_x, en_y, sel_sub;
logic [WIDTH-1:0] x_in, y_in, result;
logic x_lt_y, x_eq_y;
int errors = 0;
gcd_datapath #(.WIDTH(WIDTH)) dut (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
always #5 clk = ~clk;
initial begin
rst = 1'b1; load = 1'b0; en_x = 1'b0; en_y = 1'b0; sel_sub = 1'b0;
x_in = 8'd48; y_in = 8'd36;
@(posedge clk); #1; rst = 1'b0;
// LOAD: capture 48/36 into the registers.
load = 1'b1; @(posedge clk); #1; load = 1'b0;
assert (result === 8'd48) else begin $error("load: x_reg=%0d exp=48", result); errors++; end
// STATUS on 48 vs 36: 48 is NOT less than 36, and they are not equal.
assert (x_lt_y === 1'b0 && x_eq_y === 1'b0)
else begin $error("status(48,36): x_lt_y=%b x_eq_y=%b", x_lt_y, x_eq_y); errors++; end
// ONE ENABLED SUBTRACTION: x_reg > y_reg, so reduce X (en_x). 48-36 = 12.
en_x = 1'b1; @(posedge clk); #1; en_x = 1'b0;
assert (result === 8'd12) else begin $error("sub: x_reg=%0d exp=12", result); errors++; end
// Now 12 vs 36: 12 IS less than 36.
assert (x_lt_y === 1'b1) else begin $error("status(12,36): x_lt_y=%b exp=1", x_lt_y); errors++; end
if (errors == 0) $display("PASS: datapath loads, compares, and subtracts on command");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog datapath is the same structure with reg/wire typing; the comparator is a continuous assign, and the enabled registers live in an always @(posedge clk).
module gcd_datapath #(
parameter WIDTH = 8
)(
input wire clk,
input wire rst,
input wire [WIDTH-1:0] x_in, y_in,
input wire load,
input wire en_x, en_y,
input wire sel_sub,
output wire x_lt_y,
output wire x_eq_y,
output wire [WIDTH-1:0] result
);
reg [WIDTH-1:0] x_reg, y_reg;
// STATUS: combinational comparator over the current register contents.
assign x_lt_y = (x_reg < y_reg);
assign x_eq_y = (x_reg == y_reg);
assign result = x_reg;
always @(posedge clk) begin
if (rst) begin
x_reg <= {WIDTH{1'b0}};
y_reg <= {WIDTH{1'b0}};
end else if (load) begin
x_reg <= x_in;
y_reg <= y_in;
end else begin
if (en_x) x_reg <= x_reg - y_reg; // reduce X (when x_reg > y_reg)
if (en_y) y_reg <= y_reg - x_reg; // reduce Y (when y_reg > x_reg)
end
end
// sel_sub kept in the port list for interface parity; en_x/en_y encode direction.
wire _unused = sel_sub;
endmodule module gcd_datapath_tb;
parameter WIDTH = 8;
reg clk, rst, load, en_x, en_y, sel_sub;
reg [WIDTH-1:0] x_in, y_in;
wire [WIDTH-1:0] result;
wire x_lt_y, x_eq_y;
integer errors;
gcd_datapath #(.WIDTH(WIDTH)) dut (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
initial clk = 1'b0;
always #5 clk = ~clk;
initial begin
errors = 0;
rst = 1'b1; load = 1'b0; en_x = 1'b0; en_y = 1'b0; sel_sub = 1'b0;
x_in = 8'd48; y_in = 8'd36;
@(posedge clk); #1; rst = 1'b0;
load = 1'b1; @(posedge clk); #1; load = 1'b0;
if (result !== 8'd48) begin $display("FAIL: load x_reg=%0d exp=48", result); errors=errors+1; end
if (x_lt_y !== 1'b0 || x_eq_y !== 1'b0) begin
$display("FAIL: status(48,36) x_lt_y=%b x_eq_y=%b", x_lt_y, x_eq_y); errors=errors+1; end
en_x = 1'b1; @(posedge clk); #1; en_x = 1'b0; // 48-36 = 12
if (result !== 8'd12) begin $display("FAIL: sub x_reg=%0d exp=12", result); errors=errors+1; end
if (x_lt_y !== 1'b1) begin $display("FAIL: status(12,36) x_lt_y=%b exp=1", x_lt_y); errors=errors+1; end
if (errors == 0) $display("PASS: datapath loads, compares, subtracts on command");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the datapath uses numeric_std: the registers are unsigned, the comparator is a relational expression on them, and the enabled updates live in a rising_edge(clk) process. The status flags are concurrent assignments off the register signals.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity gcd_datapath is
generic ( WIDTH : positive := 8 );
port (
clk : in std_logic;
rst : in std_logic; -- synchronous, active-high
x_in : in std_logic_vector(WIDTH-1 downto 0);
y_in : in std_logic_vector(WIDTH-1 downto 0);
load : in std_logic; -- capture operands
en_x : in std_logic; -- reduce X this cycle
en_y : in std_logic; -- reduce Y this cycle
sel_sub : in std_logic; -- interface parity (en_x/en_y encode direction)
x_lt_y : out std_logic; -- status: x_reg < y_reg
x_eq_y : out std_logic; -- status: x_reg = y_reg
result : out std_logic_vector(WIDTH-1 downto 0) -- x_reg
);
end entity;
architecture rtl of gcd_datapath is
signal x_reg, y_reg : unsigned(WIDTH-1 downto 0);
begin
-- STATUS: combinational comparator over the current register contents.
x_lt_y <= '1' when x_reg < y_reg else '0';
x_eq_y <= '1' when x_reg = y_reg else '0';
result <= std_logic_vector(x_reg);
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then
x_reg <= (others => '0');
y_reg <= (others => '0');
elsif load = '1' then
x_reg <= unsigned(x_in);
y_reg <= unsigned(y_in);
else
if en_x = '1' then x_reg <= x_reg - y_reg; end if; -- reduce X
if en_y = '1' then y_reg <= y_reg - x_reg; end if; -- reduce Y
end if;
end if;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity gcd_datapath_tb is
end entity;
architecture sim of gcd_datapath_tb is
constant WIDTH : positive := 8;
signal clk : std_logic := '0';
signal rst, load, en_x, en_y, sel_sub : std_logic := '0';
signal x_in, y_in, result : std_logic_vector(WIDTH-1 downto 0);
signal x_lt_y, x_eq_y : std_logic;
begin
dut : entity work.gcd_datapath
generic map (WIDTH => WIDTH)
port map (clk => clk, rst => rst, x_in => x_in, y_in => y_in,
load => load, en_x => en_x, en_y => en_y, sel_sub => sel_sub,
x_lt_y => x_lt_y, x_eq_y => x_eq_y, result => result);
clkgen : process
begin
clk <= '0'; wait for 5 ns;
clk <= '1'; wait for 5 ns;
end process;
stim : process
begin
rst <= '1'; x_in <= std_logic_vector(to_unsigned(48, WIDTH));
y_in <= std_logic_vector(to_unsigned(36, WIDTH));
wait until rising_edge(clk); wait for 1 ns; rst <= '0';
load <= '1'; wait until rising_edge(clk); wait for 1 ns; load <= '0';
assert result = std_logic_vector(to_unsigned(48, WIDTH))
report "load: x_reg /= 48" severity error;
assert x_lt_y = '0' and x_eq_y = '0'
report "status(48,36) wrong" severity error;
en_x <= '1'; wait until rising_edge(clk); wait for 1 ns; en_x <= '0'; -- 48-36 = 12
assert result = std_logic_vector(to_unsigned(12, WIDTH))
report "sub: x_reg /= 12" severity error;
assert x_lt_y = '1'
report "status(12,36): x_lt_y /= 1" severity error;
report "gcd_datapath self-check complete" severity note;
wait;
end process;
end architecture;4b. The controller — the FSM that emits control and branches on status
The controller is the three-piece FSM from 4.1, and it carries no data. Its states are the phases of Euclid's procedure — IDLE, COMPARE, SUB, DONE — and its outputs are exactly the datapath's control signals. In COMPARE it reads the status flags: if x_eq_y, the operands are equal and it goes to DONE; otherwise it asserts the enable for the larger register (chosen by x_lt_y) and goes to SUB, which loops back to COMPARE. Note the shape: the controller is a Moore-style machine whose control outputs are decoded from the state (plus, in COMPARE/SUB, from the live status — a Mealy-style tap where a same-cycle decision is needed, exactly the trade of 4.2).
module gcd_controller (
input logic clk,
input logic rst, // synchronous, active-high
input logic start, // begin a computation (operands presented on x_in/y_in)
// status IN (from the datapath, "up"):
input logic x_lt_y,
input logic x_eq_y,
// control OUT (to the datapath, "down"):
output logic load,
output logic en_x, en_y,
output logic sel_sub,
output logic done // result valid, held stable
);
typedef enum logic [1:0] {IDLE, COMPARE, SUB, DONE} state_t;
state_t state, next_state;
// NEXT-STATE logic — branches on start and the datapath STATUS flags.
always_comb begin
next_state = state; // default: hold (latch-free)
unique case (state)
IDLE: next_state = start ? COMPARE : IDLE;
COMPARE: next_state = x_eq_y ? DONE : SUB; // equal -> finished
SUB: next_state = COMPARE; // one subtraction, then re-compare
DONE: next_state = start ? COMPARE : DONE; // hold result until re-started
endcase
end
// STATE register: synchronous reset to IDLE.
always_ff @(posedge clk)
if (rst) state <= IDLE;
else state <= next_state;
// CONTROL (output) logic — decoded from state, and in SUB from the live status.
// Default every control to 0, then assert only what each state needs (latch-free).
always_comb begin
load = 1'b0; en_x = 1'b0; en_y = 1'b0; sel_sub = 1'b0; done = 1'b0;
unique case (state)
IDLE: load = start; // capture operands as we leave IDLE
COMPARE: ; // pure decision cycle — no datapath change
SUB: begin
// reduce the LARGER register: if x_lt_y, Y is larger -> en_y; else X -> en_x.
en_x = ~x_lt_y;
en_y = x_lt_y;
sel_sub = x_lt_y; // direction flag (parity with the datapath)
end
DONE: done = 1'b1; // result valid and held
endcase
end
endmoduleBecause the controller has no datapath, its testbench drives the status flags as stimulus and checks the control outputs — proving the FSM emits the right command in each state and branches correctly on status, entirely independent of any real arithmetic.
module gcd_controller_tb;
logic clk = 1'b0, rst, start, x_lt_y, x_eq_y;
logic load, en_x, en_y, sel_sub, done;
int errors = 0;
gcd_controller dut (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
always #5 clk = ~clk;
initial begin
rst = 1'b1; start = 1'b0; x_lt_y = 1'b0; x_eq_y = 1'b0;
@(posedge clk); #1; rst = 1'b0;
// IDLE + start -> load asserted this cycle, then move to COMPARE.
start = 1'b1; #1;
assert (load === 1'b1) else begin $error("IDLE: load not asserted on start"); errors++; end
@(posedge clk); start = 1'b0; #1; // now in COMPARE
// COMPARE with x_lt_y=0, x_eq_y=0 -> next is SUB; in SUB expect en_x (reduce X).
x_lt_y = 1'b0; x_eq_y = 1'b0; @(posedge clk); #1; // now in SUB
assert (en_x === 1'b1 && en_y === 1'b0)
else begin $error("SUB (x>=y): expected en_x, got en_x=%b en_y=%b", en_x, en_y); errors++; end
// Back in COMPARE; make Y the larger (x_lt_y=1) -> in SUB expect en_y.
@(posedge clk); #1; x_lt_y = 1'b1; x_eq_y = 1'b0; @(posedge clk); #1; // SUB again
assert (en_y === 1'b1 && en_x === 1'b0)
else begin $error("SUB (x<y): expected en_y, got en_x=%b en_y=%b", en_x, en_y); errors++; end
// Back in COMPARE; assert equal -> next is DONE, done raised.
@(posedge clk); #1; x_eq_y = 1'b1; @(posedge clk); #1; // DONE
assert (done === 1'b1) else begin $error("DONE: done not asserted on x_eq_y"); errors++; end
if (errors == 0) $display("PASS: controller emits correct control and branches on status");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleThe Verilog controller is the same machine with localparam state codes; the output logic is a defaulted always @(*), latch-free by the default-assign discipline of 1.1.
module gcd_controller (
input wire clk,
input wire rst,
input wire start,
input wire x_lt_y,
input wire x_eq_y,
output reg load,
output reg en_x, en_y,
output reg sel_sub,
output reg done
);
localparam IDLE = 2'd0, COMPARE = 2'd1, SUB = 2'd2, DONE = 2'd3;
reg [1:0] state, next_state;
always @(*) begin
next_state = state;
case (state)
IDLE: next_state = start ? COMPARE : IDLE;
COMPARE: next_state = x_eq_y ? DONE : SUB;
SUB: next_state = COMPARE;
DONE: next_state = start ? COMPARE : DONE;
default: next_state = IDLE;
endcase
end
always @(posedge clk)
if (rst) state <= IDLE;
else state <= next_state;
always @(*) begin
load = 1'b0; en_x = 1'b0; en_y = 1'b0; sel_sub = 1'b0; done = 1'b0;
case (state)
IDLE: load = start;
COMPARE: ; // decision cycle
SUB: begin
en_x = ~x_lt_y; // reduce the larger register
en_y = x_lt_y;
sel_sub = x_lt_y;
end
DONE: done = 1'b1;
default: ;
endcase
end
endmodule module gcd_controller_tb;
reg clk, rst, start, x_lt_y, x_eq_y;
wire load, en_x, en_y, sel_sub, done;
integer errors;
gcd_controller dut (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
initial clk = 1'b0;
always #5 clk = ~clk;
initial begin
errors = 0;
rst = 1'b1; start = 1'b0; x_lt_y = 1'b0; x_eq_y = 1'b0;
@(posedge clk); #1; rst = 1'b0;
start = 1'b1; #1;
if (load !== 1'b1) begin $display("FAIL: IDLE load not asserted"); errors=errors+1; end
@(posedge clk); start = 1'b0; #1; // COMPARE
x_lt_y = 1'b0; x_eq_y = 1'b0; @(posedge clk); #1; // SUB
if (en_x !== 1'b1 || en_y !== 1'b0) begin
$display("FAIL: SUB(x>=y) en_x=%b en_y=%b", en_x, en_y); errors=errors+1; end
@(posedge clk); #1; x_lt_y = 1'b1; @(posedge clk); #1; // SUB again
if (en_y !== 1'b1 || en_x !== 1'b0) begin
$display("FAIL: SUB(x<y) en_x=%b en_y=%b", en_x, en_y); errors=errors+1; end
@(posedge clk); #1; x_eq_y = 1'b1; @(posedge clk); #1; // DONE
if (done !== 1'b1) begin $display("FAIL: DONE not asserted"); errors=errors+1; end
if (errors == 0) $display("PASS: controller emits correct control, branches on status");
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleIn VHDL the controller is an enumerated state type with two processes — a rising_edge(clk) state register and a combinational next-state/output process — the output arm defaulting every control before the case asserts what each state needs.
library ieee;
use ieee.std_logic_1164.all;
entity gcd_controller is
port (
clk : in std_logic;
rst : in std_logic;
start : in std_logic;
x_lt_y : in std_logic;
x_eq_y : in std_logic;
load : out std_logic;
en_x : out std_logic;
en_y : out std_logic;
sel_sub : out std_logic;
done : out std_logic
);
end entity;
architecture rtl of gcd_controller is
type state_t is (IDLE, COMPARE, SUB, DONE_ST);
signal state, next_state : state_t;
begin
-- STATE register: synchronous reset to IDLE.
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then state <= IDLE; else state <= next_state; end if;
end if;
end process;
-- NEXT-STATE + CONTROL: combinational, defaulted (latch-free).
process (state, start, x_lt_y, x_eq_y)
begin
next_state <= state;
load <= '0'; en_x <= '0'; en_y <= '0'; sel_sub <= '0'; done <= '0';
case state is
when IDLE =>
load <= start;
if start = '1' then next_state <= COMPARE; end if;
when COMPARE =>
if x_eq_y = '1' then next_state <= DONE_ST; else next_state <= SUB; end if;
when SUB =>
en_x <= not x_lt_y; -- reduce the larger register
en_y <= x_lt_y;
sel_sub <= x_lt_y;
next_state <= COMPARE;
when DONE_ST =>
done <= '1';
if start = '1' then next_state <= COMPARE; end if;
end case;
end process;
end architecture; library ieee;
use ieee.std_logic_1164.all;
entity gcd_controller_tb is
end entity;
architecture sim of gcd_controller_tb is
signal clk : std_logic := '0';
signal rst, start, x_lt_y, x_eq_y : std_logic := '0';
signal load, en_x, en_y, sel_sub, done : std_logic;
begin
dut : entity work.gcd_controller
port map (clk => clk, rst => rst, start => start,
x_lt_y => x_lt_y, x_eq_y => x_eq_y,
load => load, en_x => en_x, en_y => en_y, sel_sub => sel_sub, done => done);
clkgen : process
begin
clk <= '0'; wait for 5 ns;
clk <= '1'; wait for 5 ns;
end process;
stim : process
begin
rst <= '1'; wait until rising_edge(clk); wait for 1 ns; rst <= '0';
start <= '1'; wait for 1 ns;
assert load = '1' report "IDLE: load not asserted on start" severity error;
wait until rising_edge(clk); start <= '0'; wait for 1 ns; -- COMPARE
x_lt_y <= '0'; x_eq_y <= '0'; wait until rising_edge(clk); wait for 1 ns; -- SUB
assert en_x = '1' and en_y = '0'
report "SUB(x>=y): expected en_x" severity error;
wait until rising_edge(clk); wait for 1 ns; x_lt_y <= '1';
wait until rising_edge(clk); wait for 1 ns; -- SUB again
assert en_y = '1' and en_x = '0'
report "SUB(x<y): expected en_y" severity error;
wait until rising_edge(clk); wait for 1 ns; x_eq_y <= '1';
wait until rising_edge(clk); wait for 1 ns; -- DONE
assert done = '1' report "DONE: done not asserted" severity error;
report "gcd_controller self-check complete" severity note;
wait;
end process;
end architecture;4c. The composed FSMD — and the control/status timing bug beside its fix
Now wire them together: the controller's control outputs drive the datapath's control inputs, and the datapath's status flags drive the controller's status inputs. That is the FSMD. Then comes pattern (c), the flagship failure, shown as buggy vs fixed and dramatized in §7: the buggy composition samples a datapath status flag one cycle out of alignment — it registers the combinational status and branches on the stale (previous-cycle) value — so the controller occasionally takes the wrong branch and returns the wrong GCD or spends an extra cycle. The fix samples the combinational, current-cycle status in the state it acts on.
module gcd_fsmd #(
parameter int WIDTH = 8
)(
input logic clk,
input logic rst,
input logic start,
input logic [WIDTH-1:0] x_in, y_in,
output logic done,
output logic [WIDTH-1:0] result
);
// control/status interface wires — the whole contract between the two halves:
logic load, en_x, en_y, sel_sub; // control DOWN
logic x_lt_y, x_eq_y; // status UP
gcd_controller u_ctrl (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
gcd_datapath #(.WIDTH(WIDTH)) u_dpath (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
endmoduleThe composed testbench runs the whole engine to completion on the worked example and asserts both the result and the timing: GCD(48,36) must come out 12, and done must rise (not hang, not finish early). Running to done and checking the golden answer is the end-to-end proof the two halves compose correctly.
module gcd_fsmd_tb;
localparam int WIDTH = 8;
logic clk = 1'b0, rst, start, done;
logic [WIDTH-1:0] x_in, y_in, result;
int cycles = 0, errors = 0;
gcd_fsmd #(.WIDTH(WIDTH)) dut (.clk(clk), .rst(rst), .start(start),
.x_in(x_in), .y_in(y_in), .done(done), .result(result));
always #5 clk = ~clk;
initial begin
rst = 1'b1; start = 1'b0; x_in = 8'd48; y_in = 8'd36; // golden: GCD(48,36) = 12
@(posedge clk); #1; rst = 1'b0;
start = 1'b1; @(posedge clk); #1; start = 1'b0; // kick off
// Run to completion with a cycle cap so a hang (never-asserted done) FAILS.
while (done !== 1'b1 && cycles < 1000) begin
@(posedge clk); #1; cycles++;
end
assert (done === 1'b1)
else begin $error("done never asserted (hang) after %0d cycles", cycles); errors++; end
assert (result === 8'd12)
else begin $error("GCD(48,36) = %0d, expected 12", result); errors++; end
if (errors == 0) $display("PASS: GCD(48,36) = 12 in %0d cycles, done asserted", cycles);
else $display("FAIL: %0d mismatches", errors);
$finish;
end
endmoduleNow the timing bug. The signature FSMD failure is a control/status misalignment: the buggy variant inserts a register on the status path — it flops x_eq_y / x_lt_y and branches on the registered (one-cycle-late) status — so in COMPARE the controller decides using the comparison from the previous register contents, not the current ones. It reaches DONE a cycle early on some operands (declaring equality before the last subtraction has settled) or takes the wrong direction. The fix branches on the combinational status that reflects the current registers.
// BUGGY: the status is REGISTERED before the controller sees it. In COMPARE the FSM
// branches on x_eq_y_q / x_lt_y_q, which reflect LAST cycle's x_reg/y_reg — one
// cycle STALE. On operands where the equality/relationship flips on the final
// subtraction, the FSM decides on the OLD comparison -> wrong branch: it can
// declare DONE a cycle early (result off) or subtract in the wrong direction.
module gcd_fsmd_bad #(parameter int WIDTH = 8) (
input logic clk, rst, start,
input logic [WIDTH-1:0] x_in, y_in,
output logic done,
output logic [WIDTH-1:0] result
);
logic load, en_x, en_y, sel_sub;
logic x_lt_y, x_eq_y;
logic x_lt_y_q, x_eq_y_q; // the offending registers
// DANGER: register the combinational status, then feed the STALE copy to the FSM.
always_ff @(posedge clk) begin
if (rst) begin x_lt_y_q <= 1'b0; x_eq_y_q <= 1'b0; end
else begin x_lt_y_q <= x_lt_y; x_eq_y_q <= x_eq_y; end
end
gcd_controller u_ctrl (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y_q), .x_eq_y(x_eq_y_q), // <-- STALE status: one cycle off
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
gcd_datapath #(.WIDTH(WIDTH)) u_dpath (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
endmodule
// FIXED: feed the COMBINATIONAL, current-cycle status straight to the controller, so
// COMPARE branches on the comparison of the registers as they are THIS cycle.
module gcd_fsmd_good #(parameter int WIDTH = 8) (
input logic clk, rst, start,
input logic [WIDTH-1:0] x_in, y_in,
output logic done,
output logic [WIDTH-1:0] result
);
logic load, en_x, en_y, sel_sub;
logic x_lt_y, x_eq_y;
gcd_controller u_ctrl (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), // <-- current-cycle status: aligned
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
gcd_datapath #(.WIDTH(WIDTH)) u_dpath (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
endmodule module gcd_status_bug_tb;
localparam int WIDTH = 8;
logic clk = 1'b0, rst, start, done;
logic [WIDTH-1:0] x_in, y_in, result;
int cycles, errors = 0;
// Bind to gcd_fsmd_good to PASS. Point at gcd_fsmd_bad to see the stale-status
// machine return the wrong GCD (or hang) on operands where the comparison flips
// on the final subtraction — the control/status misalignment of section 7.
gcd_fsmd_good dut (.clk(clk), .rst(rst), .start(start),
.x_in(x_in), .y_in(y_in), .done(done), .result(result));
task automatic run_gcd(input [WIDTH-1:0] a, b, exp);
begin
rst = 1'b1; start = 1'b0; x_in = a; y_in = b;
@(posedge clk); #1; rst = 1'b0;
start = 1'b1; @(posedge clk); #1; start = 1'b0;
cycles = 0;
while (done !== 1'b1 && cycles < 1000) begin @(posedge clk); #1; cycles++; end
assert (done === 1'b1 && result === exp)
else begin $error("GCD(%0d,%0d)=%0d exp=%0d done=%b", a, b, result, exp, done); errors++; end
end
endtask
initial begin
run_gcd(8'd48, 8'd36, 8'd12); // golden worked example
run_gcd(8'd36, 8'd48, 8'd12); // reversed operands (relationship flips first)
run_gcd(8'd17, 8'd5, 8'd1); // coprime: comparison flips on the final steps
run_gcd(8'd30, 8'd12, 8'd6); // another with a late equality
if (errors == 0) $display("PASS: FSMD returns correct GCD across operand sets (status aligned)");
else $display("FAIL: %0d mismatches (stale status?)", errors);
$finish;
end
endmoduleThe Verilog buggy/fixed pair is the same story: the bad top registers the status before the controller sees it; the good top wires the combinational status straight through.
// BUGGY: register the status, feed the STALE copy to the FSM -> COMPARE decides on the
// previous cycle's comparison -> wrong branch on operands whose relationship
// flips on the final subtraction (wrong result or an extra/missing cycle).
module gcd_fsmd_bad #(parameter WIDTH = 8) (
input wire clk, rst, start,
input wire [WIDTH-1:0] x_in, y_in,
output wire done,
output wire [WIDTH-1:0] result
);
wire load, en_x, en_y, sel_sub;
wire x_lt_y, x_eq_y;
reg x_lt_y_q, x_eq_y_q;
always @(posedge clk)
if (rst) begin x_lt_y_q <= 1'b0; x_eq_y_q <= 1'b0; end
else begin x_lt_y_q <= x_lt_y; x_eq_y_q <= x_eq_y; end
gcd_controller u_ctrl (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y_q), .x_eq_y(x_eq_y_q), // STALE status: one cycle off
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
gcd_datapath #(.WIDTH(WIDTH)) u_dpath (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
endmodule
// FIXED: combinational, current-cycle status straight to the controller.
module gcd_fsmd_good #(parameter WIDTH = 8) (
input wire clk, rst, start,
input wire [WIDTH-1:0] x_in, y_in,
output wire done,
output wire [WIDTH-1:0] result
);
wire load, en_x, en_y, sel_sub;
wire x_lt_y, x_eq_y;
gcd_controller u_ctrl (.clk(clk), .rst(rst), .start(start),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), // current-cycle status: aligned
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub), .done(done));
gcd_datapath #(.WIDTH(WIDTH)) u_dpath (.clk(clk), .rst(rst), .x_in(x_in), .y_in(y_in),
.load(load), .en_x(en_x), .en_y(en_y), .sel_sub(sel_sub),
.x_lt_y(x_lt_y), .x_eq_y(x_eq_y), .result(result));
endmodule module gcd_status_bug_tb;
parameter WIDTH = 8;
reg clk, rst, start;
reg [WIDTH-1:0] x_in, y_in;
wire done;
wire [WIDTH-1:0] result;
integer cycles, errors;
// Bind to gcd_fsmd_good to PASS; gcd_fsmd_bad returns wrong GCDs on some operands.
gcd_fsmd_good dut (.clk(clk), .rst(rst), .start(start),
.x_in(x_in), .y_in(y_in), .done(done), .result(result));
initial clk = 1'b0;
always #5 clk = ~clk;
task run_gcd;
input [WIDTH-1:0] a, b, exp;
begin
rst = 1'b1; start = 1'b0; x_in = a; y_in = b;
@(posedge clk); #1; rst = 1'b0;
start = 1'b1; @(posedge clk); #1; start = 1'b0;
cycles = 0;
while (done !== 1'b1 && cycles < 1000) begin @(posedge clk); #1; cycles = cycles + 1; end
if (done !== 1'b1 || result !== exp) begin
$display("FAIL: GCD(%0d,%0d)=%0d exp=%0d done=%b", a, b, result, exp, done);
errors = errors + 1;
end
end
endtask
initial begin
errors = 0;
run_gcd(8'd48, 8'd36, 8'd12);
run_gcd(8'd36, 8'd48, 8'd12);
run_gcd(8'd17, 8'd5, 8'd1);
run_gcd(8'd30, 8'd12, 8'd6);
if (errors == 0) $display("PASS: correct GCD across operand sets (status aligned)");
else $display("FAIL: %0d mismatches (stale status?)", errors);
$finish;
end
endmoduleIn VHDL the bug is the same: the bad architecture registers the status signals and connects the registered copies to the controller; the good one connects the combinational status directly.
library ieee;
use ieee.std_logic_1164.all;
-- BUGGY: status is registered, so COMPARE branches on last cycle's comparison.
entity gcd_fsmd_bad is
generic ( WIDTH : positive := 8 );
port ( clk, rst, start : in std_logic;
x_in, y_in : in std_logic_vector(WIDTH-1 downto 0);
done : out std_logic; result : out std_logic_vector(WIDTH-1 downto 0) );
end entity;
architecture rtl of gcd_fsmd_bad is
signal load, en_x, en_y, sel_sub : std_logic;
signal x_lt_y, x_eq_y : std_logic;
signal x_lt_y_q, x_eq_y_q : std_logic;
begin
process (clk)
begin
if rising_edge(clk) then
if rst = '1' then x_lt_y_q <= '0'; x_eq_y_q <= '0';
else x_lt_y_q <= x_lt_y; x_eq_y_q <= x_eq_y; end if; -- STALE status
end if;
end process;
u_ctrl : entity work.gcd_controller
port map (clk => clk, rst => rst, start => start,
x_lt_y => x_lt_y_q, x_eq_y => x_eq_y_q, -- one cycle off
load => load, en_x => en_x, en_y => en_y, sel_sub => sel_sub, done => done);
u_dpath : entity work.gcd_datapath generic map (WIDTH => WIDTH)
port map (clk => clk, rst => rst, x_in => x_in, y_in => y_in,
load => load, en_x => en_x, en_y => en_y, sel_sub => sel_sub,
x_lt_y => x_lt_y, x_eq_y => x_eq_y, result => result);
end architecture;
-- FIXED: combinational, current-cycle status straight to the controller.
library ieee;
use ieee.std_logic_1164.all;
entity gcd_fsmd_good is
generic ( WIDTH : positive := 8 );
port ( clk, rst, start : in std_logic;
x_in, y_in : in std_logic_vector(WIDTH-1 downto 0);
done : out std_logic; result : out std_logic_vector(WIDTH-1 downto 0) );
end entity;
architecture rtl of gcd_fsmd_good is
signal load, en_x, en_y, sel_sub : std_logic;
signal x_lt_y, x_eq_y : std_logic;
begin
u_ctrl : entity work.gcd_controller
port map (clk => clk, rst => rst, start => start,
x_lt_y => x_lt_y, x_eq_y => x_eq_y, -- aligned
load => load, en_x => en_x, en_y => en_y, sel_sub => sel_sub, done => done);
u_dpath : entity work.gcd_datapath generic map (WIDTH => WIDTH)
port map (clk => clk, rst => rst, x_in => x_in, y_in => y_in,
load => load, en_x => en_x, en_y => en_y, sel_sub => sel_sub,
x_lt_y => x_lt_y, x_eq_y => x_eq_y, result => result);
end architecture; library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity gcd_status_bug_tb is
end entity;
architecture sim of gcd_status_bug_tb is
constant WIDTH : positive := 8;
signal clk : std_logic := '0';
signal rst, start, done : std_logic := '0';
signal x_in, y_in, result : std_logic_vector(WIDTH-1 downto 0);
signal errors : integer := 0;
begin
-- Bind to gcd_fsmd_good (aligned). gcd_fsmd_bad mis-computes on some operands.
dut : entity work.gcd_fsmd_good generic map (WIDTH => WIDTH)
port map (clk => clk, rst => rst, start => start,
x_in => x_in, y_in => y_in, done => done, result => result);
clkgen : process
begin
clk <= '0'; wait for 5 ns;
clk <= '1'; wait for 5 ns;
end process;
stim : process
procedure run_gcd(a, b, exp : integer) is
variable cycles : integer := 0;
begin
rst <= '1'; start <= '0';
x_in <= std_logic_vector(to_unsigned(a, WIDTH));
y_in <= std_logic_vector(to_unsigned(b, WIDTH));
wait until rising_edge(clk); wait for 1 ns; rst <= '0';
start <= '1'; wait until rising_edge(clk); wait for 1 ns; start <= '0';
cycles := 0;
while done /= '1' and cycles < 1000 loop
wait until rising_edge(clk); wait for 1 ns; cycles := cycles + 1;
end loop;
if done /= '1' or result /= std_logic_vector(to_unsigned(exp, WIDTH)) then
report "GCD mismatch" severity error;
errors <= errors + 1;
end if;
end procedure;
begin
run_gcd(48, 36, 12);
run_gcd(36, 48, 12);
run_gcd(17, 5, 1);
run_gcd(30, 12, 6);
if errors = 0 then report "PASS: correct GCD across operand sets (status aligned)" severity note;
else report "FAIL: mismatches (stale status?)" severity error; end if;
wait;
end process;
end architecture;Across all three languages the lesson is one sentence: the datapath status is a combinational function of the current register contents, so the controller must branch on it in the same cycle — insert a register on the status path and the FSM decides on stale data, taking the wrong branch on exactly the operands where the comparison flips at the end.
5. Verification Strategy
FSMD verification has a structure the pattern itself hands you: you can verify each half against its interface in isolation, then verify the composition end-to-end. That is the direct payoff of the clean control/status boundary — three testbenches, each proving one thing.
The datapath does the right thing on command; the controller emits the right command and branches correctly on status; and the two composed compute the golden answer in the right number of cycles, sampling status in the correct cycle.
- Verify the datapath alone by driving its control interface. With no controller present, drive
load,en_x,en_y,sel_subby hand and check the registers, the status flags, and the result:loadcaptures the operands;x_lt_y/x_eq_yread the current registers correctly; an enabled subtraction reduces exactly the intended register by exactly the right amount. The §4a testbenches do this — SVassert (result === 8'd12), Verilogif (result !== 8'd12) $display("FAIL"), VHDLassert result = to_unsigned(12,…) severity error. If the datapath is right against its interface, every controller that drives it correctly will work. - Verify the controller alone by driving its status interface. With no datapath present, drive the status flags
x_lt_y/x_eq_yas stimulus and check the control outputs:IDLE + startassertsload;COMPAREwithx_eq_ygoes toDONE;SUBasserts the enable for the larger register (chosen byx_lt_y). The §4b testbenches do exactly this. The controller is data-independent, so this exhaustively covers its logic without any arithmetic at all — the clean interface is what makes that possible. - Verify the composition end-to-end, running to
done. Present operands, pulsestart, and run the FSMD untildonerises — with a cycle cap so a hang (adonethat never asserts, e.g. from a wrong branch that never reaches equality) fails rather than looping forever. Then assert the result and, where it matters, the cycle count. The §4c testbench runsGCD(48,36)and assertsresult === 12anddone === 1; extend it with several operand sets, including reversed operands and coprime pairs, because those are where a status-timing bug (§7) diverges. The invariant checked is simple and total: for every legal operand pair, the FSMD terminates and returns the true GCD. - Assert control signals only in the right states. A distinct check: confirm each control is asserted only where it should be —
loadonly as the machine leavesIDLE,en_x/en_yonly inSUB,doneonly inDONE. A control leaking into the wrong state silently corrupts the datapath (a register updates when the controller did not intend it — one of the §6 mistakes). This is checkable by watching the control bus against the observable state or the phase of the run. - Assert the status is sampled in the right cycle. The property that catches the flagship bug: the controller must branch in
COMPAREon the comparison of the registers as they are that cycle, i.e. on the combinational status, not a registered copy. Conceptually: the branch taken in cycle N must be consistent withx_reg/y_regin cycle N. A cross-check that catches the misalignment is to compare the FSMD result against an independent software/reference GCD over a sweep of operands; the stale-status machine (§4c bad) diverges precisely on operands whose relationship flips on the final subtraction (reversed and coprime pairs), which a random or directed operand sweep exposes. - Conceptual invariants. Four properties must always hold: (i) the datapath never updates a register without the controller's enable (no unintended data movement); (ii) the controller carries no data — its next state is a function only of state,
start, and the one-bit status flags; (iii) every run terminates (the values are non-increasing and equality is eventually reached), sodonealways eventually asserts for legal operands; (iv) the status the controller branches on reflects the current register contents (control/status alignment). Property (iv) is the one the DebugLab violates. - Corner cases and expected waveform. Exercise equal operands (
GCD(n,n) = n— the machine should go straight toDONEfrom the firstCOMPARE, no subtraction); one operand a multiple of the other (GCD(24,6)=6— repeated subtraction in one direction only); reversed operands (GCD(36,48)— the first subtraction goes the other direction); coprime pairs (GCD(17,5)=1— many alternating subtractions); and a re-startafterDONE(the machine must accept new operands and recompute). On a correct waveform,startpulses,loadasserts for one cycle, then the machine alternatesCOMPARE/SUB— eachSUBcycle you see exactly one ofen_x/en_yhigh and the corresponding register step down — untilx_eq_yholds inCOMPARE, at which pointdonerises andresultholds the GCD stable. The visual signature is the register values marching down to a common value while the state ping-pongsCOMPARE↔SUB.
6. Common Mistakes
Sampling a combinational status one cycle off. The signature bug (§7). The datapath status flags are combinational functions of the current register contents, so the controller must branch on them in the same cycle. Insert a register on the status path (or, symmetrically, read a registered status as if it were combinational) and the FSM decides on the previous cycle's comparison — it takes the wrong branch or reaches DONE a cycle early, and it does so only on operands where the comparison flips on the final step, so it passes casual testing and fails on a sweep. Keep the control/status timing aligned: current-cycle status drives this cycle's branch.
A control signal asserted in the wrong state. Because the control outputs are decoded from state, it is easy to let one leak — en_x still high in COMPARE, or load asserted a cycle too long. A stray enable makes the datapath update when the controller did not intend it, corrupting a register mid-algorithm. The discipline is the latch-free output style of 1.1 and 4.5: default every control to its inactive value, then assert only what the current state needs — so no control can carry over into a state that did not ask for it.
A datapath register that updates without the controller's enable. If a register is written unconditionally (no enable, or an enable that is accidentally always true), it moves every cycle regardless of the FSM — the controller loses command of the data and the algorithm desynchronizes from the datapath. Every datapath register in an FSMD must update only under a control the controller asserts; an "always-load" register is not part of a controllable datapath. This is the register-with-enable pattern of 2.2 applied under a controller.
Reading a multi-cycle datapath result too early. Not every datapath operation completes in one cycle. If the datapath contains a multi-cycle unit — a pipelined multiplier, a multi-cycle divider, a RAM read with a cycle of latency — the controller must wait the unit's latency before sampling its result or its done/valid status. Commanding the operation and reading the answer the very next cycle, when the unit needs three, reads a stale or partial value. The controller must account for the datapath's own latency: add wait states, or branch on the unit's own valid/done flag, not on a fixed cycle count assumed wrong.
Folding the datapath into the FSM's states — the monolith. The tempting shortcut is to skip the separate datapath and encode the data relationships directly in the FSM: states like "X bigger by a lot," transitions that hardcode operand comparisons, arithmetic done inside the next-state logic. It works for a toy and collapses immediately: the state count explodes with the data, you cannot widen the datapath without rewriting the FSM, and you cannot verify the two halves independently. FSMD is worth the two-module split precisely because the alternative does not scale — keep the controller data-free and the datapath algorithm-free.
Putting the status comparison in the controller instead of the datapath. A subtle version of the monolith: the controller receives x_reg and y_reg (the full data) and compares them itself in its next-state logic. Now the controller carries data, its next-state logic contains a WIDTH-bit comparator, and the clean one-bit interface is gone — widen the operands and the controller changes. The comparator belongs in the datapath; the controller should see only the one-bit result of the comparison. If the controller's inputs include a data bus, it is no longer just a controller.
7. DebugLab
The GCD engine that is right on 48,36 and wrong on 36,48 — a control/status timing bug
The engineering lesson: the control/status interface has a timing dimension, not just a wiring one — a datapath status is valid in a specific cycle, and the controller must sample it in exactly that cycle; register one side of the interface (or assume a wrong datapath latency) and the two halves desynchronize by a cycle, producing wrong results on precisely the operands that exercise the misalignment. The tell is unmistakable: an FSMD that is right on some operands and wrong on others, deterministic per operand but seemingly random across them, with each half passing its own testbench — that is a control/status timing bug, not a logic bug in either half. The fix is always to restore alignment: sample the combinational status in the cycle you act on it, or, if a side must be registered, delay the other side by the same cycle so control and status still meet. Never register one side of the interface alone, and never assume a datapath's latency — branch on its valid/done. The reasoning is identical across SystemVerilog, Verilog, and VHDL.
8. Interview Q&A
9. Exercises
Design and reasoning exercises — no syntax drills. Each rehearses the "control down, status up, keep them aligned" habit.
Exercise 1 — Draw the FSMD and trace GCD(48,36)
Draw the GCD engine as a controller box and a datapath box with the control signals (load, en_x, en_y) as arrows down and the status flags (x_lt_y, x_eq_y) as arrows up. Then build a cycle-by-cycle table for GCD(48,36): for each cycle list the state, x_reg, y_reg, the status flags, and which control is asserted, from start through done. Confirm the machine reaches x_eq_y with result = 12, and count the total cycles. Then state which single cycle's status decision, if delayed by one cycle, would change the answer — and why.
Exercise 2 — Widen the datapath, don't touch the controller
The engine is WIDTH-generic. State exactly what changes in the datapath and what changes in the controller when you widen the operands from 8 to 32 bits, and explain why the controller is untouched. Then describe one feature you could add — an iteration counter that reports how many subtractions the GCD took — and identify precisely which module(s) change and which control/status signals you would add to the interface.
Exercise 3 — Diagnose the operand-dependent wrong answer
A colleague's FSMD GCD returns the correct answer for GCD(48,36) but the wrong answer for GCD(36,48) and for the coprime pair GCD(17,5); each half's own testbench passes. State the single most likely root cause, the precise timing mechanism (name what is misaligned and by how much), why it is right on some operands and wrong on others, why the two per-half testbenches missed it, and the exact interface change that fixes it. Then name the one verification move (beyond a single directed test) that would have caught it before integration.
Exercise 4 — Absorb a multi-cycle datapath unit
The single-cycle subtractor is replaced by a functional unit that takes three cycles to produce its result and raises its own op_valid when the result is ready. Rewrite the controller's state sequence (in words or a state diagram) so the FSMD is correct with the new unit and would still be correct if the unit's latency later changed to two or four cycles. Explain why branching on op_valid rather than counting cycles is the latency-agnostic choice, and state what specifically breaks if you keep the old "read the result the next cycle" sequence.
10. Related Tutorials
Continue in RTL Design Patterns (sibling and forward links unlock as they ship):
- FSM State Encoding (binary vs one-hot) — Chapter 4.4; how the controller's state is encoded, and why one-hot makes each control-output decode a single-bit test off the state.
- Safe FSM Design & Latch-Free Outputs — Chapter 4.5; the default-assign discipline that keeps the controller's control outputs latch-free, and recovering the controller from an illegal state without corrupting the datapath.
- FSM Worked Example — Chapter 4.7; a full end-to-end FSMD build carried from specification to verified RTL, the natural next step after this pattern.
- valid/ready Handshake — Chapter 9.1; the control/status interface generalized into a standard flow-control contract between blocks — the same "signal down, status up" idea across a module boundary.
- ALU Construction — Chapter 5; the multi-function datapath unit an FSMD controller most often drives, with an op-select that is exactly a control signal.
Backward / in-track dependencies:
- FSM Fundamentals — Chapter 4.1; the three-piece controller (state register + next-state logic + output logic) that becomes the FSMD's controller.
- Moore vs Mealy — Chapter 4.2; whether a control output is decoded from state alone (Moore) or from state and live status (Mealy) — the same-cycle status branch here is a Mealy tap.
- FSM Coding Styles (1/2/3-process) — Chapter 4.3; how to organize the controller's state/next-state/output logic into processes cleanly.
- The Register Pattern (D-FF) — Chapter 2.1; the datapath registers
x_reg/y_regthat hold the values between cycles. - Register with Enable / Load — Chapter 2.2; the enable on every datapath register that lets the controller command exactly when data moves.
- Multiplexers (2:1, N:1, one-hot) — Chapter 1.1; the input and load muxes the control signals steer inside the datapath.
- Comparators — Chapter 1; the datapath comparator that produces the
x_lt_y/x_eq_ystatus flags. - Up/Down Counters — Chapter 3; the counting datapath element a controller drives when the algorithm is count-based, with a terminal-count status.
- Synchronous Reset — Chapter 2.3; the sampled-on-the-edge reset that returns the controller to IDLE and clears the datapath registers.
Verilog v1 prerequisites (the grammar this pattern transcribes into):
- Case Statements — the
case (state)that expresses the controller's next-state and control-output logic. - Arithmetic Operators — the
-the datapath subtractor uses to reduce the operands. - Relational Operators — the
<and==the datapath comparator uses to produce the status flags. - Blocking and Non-Blocking Assignments — why the state and datapath registers use non-blocking (
<=) while the combinational next-state and control logic use blocking (=).
11. Summary
- FSMD is control driving datapath — the core RTL composition pattern. Almost nothing computes in one cycle, so real blocks are a controller (an FSM) sequencing a datapath (registers, adders, comparators, muxes) through a narrow, two-way interface: control down, status up. The controller holds the procedure and no data; the datapath holds the data and no procedure.
- The interface is control signals down, status flags up. The controller emits register enables, mux selects, and op commands down into the datapath to steer it this cycle, and the datapath returns single-bit status flags — zero, less-than, equal, done — up to the controller, which branches on them. That narrow, directional contract is the whole pattern, and it is built from the earlier patterns: the datapath is registers (Ch. 2), comparators and subtractors (Ch. 1/3), and muxes (Ch. 1) under a controller (Ch. 4).
- The separation is what makes it scale. Because the controller only branches on status and the datapath only responds to control, you widen the datapath (8→64 bits) with the controller untouched, and extend the controller without rewriting the datapath — and you verify each half against its interface in isolation, then the composition end-to-end (run to
done, assert the golden result and cycle count). The worked GCD engine returnsGCD(48,36) = 12, verified across three HDLs. - The signature failure is a control/status timing misalignment. The datapath status is combinational off the current registers, so the controller must branch on it the same cycle; register one side of the interface (or assume a wrong datapath latency) and the two halves desynchronize by a cycle — the machine returns the wrong answer on exactly the operands where the comparison flips at the end (the DebugLab), deterministic per operand yet seemingly random across them, with each half's own test passing.
- Keep control and status aligned, and never fold the datapath into the FSM. Sample the combinational status in the cycle you act on it; if a side must be registered for timing, delay the other by the same cycle; branch on a multi-cycle unit's valid/done rather than a hardcoded latency; and keep the controller data-free and the datapath algorithm-free — the monolith that fuses them works for a toy and scales to nothing. Built and self-check-verified here in SystemVerilog, Verilog, and VHDL.