Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 37 ยท FSMs and Design

Datapath and Controller Design

Split a Verilog design into a datapath of registers and operators and an FSM controller, with a shift-and-add multiplier and a GCD calculator as worked examples.

Small FSMs decide things; real designs also compute things. Multipliers, dividers, CRC engines, packet parsers and filters all do work over several clock cycles, holding intermediate values in registers. The standard way to design them is to split the circuit into two cooperating parts:

  • the datapath: registers, multiplexers, adders, comparators, shifters, the hardware that holds and transforms data,
  • the controller: an FSM that sequences the datapath by driving its control signals (load, shift, select, enable) and reading its status flags (zero, done, carry).

This is known as an FSMD (finite state machine with datapath) or the "ASM chart" method. This lesson shows the method on a shift-and-add multiplier and on Euclid's GCD algorithm. If state machines are new, first read Moore and Mealy machines.

No Verilog simulator runs on this site, so the Verilog code is read-only. The C programs are labelled stand-ins: each C function mirrors the controller states and the datapath registers cycle by cycle, so you can see how many clocks the Verilog would take.

Thinking in registers and cycles

Start from the algorithm written as software, then decide what each statement costs in hardware:

  • Variables become registers.
  • Each assignment that needs a different source becomes a multiplexer input.
  • Each operator becomes a hardware unit (adder, comparator, shifter).
  • Loops and conditionals become states and transitions.

Hardware can do many things in one cycle (all the operators work in parallel), so the controller's job is to decide which registers capture a new value this cycle.

flowchart LR
  CT["Controller<br/>(FSM)"] -->|"control: load, shift, add"| DP["Datapath<br/>(registers, adder, mux)"]
  DP -->|"status: zero, lsb, done"| CT
  IN["start, operands"] --> DP
  IN --> CT
  DP --> OUT["result, done"]

The controller reads status flags and drives control signals; the datapath does the arithmetic.

Example 1: shift-and-add multiplier

To compute a * b for 8-bit numbers with one adder, use the schoolbook method: look at the lowest bit of b; if it is 1, add a to the result; then shift a left and b right; repeat 8 times.

Datapath registers: A (16 bits, holds the shifting multiplicand), B (8 bits), P (16-bit product), a 4-bit counter n. Control: load, add, shift. Status: B[0], n == 0.

VERILOG
module mult8 (
  input             clk, rst_n, start,
  input      [7:0]  a_in, b_in,
  output reg [15:0] product,
  output            done
);
  reg [15:0] A;
  reg [7:0]  B;
  reg [3:0]  n;
  reg        busy;

  localparam IDLE = 2'd0, RUN = 2'd1, FINISH = 2'd2;
  reg [1:0] state;

  assign done = (state == FINISH);

  always @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      state <= IDLE; product <= 16'd0; A <= 16'd0; B <= 8'd0; n <= 4'd0;
    end else case (state)
      IDLE: if (start) begin
        A <= {8'd0, a_in}; B <= b_in; product <= 16'd0; n <= 4'd8;
        state <= RUN;
      end
      RUN: begin
        if (B[0]) product <= product + A;    // add step
        A <= A << 1;                         // shift steps
        B <= B >> 1;
        n <= n - 4'd1;
        if (n == 4'd1) state <= FINISH;
      end
      FINISH: state <= IDLE;
    endcase
endmodule

This is the one-process style from the coding styles lesson: controller and datapath sit in one clocked block, which is fine at this size. Bigger designs separate them into two modules with an explicit interface of control and status wires, which makes each easier to test.

The C stand-in executes the same registers cycle by cycle:

C Stand-in: 8x8 shift-and-add multiplier, one cycle per loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The result is 143 after exactly 8 cycles, one per bit of the multiplier. A combinational a * b finishes in a single cycle but uses a large array of adders; the shift-and-add design uses one adder and takes 8 cycles. That area-versus-latency trade is the heart of datapath design.

Example 2: Euclid's GCD

The greatest common divisor by repeated subtraction: while x != y, subtract the smaller from the larger; when equal, that value is the GCD.

Software:

C
while (x != y) {
    if (x > y) x = x - y;
    else       y = y - x;
}

In hardware this needs two registers, two subtractors and a comparator giving three status bits (x == y, x > y). The controller waits for start, loads, then loops until x == y:

VERILOG
module gcd (
  input             clk, rst_n, start,
  input      [15:0] a, b,
  output reg [15:0] result,
  output            done
);
  localparam IDLE = 2'd0, LOOP = 2'd1, DONE = 2'd2;
  reg [1:0]  state;
  reg [15:0] x, y;

  assign done = (state == DONE);

  always @(posedge clk or negedge rst_n)
    if (!rst_n) begin state <= IDLE; x <= 0; y <= 0; result <= 0; end
    else case (state)
      IDLE: if (start) begin x <= a; y <= b; state <= LOOP; end
      LOOP: begin
        if (x == y)      begin result <= x; state <= DONE; end
        else if (x > y)  x <= x - y;
        else             y <= y - x;
      end
      DONE: state <= IDLE;
    endcase
endmodule

Because it loops while it works, the number of cycles depends on the inputs, so the controller must signal done; the user holds start high for one cycle and waits for done. This handshake (request, then acknowledge) is how multi-cycle blocks talk to the rest of the system.

C Stand-in: GCD controller counting cycles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Compare the cycle counts: equal inputs finish at once, awkward inputs take many cycles. A hardware designer would note that subtraction is slow for large ratios (gcd(1000000, 1) takes a million steps) and might use a binary GCD that only shifts and subtracts. Counting cycles before writing RTL is how you catch this.

The design process

  1. Write the algorithm in software (C or Python) and get it right.
  2. List the registers, operators and their widths; draw the datapath.
  3. Write the ASM chart or state diagram: states, transitions on status flags, control signals per state.
  4. Write the Verilog; keep datapath and controller separated when it gets big.
  5. Test with a self-checking bench against the software model (see self-checking testbenches).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In an FSMD design, what does the datapath send to the controller?

    The controller uses status flags from the datapath to choose its next state, and drives control signals back.
  2. 2. The shift-and-add multiplier computes an 8x8 product in how many cycles in the stand-in design?

    Each cycle handles one bit of the multiplier, so the loop runs 8 times regardless of the values.
  3. 3. Why does the GCD block need a done signal?

    The loop length varies with the data, so the user cannot know how long to wait without a handshake.
  4. 4. What is the trade-off between a combinational a * b and a shift-and-add multiplier?

    Sequential hardware reuses one adder over many cycles to save area. Combinational logic spends area to finish in one cycle.

Summary

  • Split computation designs into a datapath (registers and operators) and a controller (an FSM).
  • Variables become registers, operators become units, control flow becomes states.
  • A multi-cycle block needs a start/done handshake when its latency depends on data.
  • Count cycles in software first; trade area against latency deliberately.

Next: SystemVerilog Data Types: logic, enum and struct