Every line of the algorithm answers two questions. Storage and arithmetic belong to the datapath, order and conditions to the controller.
gcd(a, b): // a, b >= 1
while (a != b)
if (a > b) a = a - b
else b = b - a
return aThe GCD loop needs two registers, subtractors, and comparators. Its loop and branch become states and transitions.
Algorithm element | Hardware | Belongs to |
|---|---|---|
Variables | Two registers | Datapath |
| Two subtractors (or one shared) | Datapath |
| Comparators, producing status flags | Datapath |
“while”, “if / else”, “return” | States and transitions | Controller |
Loading the inputs, signalling done |
| Interface |
Read the diagram as a conversation: the controller commands, the datapath reports.
Down the left arrow: load, sub_a and sub_b are control signals. They tell the registers what to do at the next edge.
Up the right arrow: a_eq_b and a_gt_b are status flags from the comparators. The FSM uses them to pick its next state.
Outside the boxes: start and done are the only signals the rest of the system sees.
Write the algorithm in plain pseudo-code.
List the variables → registers, the operations → functional units, the conditions → status flags.
Draw the datapath and mark which inputs are control signals (load, enable, select).
Derive the FSM: one state per distinct step; transitions on the status flags.
Write a table: in state S, with flags F, assert controls C and go to S′. The code is then mechanical.
The loop body runs once per clock in the same state (RUN); the if/else is expressed as different control signals in that state. States are needed only for distinct phases: waiting, working and reporting.