The datapath holds a and b with load and subtract operations. Two status flags report greater-than and equal.
The controller waits for start, subtracts until the operands are equal, then reports done. This listing requires both inputs to be at least 1; with exactly one zero operand, subtraction makes no progress.
Watch state, a, b, and done across the nine slots. The slot table below it names the control behind each step.
Slot 1: idle in IDLE, start low, operands unknown.
Slot 2: start rises, and IDLE answers with load.
Slot 3: RUN with a = 12 and b = 8, so a > b selects sub_a.
Slot 4: a = 4 and b = 8, so a < b selects sub_b.
Slot 5: b = 4 and the operands match, so next is DONE.
Slot 6: DONE with done high and result 4.
Slot 7: back to IDLE with done low.
Slot 8: idle.
Slot 9: idle.
Slot | State | a | b | Flags | Control |
|---|---|---|---|---|---|
2 | IDLE | x | x | – | load (start seen) |
3 | RUN | 12 | 8 | a > b | sub_a |
4 | RUN | 4 | 8 | a < b | sub_b |
5 | RUN | 4 | 4 | a = b | – (next = DONE) |
6 | DONE | 4 | 4 | a = b | done |
Edge | Before edge / action | After edge settles |
|---|---|---|
0 (accept) | IDLE, start=1: load | RUN, a=12, b=8, done=0 |
1 | RUN, a>b: sub_a | RUN, a=4, b=8, done=0 |
2 | RUN, a<b: sub_b | RUN, a=4, b=4, done=0 |
3 | RUN, equal: enter DONE | DONE, done=1, result=4 |
4 (consume) | Consumer samples done=1 and result=4 | IDLE, done=0, result held |
Done asserts after edge 3, three periods after the edge-0 load. A consumer sampling pre-update values at rising edges sees it at edge 4. Equality is already combinational after edge 2; there is no extra output-register cycle.
The complete width-8 design and bounded checker follow: 961 positive pairs in 1..31, plus directed interface cases.
module gcd_dp #(parameter int W = 8) (
input logic clk,
input logic load, sub_a, sub_b,
input logic [W-1:0] a_in, b_in,
output logic a_gt_b, a_eq_b,
output logic [W-1:0] result
);
logic [W-1:0] a, b;
always_ff @(posedge clk)
if (load) begin a <= a_in; b <= b_in; end
else if (sub_a) a <= a - b;
else if (sub_b) b <= b - a;
assign a_gt_b = (a > b);
assign a_eq_b = (a == b);
assign result = a;
endmodule
module gcd_ctrl (
input logic clk, rst_n,
input logic start, a_gt_b, a_eq_b,
output logic load, sub_a, sub_b, done
);
typedef enum logic [1:0] {IDLE, RUN, DONE} state_t;
state_t state, next;
always_ff @(posedge clk or negedge rst_n)
if (!rst_n) state <= IDLE;
else state <= next;
always_comb begin
next = state; load = 1'b0; sub_a = 1'b0; sub_b = 1'b0; done = 1'b0;
unique case (state)
IDLE: if (start) begin load = 1'b1; next = RUN; end
RUN: if (a_eq_b) next = DONE;
else if (a_gt_b) sub_a = 1'b1;
else sub_b = 1'b1;
DONE: begin done = 1'b1; next = IDLE; end
default: next = IDLE;
endcase
end
endmodule
module gcd_top #(parameter int W = 8) (
input logic clk, rst_n, start,
input logic [W-1:0] a_in, b_in,
output logic done,
output logic [W-1:0] result
);
logic load, sub_a, sub_b, a_gt_b, a_eq_b;
gcd_ctrl u_ctrl (.*);
gcd_dp #(W) u_dp (.*);
endmodule
Every pair of operands from 1 to 31 gives the correct GCD, compared with a software reference, including cases where one operand is a multiple of the other.
A 100-cycle timeout rejects hangs for the enumerated positive pairs.
Back-to-back operations work: the machine returns to IDLE after done and accepts the next start.
Directed checks exercise changed operands and start while busy, an ignored DONE offer, exact load-to-done edges, one-cycle done, result hold and reset cancellation followed by a fresh operation. Errors identify time, context, state and controls and end in a fatal verdict.
The bounded checker covers 961 positive pairs in 1..31 and directed interface cases. The 100-cycle timeout rejects hangs for the enumerated pairs; it is not a proof of termination for every width or input.
The 1 ns post-edge samples use a 10 ns teaching clock. They are simulation scheduling margins, not physical delays.