Long multiplication in hardware

Binary long multiplication adds the multiplicand, shifted by each set bit of the multiplier. The example below is 13 × 11 = 143.

      1101   (13, multiplicand)
    x 1011   (11, multiplier)
    ------
      1101   bit 0 = 1: add 13 << 0 =   13
     1101    bit 1 = 1: add 13 << 1 =   26
    0000     bit 2 = 0: nothing
   1101      bit 3 = 1: add 13 << 3 =  104
  --------
  10001111   = 143

The hardware runs one bit per cycle. The multiplicand shifts left, the multiplier shifts right, and an accumulator adds the multiplicand when bit 0 is set.

Watching it run

The waveform shows 13 × 11. Eight iterations follow the load; the pre-edge consumer observes done at edge 9 when acceptance is edge 0. This is nine inclusive load/working slots.

• Start: start pulses and busy rises while the operands load.

• Steps 1 to 2: the accumulator becomes 13, then 39 (0x27).

• Steps 3 to 4: bit 2 adds nothing, then bit 3 brings the total to 143 (0x8f).

• Steps 5 to 8: the higher bits are 0, so nothing more is added. Completion follows the eighth iteration.

Cost and speed

busy stays high during the DONE pulse and falls only on return to IDLE. Offer the next start as soon as busy is low; the next rising edge accepts it. Completion and acceptance availability are separate: done marks a valid product, while !busy marks readiness for a new operation.

• Latency convention: acceptance is edge 0; iterations run at edges 1 through W. Product and done are available after edge W; a rising-edge consumer samples them at W + 1. The test's inclusive load/working-slot count is W + 1 (9 for W = 8), not nine elapsed periods from acceptance. DONE returns to IDLE after edge W + 1, so the earliest next acceptance is W + 2.

• Area: one 2W-bit adder, three registers (accumulator, multiplicand, multiplier) and a counter.

• Speedups: stop early when the remaining multiplier bits are zero (variable latency), or handle 2 bits per cycle (radix-4).

For signed operands, use a Booth recoding or sign-correct the result. The unsigned design above is the foundation for both.

Common mistakes

Testbench

The complete multiplier and the exhaustive testbench over all input pairs, plus directed restarts on the first cycle where busy is low.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

module shift_add_mul #(parameter int W = 8) (
  input  logic           clk, rst_n,
  input  logic           start,
  input  logic [W-1:0]   a, b,
  output logic           busy, done,
  output logic [2*W-1:0] product
);
  typedef enum logic [1:0] {IDLE, RUN, DONE} state_t;
  state_t state;

  logic [2*W-1:0] mcand;          // multiplicand, shifts left each step
  logic [W-1:0]   mplier;         // multiplier, shifts right each step
  logic [2*W-1:0] acc;            // running sum
  logic [$clog2(W+1)-1:0] count;  // steps remaining

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      state <= IDLE; mcand <= '0; mplier <= '0; acc <= '0; count <= '0;
    end else begin
      unique case (state)
        IDLE: if (start) begin
          mcand  <= {{W{1'b0}}, a};
          mplier <= b;
          acc    <= '0;
          count  <= W[$clog2(W+1)-1:0];
          state  <= RUN;
        end
        RUN: begin
          if (mplier[0]) acc <= acc + mcand;          // add the shifted multiplicand if this bit is 1
          mcand  <= mcand << 1;
          mplier <= mplier >> 1;
          count  <= count - 1'b1;
          if (count == 1) state <= DONE;
        end
        DONE: state <= IDLE;
        default: state <= IDLE;
      endcase
    end

  assign busy    = (state != IDLE);               // includes DONE: !busy means start can be accepted
  assign done    = (state == DONE);
  assign product = acc;
endmodule

Related topics

• Combinational arithmetic

• Memory read sequencer