A multicycle unsigned shift-add multiplier

Prerequisites: sequential circuits, nonblocking^{iNonblocking assignment An assignment written as <= in sequential RTL. It evaluates the right-hand side and schedules the update, allowing registers at the same edge to compute from the previous state. Learn more} assignments, counters, shifts and adders.

Reuse one adder over several clocks

Unsigned^{iUnsigned A rule for interpreting a bit pattern as a nonnegative integer. The n-bit range is 0 through 2^n−1 and may differ from the signed interpretation of the same bits. Learn more} W-bit multiplication sums partial products selected by each multiplier bit B:

Adding all partial products at once needs substantial addition logic. Here, one adder is used W times, trading area for throughput. Writing an RTL loop does not automatically create a multicycle circuit: registers^{iRegister A circuit that stores multiple bits of state. The synchronous registers in this course store their specified inputs at a clock edge. Learn more} must retain computational state between clocks, with a termination condition.

Accumulator P and shifted multiplicand M are 2W bits; right-shifting multiplier Q is W bits. Initialize P=0, M=zero-extend(A), Q=B. At each work clock, add M to P if Q[0]=1, then shift M left and Q right by one.

After W steps, Q=0 and P holds the full product. 2W bits suffice: $(2^W-1)^2<2^{2W}$, and intermediate unsigned partial-product sums never exceed the final product.

For A=13,B=11,W=4, Q's low bits are 1,1,0,1. P follows 0→13→39→39→143, using M=13→26→52→104. Shifts and the step counter must advance even during the third step with Q[0]=0.

Each column below is state just after request capture or a work edge. The first initializes; the next four perform work. At the third work edge, old Q[0]=0 holds only P while M and Q shift.

Define request and completion timing first

The interface accepts a request at a rising edge^{iRising edge The instant at which the clock changes from 0 to 1. Distinguish it from a level, which refers to the entire interval during which CLK=1. Learn more} with start=1 while idle. At that edge t0, only inputs are captured. Work runs from t1 through tW, and product and done become valid just after tW. Acceptance-to-completion latency is W clock periods, although counting the acceptance edge gives W+1 edges in total.

start is ignored while busy=1. At the completion edge, pre-edge busy is still 1, so no new request is accepted. The earliest next acceptance is tW+1, giving a minimum initiation interval of W+1 periods. Holding start high starts another operation at the next idle edge. The caller usually supplies a pulse aligned with acceptance.

module mul_iter #(parameter int W = 8) (
  input  logic clk, rst, start,
  input  logic [W-1:0] a, b,
  output logic busy, done,
  output logic [2*W-1:0] product
);
  localparam int CW = (W <= 1) ? 1 : $clog2(W);
  localparam logic [CW-1:0] LAST = CW'(W-1);
  logic [CW-1:0] step;
  logic [2*W-1:0] acc, m, next_acc;
  logic [W-1:0] q;

  assign next_acc = acc + (q[0] ? m : {2*W{1'b0}});

  always_ff @(posedge clk) begin
    if (rst) begin
      busy <= 1'b0;
      done <= 1'b0;
      product <= '0;
      acc <= '0;
      m <= '0;
      q <= '0;
      step <= '0;
    end else begin
      done <= 1'b0;
      if (!busy) begin
        if (start) begin
          busy <= 1'b1;
          acc <= '0;
          m <= {{W{1'b0}}, a};
          q <= b;
          step <= '0;
        end
      end else begin
        acc <= next_acc;
        m <= m << 1;
        q <= q >> 1;
        if (step == LAST) begin
          product <= next_acc;
          busy <= 1'b0;
          done <= 1'b1;
        end else begin
          step <= step + 1'b1;
        end
      end
    end
  end
endmodule

The design assumes W≥1 and sets CW to at least 1 to avoid a zero-bit counter at W=1. Reset is synchronous active-high and outranks an ongoing operation. External a,b may change after acceptance without affecting the result, since stored m,q are used. product changes only on reset or completion. done is a one-period pulse, not a valid signal held until consumption.

The final assignment is product<=next_acc, not product<=acc. Nonblocking right-hand sides read pre-update values, so outputting acc omits the last multiplier bit's partial product. For the same reason, placing q's shift assignment earlier does not change next_acc's use of current Q[0].

A computation invariant and practical choices

After k work steps,

Splitting Q into its even part and low bit shows that the relation survives the next step. At k=W, Q=0, so P=AB. This invariant^{iInvariant A condition that must remain true in every permitted execution. For example, the occupancy of a depth-4 FIFO must always lie between 0 and 4. Learn more} explains why the accumulate/shift order works more clearly than a few small waveforms alone.

Each work step's critical path includes a 2W-bit adder and input selection. Removing the multiplication operator does not guarantee a smaller or faster design. Compare dedicated FPGA DSP blocks, synthesis results and required throughput^{iThroughput The number of operations accepted or completed per unit time. A pipeline can increase throughput without reducing the latency of an individual operation. Learn more}. This module does not implement early exit, signed operands or output backpressure. The consumer must not miss done.

Test 0, 1, maximum values and B with only its highest bit set. Also test start and input changes while busy, and reset cancellation. Setting only B's top bit specifically exposes a missing final accumulation.